By Matt Kaplan
An analysis of how ants quickly find new routes in a changing maze reveals techniques that could be useful to systems engineers.
The research, 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. Because there are many network-management programs that mimic the search behavior of this ant species, systems engineers are taking notice and wondering what they can learn.
In the wild, ant scouts deposit pheromones along the trails between food and the nest. Nest mates to 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. These ants explore all possible routes in a system and deposit virtual pheromones on each route they travel.
Yet such systems are not perfect. When virtual ants are blocked from following a well-traveled path, they must turn around and are likely to follow the path that they have just traveled because it usually has the strongest concentration of pheromones of any nearby paths.
"I figured Argentine ants had to have some way of dealing with obstacles that didn't involve starting a search from scratch," says Chris Reid, a behavioral biologist at the University of Sydney in Australia, the lead author of the study.
To put the insects to the test, Reid and his colleagues presented them with a logic puzzle known as the Towers of Hanoi. The human version of the puzzle comprises three rods with a number of differently sized rings. The rings have to be stacked so that the smallest is on top and the largest on the bottom, without ever lifting more than one ring at a time or ever placing a larger ring on top of a smaller one.
Reid converted the various possibilities and dead ends presented by the Towers of Hanoi into a maze containing 32,768 possible paths leading from one end to the other. Like the Towers of Hanoi, which can be solved in many very time-consuming ways, the maze presented many long options, but like the Towers, it had two paths that were shorter than all of the others.
Blocking the path
The researchers worked with 12 colonies of Argentine ants and gave each an hour to find the food at the other end of the maze. By the end of the hour, about 83 percent of the colonies used at least one of the shortest paths. Then barriers were placed on the shortest paths and a new route was opened. By the end of another hour, almost 86 percent of the other colonies had established trails along the new shortest route.
"The discovery that these ants can solve the Towers or Hanoi is far from trivial," says Simon Robson, a biologist at James Cook University in Townsville, Australia.
Many ant species have pheromones for different situations. For those species to work their way around an altered maze would not come as a surprise. However, "Argentine ants were widely thought to have only one pheromone and not be capable of doing something like this", says Reid. Instead of following their pheromone trails back to their nests, the ants searched the local area around the blocked path.
"When I heard that these ants started exploring nearby routes rather than turning around, I just thought, this is dead cool," says David Broomhead, director of the Centre for Interdisciplinary Computational and Dynamical Analysis at the University of Manchester, UK.
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 Reid. Broomhead adds that "it would be really interesting to see if we can get a computer to do what these ants are doing."
Although practical application is still a way off, Reid's intention is to give virtual ants compasses and odometers to better work their way through networks when blockages form.