Computing with ants
COMPUTER SCIENTISTS are getting excited about bugs. Not the Y2K kind we've heard enough about that but insects. Swarm behaviour is providing new insights for solving difficult problems.
Biologists have long puzzled over how the individual actions of single creatures on the small scale can lead to complex group activity on the large scale. How is it that ants can discover the shortest paths from their colony to sources of food? The answer, first discovered by Jean-Louis Deneubourg of the Free University of Brussels, is that as they travel, the ants deposit chemicals called pheromones. These mark the trails which are later detected by other ants.
Imagine some ants whose colony is near a food source. Ants will start wandering off from the colony, leaving trails of pheromones as they explore. Some ants will find the food source, then return to the colony, following their own trails back. The route they took is now doubly saturated with pheromones. Other ants are attracted to the high concentration of pheromone and take the same route, which soon becomes the main route from colony to food. It's also the shortest, because those ants who discovered it will have got back soonest. The other routes gradually fade out, as their pheromone markers evaporate.
The relevance to computing lies in the problem of finding the shortest path between points a problem central to communications networks. Consider a travelling salesman, who has to visit a number of cities, passing through each city only once. With knowledge of only a few cities and their interconnections, it's not hard to solve the problem, but as the number of cities grows, the possibilities for travel become unimaginably huge. Researcher Marco Dorigo of the Free University of Brussels has used techniques based on ant behaviour to provide new, fast, solutions to the problem. He imagines ants travelling between the cities at random, depositing pheromone trails which slowly evaporate. By repeating this process many times, eventually the ants' favoured paths converge to a shortest-path solution.
Paul Kantor of Rutgers University is using a similar approach in a Web searching scheme he calls "Ant World". Kantor's idea is to make Web searching a cooperative process, by enabling searchers to draw on the results of others, and to add their own experience to a common pool of knowledge. Just as an ant marks its path with pheremones, the Web searcher is able to mark "information traces" along the links between Web pages. Kantor calls these traces "digital information pheromones". Because the links between Web sites don't have a physical reality, the digital pheromone traces are stored in a separate database. Ant World attaches itself to your browser (it currently only works with Netscape) and whenever you perform a web search, you're invited to submit comments about the suitability of the pages you've found. Your results are stored centrally on the Ant World server, which runs on a computer in Kantor's lab.
Ideas from ant behaviour are also being applied to robotics. IBM researcher Israel Wagner is using ant-based methods for controlling the behaviours of mobile robots. One application is to marshall the robots to cooperativly clean a room, and the same techniques are applicable to sweeping a minefield. Wanger has some nice java applets showing how his robots can behave. And at the University of Alberta, Ronald Kube is using swarm behaviour to make a group of robots work collectively to push an object towards a light source.
Swarming methods are also appearing in financial analysis, production line optimisation, and optical networks. Bugs, once the bane of programmers, suddenly have a lot to offer.
Toby Howard teaches at the University of Manchester.