News

Chris Reid shows that Argentine ants can solve Towers of Hanoi



9 December 2010

Already a trail along each of the two shortest routes (on the edge of the maze) has formed, connecting the nest (left hand side of the maze) with the food source (right had side of the maze). Some ants still explore the inner paths. Image credit: Chris Reid.
Already a trail along each of the two shortest routes (on the edge of the maze) has formed, connecting the nest (left hand side of the maze) with the food source (right had side of the maze). Some ants still explore the inner paths. Image credit: Chris Reid.

An ant colony is probably the last place you'd expect to find a maths whiz, but researchers Chris Reid and Associate Professor Madeleine Beekman have shown that the humble ant is not only capable of solving difficult mathematical problems, but is even able to do what few computer algorithms can - adapt the optimal solution to fit a changing problem.

Ten minutes after researchers block the shortest outer path and open up a bridge in the centre of the maze, ants start to make a path that extends their original by curving around the blockage. This new path, which is based on their original solution, is not the shortest route, thus is suboptimal. But there is starting to be the first traffic beginning to be redirected along new optimal path (upper) that traverses through the centre of the maze. Image credit: Chris Reid.
Ten minutes after researchers block the shortest outer path and open up a bridge in the centre of the maze, ants start to make a path that extends their original by curving around the blockage. This new path, which is based on their original solution, is not the shortest route, thus is suboptimal. But there is starting to be the first traffic beginning to be redirected along new optimal path (upper) that traverses through the centre of the maze. Image credit: Chris Reid.

These findings, published in the Journal of Experimental Biology, deepen our understanding of how even simple animals can overcome complex and dynamic problems in nature, and will help computer scientists develop even better software to solve logistical problems and maximise efficiency in many human industries.

An hour after the maze was altered, the only trail remaining lies along the new optimal path. Image credit: Chris Reid.
An hour after the maze was altered, the only trail remaining lies along the new optimal path. Image credit: Chris Reid.

Using a novel technique, PhD student Chris Reid and Associate Professor Beekman from the Behaviour and Genetics of Social Insects Laboratory, working with Professor David Sumpter of Uppsala University, Sweden, tested whether Argentine ants (Linepithema humile) could solve a dynamic optimisation problem by converting the classic Towers of Hanoi maths puzzle into a maze.

Finding the most efficient path through a busy network is a common challenge faced by delivery drivers, telephone routers and engineers. To solve these optimisation problems using software, computer scientists have often sought inspiration from ant colonies in nature - creating algorithms that simulate the behaviour of ants who find the most efficient routes from their nests to food sources by following each other's volatile pheromone trails. The most widely used of these ant-inspired algorithms is known as Ant Colony Optimisation (ACO).

"Although inspired by nature, these computer algorithms often do not represent the real world because they are static and designed to solve a single, unchanging problem," says lead author Chris Reid, who did the work as part of his PhD project.

"But nature is full of unpredictability and one solution does not fit all. So we turned to ants to see how well their problem solving skills respond to change. Are they fixed to a single solution or can they adapt?"

The researchers tested the ants using 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 since ants cannot move disks, the researchers 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 chose 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 ants were given one hour to solve the maze by creating a high traffic path between their nest and the food source, after which time the researchers blocked off paths and opened up new areas of the maze to test the ants' dynamic problem solving ability.

After an hour, the ants solved the Towers of Hanoi by finding the shortest path around the edge of the maze. But when that path was blocked off, the ants responded first by curving their original path around the obstacle and establishing a longer, suboptimal, route. But after a further hour, the ants had successfully resolved the maze by abandoning their suboptimal route and establishing a path that traversed through the centre of the maze on the new optimal route.

But not all the colonies' problem solving skills were equal: ants that were allowed to explore the maze without food for an hour prior to the test made fewer mistakes and were faster at resolving the maze compared to the ants that were naive. This result suggests that the "exploratory pheromone" laid down by ants searching a new territory is key in helping them adapt to changing conditions.

"Even simple mass-recruiting ants have much more complex and labile problem solving skills than we ever thought. Contrary to previous belief, the pheromone system of ants does not mean they get stuck in a particular path and can't adapt. Having at least two separate pheromones gives them much more flexibility and helps them to find good solutions in a changing environment. Discovering how ants are able to solve dynamic problems can provide new inspiration for optimisation algorithms, which in turn can lead to better problem-solving software and hence more efficiency for human industries."

Watch Chris Reid's research featured on Catalyst, ABC TV.

Chris R. Reid et al. (2010) Optimisation in a natural system: Argentine ants solve the Towers of Hanoi. Journal of Experimental Biology. 214.1.


Contact: Carla Avolio

Phone: 02 9351 4543

Email: 000918065517135d3c5b5d22303a0d20360429630b2b04420b13