Argentine ants solve the Towers of Hanoi problem

It was always assumed that Argentine ants, as for all species of ants that lead nest mates to food sources via a pheromone trail, were incapable of adapting to dynamic changes in their foraging environment. Supposedly, individual ants follow a few simple rules when searching for food. After finding a food source that is of high enough quality, they mark the route between the nest and the food source with pheromone. In the presence of a pheromone trail, the ants simply follow it towards the pot of gold and reinforce the trail. Mathematical models have suggested that these simple rules often cause the ants to follow an existing trail even when a food source of better quality becomes available or a short cut can be found. Yet, ants live in an environment in which food sources come and go. Are they really so dumb?

HFSP Program Grant holders Madeleine Beekman and David Sumpter and colleagues
authored on Thu, 16 December 2010

As part of our HFSP funded project ‘Optimization in natural systems: ants, bees and slime moulds’ we set out to investigate the ability of Argentine ants to adapt to dynamic changes in their foraging environment. We tested the ants by asking them to solve the three-rod, three-disk version of the Towers of Hanoi problem - a toy puzzle that requires players to move disks between rods while obeying certain rules and using the fewest possible moves. But because ants cannot move disks, we converted the puzzle into a maze where the shortest path corresponds to the solution with fewest moves in the toy puzzle. The ants at the entry point of the maze could choose between 32,768 possible paths to get to the food source on the other side, with only two of the paths being the shortest path and thus the optimal solution. The result was exactly as predicted: the ants quickly established pheromone trails along the shortest path. But then we blocked the shortest paths, thus forcing the ants to find an alternative solution. As explained above, conventional wisdom dictates that the ants would not be able to adapt and would continue following their original trail that now leads nowhere.
 
Contrary to predictions, Argentine ants rapidly found the alternative shortest path, showing that they have the ability to adapt to sudden changes in their environment. But the speed with which they adapt depends on whether or not they had prior experience with the maze: colonies that had explored the maze hours before food was introduced, found the alternative solution quicker than colonies without such pre-exposure. This is a puzzling result, as the time between exploring the maze and the need to find an alternative solution when the original path is blocked, was at least 1 hour.
 
What mechanisms allow the ants to adapt so quickly? We think that the ants use different pheromones; one when exploring a new environment and one to lead nest mates to profitable food sources. The way these different pheromones are used probably depends on the context. We also suspect that individual ants are not as dumb as assumed and that they have an internal compass that tells them if they are going towards or away from the nest. Making use of the large range of expertise within our HFSP team, we are currently exploring our different hypotheses using computer simulations. Ultimately, we will not only understand better how colonies of ants navigate through a complex and dynamic environment but we also hope to provide new inspiration to computer scientists interested in using biological systems in the design of optimization algorithms. Follow the ant!

Fig. 1. (A) Graph of the possible moves in the Towers of Hanoi game with three disks and three rods. (B) Towers of Hanoi maze. (C) Modified Towers of Hanoi maze, configured after an hour of solving the original Towers of Hanoi formation. Dashed lines show the shortest routes between nest and food source. 
 


Fig. 2. Results for (A) 60 min, (B) 90 min and (C) 120 min, when exploration pheromone has previously been laid. At 60 and 120 min, the shortest paths in each configuration are in use, 90 min shows traffic at the intermediate stage. 

Reference:
Optimization in a natural system: Argentine ants solve the Towers of Hanoi. Reid CR, Sumpter DJT, Beekman M (2011). Journal of Experimental Biology 214:50-58 doi: 10.1242/jeb.048173.

Additional References:
Ant Strategies for Negotiating Obstacles by Kathryn Knight. Journal of Experimental Biology 214, iii (2011) doi: 10.1242/jeb.054171.


Pubmed link

University of Sydney link: Chris Reid shows that Argentine ants can solve Towers of Hanoi

Nature News: Ants lead way to speedier computer networks

ABC Science: Ants lay trail to complex problem-solving