Friday, December 10, 2010

How Ants Solve the Shortest Path Problem

A Scientific American article reports the results of a new study of the techniques used by ants to quickly find routes in a changing maze that could be useful to systems engineers.

“In the wild, ant scouts deposit pheromones along the trails between food and the nest. Nest mates then follow the trail, laying their own pheromones, amplifying the markings along the path. Because the pheromones gradually evaporate, longer trails--on which ants are spread more thinly--carry lower pheromone concentrations than short trails. Since pheromone strength is what draws an ant to follow a specific path, longer trails that have weaker pheromones are abandoned in favor of shorter ones. (…)

Many computerized systems, such as those that route telephone calls through busy networks while minimizing connection times, already solve shortest path problems by deploying virtual ants that explore all possible routes in a system and deposit virtual pheromones on each route they travel.”

This technique however implies that when a new obstacle blocks a well traveled path they should turn around and go all the way back to their nest along the most traveled path, in order to start a new search.

The study reported in the Journal of Experimental Biology, shows that Argentine ants (Linepithema humile), do not just retrace their steps when presented with a barrier--as might be expected. Instead, the ants begin a localized search that seems to take into account the direction in which they were planning to go.

The discovery indicates that Argentine ants use more than just the simple trail pheromone to find their way. "The individual ants appear to have internal compasses and odometers that allow them to guide their search," says Chris Reid, a behavioral biologist at the University of Sydney in Australia, the lead author of the study.

David Broomhead, director of the Centre for Interdisciplinary Computational and Dynamical Analysis at the University of Manchester, UK, adds that "it would be really interesting to see if we can get a computer to do what these ants are doing."

Hat tip: Big Think.

No comments: