by Peter W McOwan and Paul Curzon, Queen Mary University of London
(Updated from the archive)
Ants communicate by leaving trails of chemicals that other ants can follow to sources of food they’ve found. Very quickly after a new source of food is found ants from the nest are following the shortest path to get to it, even if the original ant trail was not that direct and wiggled around. How do they do that? And how come computers are copying them?
Bongo playing physicist, Richard Feynman, better known for his Nobel Prize for Physics, wondered about this one day watching ants in his bath. The marvellous thing about science is it can be done anywhere! He grabbed some crayons and started marking the paths each ant followed by drawing a line behind it. He quickly discovered from the trails that what was happening was that each ant was following earlier trails but hurriedly so not sticking to it exactly. Instead it was leaving its own trail. As this was done over and over again the smooth direct route emerged as having the strongest line from the superimposed hurried trails. It’s a bit like when you sketch – you do a series of rough lines to start, but as you do that over and over the final line is much smoother.
From very simple behaviour the ants are able to achieve complex things that might otherwise need complex geometrical skills. As a result, Computer Scientists have been inspired by the ants. Marco Dorigo, Université Libre de Bruxelles first came up with the idea of ‘ant algorithms’: ways of programming separate software agents to do complex things that otherwise would bog down even fast computers. They are part of a more general idea of swarm computing. Finding shortest routes, whether for taxi drivers or for messages sent over networks, is a very common problem of the kind ant algorithms can solve. An ant algorithm solution involves programming lots of software agents to behave a bit like ants leaving digital trails for other agents to pick up. Over time, their simple individual behaviour yields a good solution to the otherwise complex problem of finding the shortest route. Another use is to detect the edges of objects in images – the first step in understanding a picture. Here the virtual ants wander from pixel to pixel based on the differences between nearby pixels, with the result that the strongest trail is left along edges of things shown in the image.
So ants are helping to solve real problems. Not bad for such a tiny brain.
More on …
Related Magazines …
- Issue 4 – Computer Science and Biolife
- Issue 28 – Cunning Computational Contraptions
- Biology loves technology
EPSRC supports this blog through research grant EP/W033615/1, and through EP/K040251/2 held by Professor Ursula Martin.
cs4fn 
3 thoughts on “Ant Track Algorithms”