Friday, August 17, 2007

For the love of ants

To be published next week, one book on my Amazon wishlist is titled The Ants Are My Friends. Students of popular music may recognise the phrase as one of the great misheard lyrics of our time, up there with "Beelzebub had a devil for a sideboard", rather than an expression of insect infatuation (the response being, of course, "blowing in the wind").

But I rather like the idea of ants being my friends. I've always held these misunderstood creatures in high regard, and was charmed by the story, recounted in Surely You're Joking, Mr. Feynman! (p. 91 in the Vintage edition), of how Richard Feynman investigated ant trail-following behaviour in his Princeton accomodation. He eventually used his findings to persuade an ant colony to leave his larder; "No poison, you gotta be humane to the ants!"

Anyone who has ever watched an ant colony at work cannot fail to be entranced by its beauty and efficiency. A single colony can strip an entire moose carcass in under two hours, and their work is coordinated in an inherently decentralised fashion (that is, there is no "head ant" giving out orders). An ant colony can be considered as a class of "super-organism", that is, a "virtual" organism made up of many other single organisms. Other examples include bacterial colonies and (arguably) the Earth itself.

Ants communicate remotely by way of pheromones, chemicals that generate some sort of response amongst members of the same species. When ants forage for food, they lay a particular pheromone on the ground once they've found a source. When this signal is detected by other ants, they follow the trail and reinforce it by laying pheromone themselves. Chemical signals also evaporate over time, which allows colonies to "forget" good solutions (i.e., paths) and construct new solutions if the environment changes (e.g., a stone falls onto an existing path).

By describing this mechanism in abstract terms, computer scientists have managed to harness the power of positive feedback in order to solve difficult computational problems. Perhaps the leading scientist in the field of ant colony optimization (ACO) is Marco Dorigo, and he has described how to use models of artificial ants to solve the problem of how to route text messages through a busy network of mobile base stations. We've also done some initial work on how ants build spatial structures, using an abstract model of pheromone deposition to explain how certain species can construct "bullseye"-like patterns of differently-sized objects.

Fundamentally, ongoing work in ACO reflects a wider interest in the notion of decentralised control. Rather than controlling everything from "on high" with global instructions, "bottom up" control emphasises the value of small, local interactions in keeping systems running smoothly. Software packages such as Netlogo have brought so-called agent-based modelling to a wider audience. I've just taken on a Ph.D. student to study the evacuation of tall buildings using this approach, and it's clear that, with ever-increasing computational power being available, the notion of simulating large systems of interacting entities will gain increasing influence.

No comments: