Credit: Malcolm Ricketts
With a rudimentary brain and no memory, individual ants aren’t particularly clever, but in groups they've shown the ability to solve complex problems.
Now as researchers gain a deeper understanding of the processes used by these tiny insects, programming engineers are taking notice, using them as inspiration for computer algorithms.
Chris Reid, a PhD student at the University of Sydney, shows me a photo of a diamond-shaped maze full of Y-shaped branching paths. It’s a spatial map of all possible solutions to an ancient toy puzzle, the Towers of Hanoi (see box at the end of the article).
A faint dotted trail of Argentine ants (Linepithema humile) traces the shortest path from one end of the maze to food at the other end. By finding the shortest path, the ants had solved the toy puzzle in the fewest possible moves.
I’m impressed, but Reid seems rather unsurprised by the ants’ feat. “Ants are particularly good problem solvers because of the pheromone system they use for navigation,” he explains.
As ants initially explore a new area they leave trails of pheromones, volatile chemicals that mark paths for other ants to follow. At first the ants create many trails through the maze, but over time the ants refine their routes via a pruning process.
“Less optimal trails are pruned away as the pheromone evaporates quickly on the longer, less-used paths,” says Reid, who published his findings in the Journal of Experimental Biology. Those paths that are maintained are the shortest path connections, where the pheromone trail is constantly reinforced by high levels of ant traffic.
The same pheromone system allows Argentine ants to construct minimum-distance networks between nest sites. In the wild, these trail networks allow colonies to quickly recruit large numbers of ants to travel to food sources and defend nests from predators.
“Argentine ants end up forming massive supercolonies containing hundreds or thousands of nests connected to each other by trails. There’s a colony in Europe that spans over 6,000 km!” explains Tanya Latty from the University of Sydney, who published her study in the Journal of the Royal Society this year.
“An individual ant has no idea where it’s going," she says. "They don’t know that they are constructing an optimal route or network. These networks are just an emergent property of all these individuals following what are probably really simple behaviour rules.”
“The ants need to solve the same problems that a transport engineer might face. “How can I connect all of these separate points using the minimum length of trail or road and minimum resources, but still achieve a network that is robust and that isn’t going to crash and become disconnected?” It’s interesting to see how natural systems solve the same problem, given that there is no centralised control,” says Latty.
It’s not just ants that are clever at solving mazes and forming efficient networks. When challenged with the same problems to solve, slime moulds and vascular networks use the same pruning mechanisms, producing almost identical network patterns to the ants.
“A slime mould is a giant amoeba,” Latty tells me. “They look like bits of goo really, but they can grow to be metres wide.”
She then shows me what looks like a scene out of a horror movie, a time lapse video of a slime mould engulfing some mushrooms, which shrivel up as the mould seems to suck the life out of them.
In the lab, the slime mould looks a little more reserved, a motionless yellow branching network, tendrils extended to feed on scattered pieces of oatmeal.
The problem-solving abilities of natural systems have already been used to design new technologies to manage transport through all kinds of networks.
Ant behaviour forms the basis for ant colony optimisation (ACO) algorithms, which are used to optimise telephone networks, vehicle traffic routing and computer networks. Another example is artificial neural networks, which mimic the way neural pathways in the brain become stronger the more they are used.
“Data packets are like ants in that they cannot individually decide the best route to take through a network,” explains Reid.
Like the Argentine ants, data packets leave a virtual pheromone in the form of code, which coaxes other data along the more efficient paths until an optimal route is reinforced. Other algorithms are based on the behaviour of slime moulds and swarms of honey bees.
Blockages in a network, such as an outage in a telecommunications node or a traffic accident on a major road, create a changing problem for algorithms to solve. While some nature-inspired algorithms, such as neural networks and genetic algorithms, are routinely applied to dynamic problems, ACO algorithms don’t deal well with change.
Computer scientists, such as associate professor Bernd Meyer from the Faculty of Information Technology at Monash University in Melbourne, are working together with biologists to study ant behaviour and improve ACO algorithms. “The capability of ant colonies to function in dynamic environments is not yet well understood but we’re working on it,” explains Meyer.
But conditions are never static in nature, so how do ants cope with change? “We originally thought that Argentine ants use only a single pheromone, which would make it difficult for them to reroute their trails when conditions changed,” says Reid.
Reid discovered that the Argentine ants actually cope well with change and quickly find an alternative optimal route when their initial path through the maze is blocked.
It is likely that Argentine ants are using a second exploratory pheromone to help them find alternative trails when conditions change.
Meyer’s research group recently discovered that it might be the mistakes that ants make that are important in how they solve changing problems.
“Noisy or imperfect communication between colony members is a crucial ingredient that enables ant colonies to make decisions in dynamic environments,” explains Meyer. “The function of multiple pheromones is also another important piece of the puzzle”.
While Meyer advocates more collaboration between biologists and computer scientists, he warns that trying to make algorithms perfectly mimic biological systems is missing the point of algorithm design.
“What is necessary, though, is a better understanding of how the underlying biological systems function, and of their limitations,” says Meyer.
Reid predicts that using multiple code pheromones instead of a single pheromone will improve how ACO algorithms optimise dynamic and changing networks.
With ants and slime moulds behaviour continuing to inspire new-age computing technology, here’s hoping that they can figure out a way to speed up my Internet connection.
THE TOWERS OF HANOI
The Towers of Hanoi consists of three vertical rods and a pyramid of different-sized discs. By moving the discs between rods, the player must reconstruct the pyramid on a different rod, moving only one disc at a time without placing a larger disc on top of a smaller one.
Legend has it that Brahmin priests are working on a 64-disc version of the puzzle. When they have solved the puzzle, the legend says that the world will end.
Chris Reid’s Argentine ants solved a 3-disc version of the puzzle. Because ants can’t move discs, Reid used a maze to model the possible moves of the puzzle. The ants enter the maze at the left vertex of the diamond and make their way to the food at the opposite end.
Bridget Murphy is a science writer in Sydney and is studying for a PhD in biology.
