Ants can behave in ways we tend to regard as uniquely human. Some species cultivate fungi, while others manage flocks of aphids, guarding them from predators and ‘milking’ them for sugar-rich honeydew. Ants can also engage in behaviour which is about as alien to humans as you can get; Honeypot ants routinely overfeed some workers (replete workers), making them grow in size until they become so swollen with food that they can no longer move. These are then used as a living food storage for the colony over winter. But I bet not many people know that ants can be used to help deliver internet messages…
Some ants are solitary, while others are highly social – living in huge colonies with millions of other ants. Social ants share resources and information, cooperating to achieve feats which would otherwise be impossible. Some species do not have permanent nests and are continuously on the move looking for new sources of food, while others engage in behaviour known as polydomy in which multiple nests share workers and resources. The most impressive example of polydomy that I’ve found is the super-colonies established by invasive Argentine ants, which can span continents!
Ants are well known for being good engineers, building wind-powered ventilation tunnels to remove carbon dioxide, bridges and even living rafts (see video below). But besides engineering, ants are also great collaborators – they’re so small that they have to co-operate to get anything done! Incredibly, social ants work together without centralised control. There is no de-facto leader or organiser telling individuals what to do (not even the queen). Somehow they manage to efficiently forage for food, guide others to good food sources, swarm to protect their colony from predators, and can even coordinate raids against other nests! Ants engage in such a wide range of coordinated behaviour that even the problem of allocating tasks isn’t a trivial one. Solving these problems requires communication.
The problem with all this co-operation and communication is that single ants really aren’t very intelligent (they are certainly less intelligent than this dinosaur was). One method ants use to get around this is by communicating with chemical pheromones. The use of pheromones allows ants to follow simple rules; as they encounter particular pheromones in their day-to-day anty lives, they change their behaviour accordingly. Some pheromones are associated with food sources, so when a worker ant is looking for food it will go toward a high concentration of these chemicals. When she finds food, she’ll deposit more pheromone, letting others know where food is. This is a type of indirect communication called stigmergic communication, where individuals communicate by altering their environment.
This stigmergy is a great communication strategy for ants, because it means the colony’s knowledge is stored in their environment, and each ant doesn’t have to actually remember everything! All they need to know is; if I find food, release this pheromone. If I’m looking for food, go to where this pheromone is strongest. It sounds simple, but this basic principle can be really powerful.
Finding the shortest path
Don’t worry, we’re close to the bit about internet ants now, I got a little sidetracked… Scientists noticed that ants are able to reliably identify the shortest path between food and their nest. They tested this by putting ants in mini mazes called binary bridges, and seeing which path they took. The binary bridges contain two paths of different lengths between a single food source and the nest. Initially ants took fairly random paths to get between the food and nest. However over time, nearly all the ants converged to use the shortest path. This behaviour can be explained by stigmergic communication using pheromones:
- If an ant finds a food source it returns to the nest following the same path and laying down a pheromone trail.
- Other ants encountering a pheromone trail begin to follow it. If they find food at the end they return, reinforcing the pheromone trail as they go.
- Longer paths take ants longer to travel down, so take longer to be reinforced. Shorter paths are reinforced more quickly, and the pheromone trail grows in strength rapidly.
- Ants are more likely to follow stronger pheromone trails, and on their way back continue to reinforce it. This positive reinforcement leads to the pheromone trails on shorter paths becoming stronger, making it more and more likely that ants choose the path.
- Pheromone trails slowly evaporate, so only those which get reinforced survive in the long term, leading to all the ants following the shortest path!
What does this have to do with the internet?
A PhD student called Marco Dorigo realised that the method ants were using to find the shortest path to food could be adapted to solve other problems. In mathematics there are all sorts of scenarios where you might want to find the shortest (or least expensive) path to something. One example is the travelling salesman problem, which involves a hypothetical salesman. He needs to plan a tour of a number of cities, that allows him to visit each city once in the most efficient way. The overall distance travelled is determined by the order he visits cities in. In the picture below, the tour shown by green arrows leads to a much shorter tour than the one shown in blue. If there are only a small number of cities in the tour, it’s not too tricky to solve, but these sort of problems get exponentially harder as they grow in size.
Dorigo designed a type of computer algorithm called ‘ant colony optimisation’ (ACO), which uses artificial ants to solve problems like these. The virtual ants would initially walk between nodes (cities) making random tours. Once an ant has completed a tour it retraces its steps and deposits pheromone as it goes. The amount of pheromone deposited is inversely proportional to the distance of the path, meaning shorter paths get more pheromone than longer ones. Pheromone ‘evaporates’, and while ants make decisions randomly they are more likely to choose paths with higher pheromone concentrations. This leads to the same sort of positive reinforcement seen in real ant path finding. It turns out, while the ants do not always find the absolute best tour, they tend to find very good tours, very quickly!
Ants and the internet
So, we have a new way to solve a hypothetical question posed by a fictitious businessman… Great. Now what? Well, the virtual ants don’t have to travel between virtual cities. They can travel between anything, including real computers in a computer network. A big problem with large computer networks (like the internet) is finding efficient routes to send messages between computers. Internet messages usually have to hop between lots of intermediate points before they can get to their destination. Sounds a little like our travelling salesman problem!
But the internet is always changing. Computers are joining and leaving all the time, and paths become unavailable or congested. Real ants are very good at adapting their route if part of it becomes blocked. This is partly because the pheromone is always evaporating, and there are always a few ants which decide to go against the flow and explore new routes. So if another path becomes the quickest, the ants are able to adapt their route. ACO algorithms inherit this adaptability, making them potentially useful for things like finding paths which avoid internet congestion.
Virtual ants can travel between more abstract things too. If you have a problem which involves combining lots of smaller parts and assigning a cost (like the total distance) to the whole solution, it too could be solved with swarms of virtual ants! They’ve been used in quite a range of areas too, including improving the efficiency of car assembly lines, generating timetables, data-mining and vehicles route finding.
Sadly, I couldn’t find definitive proof that any of the big telecommunication companies are actually using ant based techniques to run their services. It may be that they don’t like to make their routing algorithms public, perhaps I just wasn’t looking hard enough, or maybe they don’t actually use them. Either way, ants have inspired an interesting approach to solving all kinds of problems. If anyone knows of any examples of ACO being used in industry, especially telecommunications, I’d be interested to hear about it (so please leave a comment!) And if you made it this far, well done on humouring me to the end. I hope that you now share at least some of my enthusiasm for ants.
References and interesting links
- Ants behaving (sort of) like fluids (video):
- Feeding ants brightly coloured liquid to create multi-coloured ants!
- Swimming ants (David Attenborough video clip).
- BBC article about Argentine Ants super-sized colonies: http://news.bbc.co.uk/earth/hi/earth_news/newsid_8127000/8127519.stm
- For more information on stigmergy, I’m told you can find the original 1959 paper which introduces the concept here. Unfortunately I can’t read it because it’s in French.
- Debout, G., Schatz, B., Elias, M., & McKey, D. (2007). Polydomy in ants: what we know, what we think we know, and what remains to be done. Biological Journal of the Linnean Society, 90(2), 319-348.
- Conway, J. R. (1990). Notes on repletes, myrmecophiles, and predators of honey ant nests (Myrmecocystus mexicanus)(Hymenoptera: Formicidae) in Arizona. Journal of the New York Entomological Society, 103-107.
- Kleineidam, C., Ernst, R., & Roces, F. (2001). Wind-induced ventilation of the giant nests of the leaf-cutting ant Atta vollenweideri. Naturwissenschaften, 88(7), 301-305.
- Kleineidam, C., & Roces, F. (2000). Carbon dioxide concentrations and nest ventilation in nests of the leaf-cutting ant Atta vollenweideri. Insectes sociaux, 47(3), 241-248.
- Buschinger, A. (2009). Social parasitism among ants: a review (Hymenoptera: Formicidae). Myrmecological News, 12, 219-235.
- Goss, S., Aron, S., Deneubourg, J. L., & Pasteels, J. M. (1989). Self-organized shortcuts in the Argentine ant. Naturwissenschaften, 76(12), 579-581.
- Bonabeau, E., Henaux, F., Guérin, S., Snyers, D., Kuntz, P., & Theraulaz, G. (1998). Routing in telecommunications networks with ant-like agents. In Intelligent Agents for Telecommunication Applications (pp. 60-71). Springer Berlin Heidelberg.
- Gagné, C., Gravel, M., & Price, W. L. (2006). Solving real car sequencing problems with ant colony optimization. European Journal of Operational Research, 174(3), 1427-1448.
- Bell, J. E., & McMullen, P. R. (2004). Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 18(1), 41-48.