Problem-solving Ants Inspire Next-gen Algorithms
|Argentine ant. Courtesy of Penarc|
An ant colony is probably the last place you’d expect to find a math whiz, but researchers 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. 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 maximize efficiency in many human industries.
Using a novel technique, Chris Reid and Associate Professor Madeleine Beekman from the University of Sydney School of Biological Sciences, working with Professor David Sumpter of Uppsala University, Sweden, tested whether Argentine ants (Linepithema humile) could solve a dynamic optimization problem by converting the classic Towers of Hanoi math 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 optimization problems using software, computer scientists often have sought inspiration from ant colonies in nature — creating algorithms that simulate the behavior 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 Optimization (ACO).
|The ants were able to find the shortest route from one end of the maze to the other in under an hour, then were able to adapt and find the second shortest route when obstacles were put in their path.|
“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, a doctoral student from the Behavior and Genetics of Social Insects Laboratory.
“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 optimization algorithms, which in turn can lead to better problem-solving software and, hence, more efficiency for human industries.”