Swarm Intelligence
http://www.huffingtonpost.com/2012/03/28/ant-mill-swarm-suicide_n_1386017.html
Beekman M., et al. Biological Foundations of Swarm Intelligence. http://link.springer.com/chapter/10.1007%2F978-3-540-74089-6_1
http://en.wikipedia.org/wiki/Ant_colony_optimization
http://www.youtube.com/watch?v=mA37cb10WMU – Swarming ant mill
http://www.youtube.com/watch?v=BkfHdEOgh5Q – Simulation with zerglings
Ants are a fascinating species, particularly in the way they navigate and forage for food. Instead of relying on conventional means of observation and memory to navigate its way through thick underbrush, this insect species has evolved to rely on swarm intelligence to survive in its environment. When an ant leaves its colony, it leaves behind a faint trail of pheromones so that it can find its way back home, however, once it leaves its nest, its motion is rather random until it finds some food to bring back. Then, it will return home with the food, leaving behind another pheromone trail of a much high concentration, depending on the quantity and quality of the food it finds. When other ants leave the anthill, they find themselves instinctively attracted to theses pheromones and, depending on the concentrations laid down, are more likely to walk in the direction of the pheromones. These ants, however, are not always guaranteed to follow the pheromone trails they find. Instead, they simply have a higher chance of choosing trails with more pheromones. This ensures that new trails are always being discovered, even if most of the colony is already set on one particular path. It has been observed that through this system of pheromones, large colonies of ants are able to not only quickly find food, but also optimize routes to the food it finds. Shorter paths will be crossed more frequently, leaving behind higher amounts of pheromone on that path, while higher quality foods will cause the ants to release higher concentration pheromones. These mechanisms cause the ant colonies, as a whole, to swarm to good food sources and efficiently harvest them back to the hive.
These behaviors can be described as herding behaviors, as the mechanisms that cause them are akin to the mechanisms behind the information cascade. When ants explore and forage the land outside of their hives, they instinctively sniff for pheromone trails that have been left behind. They are essentially looking for the decisions left behind by previous ants. Because the ants cannot always find signs of food until they have already found it, there does not exist a reliable private signal for each individual ant. Instead, each ant receives a random internal signal that tells the ant where to go. This ensures that the ant’s initial walks are random, and that even when pheromone trails are present, these ants can still be influenced to go in other directions. An ant colony’s mission to find optimal paths to a food source can be modeled as an information cascade. If we analyze this as a simple cascade model, each ant receives a random signal and decides on a path to the food it finds. Shorter paths can be traversed faster and thus more frequently. Ant can see pheromone trails and therefore see the number of decisions made on each path. They decide on a path based on the pheromone trails and the random signal it receives. Shorter paths will be decided more frequently and thus the ants will be more likely to decide on these paths. The cascade of these trails will cause these ants to converge on the shortest path.
Of course, there are factors that make this much more complex that a simple cascade model. Unlike the simple cascade model, this model enables an infinite number of possible choices. An ant decides on the choice of its path after is has found the food source and returns to the hive leaving a concentrated trail of pheromone on the path he takes. Making a choice also takes a nontrivial amount of time. Longer paths take longer to traverse and thus, pheromone trails take longer to lay down. These paths are therefore, all else being equal, decided on less frequently that a shorter path. Older pheromone trails evaporate away making older decision less and less significant. This mechanism is important, as it ensures that ant will stop foraging towards depleted food sources. The paths chosen are also not discrete decisions. Each path can be thought of as a series of smaller paths and after each segment, an ant makes a mini-decision on how to continue its path. This allows paths that are extremely concentrated to mutate by small amounts.
This behavior, however, does have a pitfall. Ants also rely on pheromones to navigate, especially when armies are moving across a forest. Because some ants are blind, they must rely solely on their pheromones to navigate. Because of this, if an ant is diverted and strays from the correct path, say, back to the colony, other ants may follow. These ants may create a pheromone trail going in the wrong direction, and as other ant follow, this false trail only grows stronger. A deadly phenomenon occurs when the leader of the false trail finds a previous segment of his trail, creating a loop. As these ants walk through the loop over and over again, the pheromone trail they leave grows only stronger, trapping these ants to walk in this look until they starve to death. This phenomenon is called an ant mill. This is an example of when a cascade of bad information can result in fatal consequences. When one ant decides on a bad path, other ants may make decisions based on these bad data. These ants detect the concentrated pheromones of many ants following a bad path and all converge onto a deadly spiral.
-lz228