Kill Decision meets Finding Nemo

This week’s post is inspired by the book Kill Decision by Daniel Suarez. Suarez is a relatively new Techno-Thriller author, and I love his books. In this book, unmanned drones already exist and are causing some major problems. How do these drones know what to do if they are not controlled remotely? How do they fight? Thats the scary part. It turns out they get their fighting instincts from some of the fiercest killers on the planet... Weaver ants. The female protagonist studies the social structure of ants, (she’s a myrmecologist) however unknown forces have taken the algorithm she has developed to implant in unmanned drones.

This video shows you everything you need to understand about how ants are attracted to pheromones and will sense the pheromones and move toward them. In the video the blue blobs are patches of food, and the purple blog is the nest. When ants find food they head back to the nest, but they also leave behind a trail of pheromones that other ants can follow. the stronger the scent the whiter the trail. Yuu can see how quickly the majority of the ants get to the strongest trail. In the case of drones in the book getting food equals killing people and tearing apart things.

The rest of the story you’ll have to read for yourself [1]. If you want to readd more about intelligence that arises from simple organisms and behavior check out Turtles, Termites, and Traffic Jams by Mitchel Resnick.

The ant intelligence in Kill Decision got me to thinking about swarming bees and schooling fish and flocking birds. Have you ever wondered how such creaters with supposedly no intelligence form themselves into groups that seemingly exhibit intelligent behavior? It turns out that there has been a lot of computer science work on this over the years, so I looked at some schooling algorithms and I wondered whether or not I could implemented something really simple in Python. I’ve always been interested to investigate how Pixar made the giant stampede of wildebeest in Lion King, or how the sardines in Nemo were modelled. Although there are many swarming algorithms that are used to solve really hard problems I’m going to go with something simple and graphical.

First Example

Here’s a simple example Suppose you have a bird or a fish and the only rule they have for where to go next is to head directly for the fish or bird that is “most directly in their line of vision.”

The procedure for this is pretty easy. First, iterate through all the other organisms in our simulated world. As we iterate we will:

  1. Eliminate all of those that are behind us. Lets assume that our organisms can only see things in front of them.
  2. Of all the things in front of us choose the one that is most closely aligned with our own heading.
  3. Change our heading to go directly toward that organism.

Here is a first try at implementing, and graphically showing the algorithm I’ve just described. Warning this is ugly code. This example took me 20 minutes to hack together, with little forethought or planning. But as you can see it works. As it turns out its really nothing like a swarm or a school of fish but more of a giant follow the leader game. What is interesting to me is that in just a short coding session implementing a single rule you do get something that looks like there is a pattern to the behavior.

Even though, as I said, the code above is ugly there are a couple of things I would point out that are important. The expression cos(radians(head)) determines whether the other object – swarm[j] is in front of or behind the object swarm[i]. We define “in front of” to be based on the heading of the object swarm[i]. This is important because we are assuming that you can only see objects in front of you.

Now the list, newhead is important, because when we are doing a simulation, that is simulating a bunch of things simultaneously you have to do things in the simulation in two steps.

  1. Each object must make a decision about their new heading.
  2. Each object takes action on their decision.

Although in the real world all of these decisions and actions happen in parallel in the non-parallel simulation we do them in two stages to simulate the parallelism. In code this plays out by having each object in the swarm make a decision about what its new heading will be and recording that decision in newhead. Once all of the decisions are made then we can go back and implement the decisions and update our display of the world swarm[i].setheading(newhead[i]) This is a good example of parallel array construction. Where the new heading for swarm[i] is in newhead[i].

With the initial implementation out of the way, lets look at a much nicer and cleaner version that illustrates some nice Object Oriented Programming techniques. If you are not so familiar with writing classes in Python you may want to take time to read about classes and inheritance.

An Object Oriented Implementation

Although this implementation does exactly the same thing as the first one you will hopefully find this one easier to read and follow. There are a couple of very important things about this code to notice. First, the class Schooler, is a subclass of Turtle. That is, Schooler ISA Turtle. This has some really great side effects in that all of the Turtle methods for getting location and heading are availalbe as self. methods.

We can also eliminate the parallel list construction used to hold the new position for the Schooler. The new position becomes an instance variable of the class. We still need to make the decision in one phase and take action on the decision in the second phase, but that is OK and the two loops make it very clear what is happening. getNewHeading then setHeadingAndMove.

Another important feature to notice is that the variable swarm is no longer a global variable, but rather has become a ‘class variable’ of the class Schooler. This means that every instance of the Schooler class can access the swarm as Schooler.swarm. In fact, individual instances can also access swarm as self.swarm but if an method makes a change to self.swarm then the variable becomes an instance variable for that instance which shadows the class variable.

A More Interesting Example

My initial example was pretty simplistic, as you can imagine there are lots of other ways to model this swarming or schooling behavior. Many models follow these three basic rules:

  1. Move in the same direction as your closest neighbors.
  2. Don’t stray off by yourself - stay close
  3. But not too close. Avoid collisions with your neighbors.

Simulations that demonstrate these rules have been around since the Boids program by was first created in 1986. You can implement your own version of this by creating a new subclass of Schooler called FocalFish. To get new behavior you will need to write a new getNewHeading method in the new class. Note, you will not need to write or re-write the setHeadingAndMove or __init__ methods!

This diagram may give you some ideas on how to implement your getNewHeading method.

../../_images/focalfish.png

In the diagram you can see that you can classify all the other organisms (Fish) into one of three zones: 1) Zone of repulsion, 2) zone of alignment, and 3) zone of attraction.

  1. In the zone of repulsion the current fish will seek to move itself away from its neighbors. You might think of doing this by finding the midpoint of all the neighbors, finding the heading to go towards that midpoint, and then doing going in the opposite direction.
  2. In the zone of alignment, the fish would want to align its heading with the average heading of all the fish in the zone. You might average the headings of all the other fish in this zone to get your own heading.
  3. In the zone of attraction you might calculate the midpoint of all the fish in the zone and then head toward that point.

Once you have these rules calculated it is fun to experiment a bit. Should you try to apply all three rules all the time? Or should you only apply the rule in the closest zone that has fish in it? If you apply the rules for more than one zone how should you combine the headings for the different zones?

If you have an interesting solution, please post it to the comments, it should be interesting to experiment. Next time we’ll look at some solutions and think about what would happen if a certain fish in the school was a ‘leader’ and or how a school/swarm would respond to an obstacle.

So, work on this little project then take a break and watch Finding Nemo and enjoy the behavior of the sardines in a completely new light.

Next Section - A Better Flocking Implementation