Mimicking the behaviour of ants, bees and birds started as a poor man’s version of artificial intelligence. It may, though, be the key to the real thing ONE of the bugaboos that authors of science fiction sometimes use to scare their human readers is the idea that ants may develop intelligence and take over the Earth. The purposeful collective activity of ants and other social insects does, indeed, look intelligent on the surface. An illusion, presumably. But it might be a good enough illusion for computer scientists to exploit. The search for artificial intelligence modelled on human brains has been a dismal failure. AI based on ant behaviour, though, is having some success.
Ants first captured the attention of software engineers in the early 1990s. A single ant cannot do much on its own, but the colony as a whole solves complex problems such as building a sophisticated nest, maintaining it and filling it with food. That rang a bell with people like Marco Dorigo, who is now a researcher at the Free University of Brussels and was one of the founders of a field that has become known as swarm intelligence.
In particular, Dr Dorigo was interested to learn that ants are good at choosing the shortest possible route between a food source and their nest. This is reminiscent of a classic computational conundrum, the travelling-salesman problem. Given a list of cities and their distances apart, the salesman must find the shortest route needed to visit each city once. As the number of cities grows, the problem gets more complicated. A computer trying to solve it will take longer and longer, and suck in more and more processing power. The reason the travelling-salesman problem is so interesting is that many other complex problems, including designing silicon chips and assembling DNA sequences, ultimately come down to a modified version of it.
Ants solve their own version using chemical signals called pheromones. When an ant finds food, she takes it back to the nest, leaving behind a pheromone trail that will attract others. The more ants that follow the trail, the stronger it becomes. The pheromones evaporate quickly, however, so once all the food has been collected, the trail soon goes cold. Moreover, this rapid evaporation means long trails are less attractive than short ones, all else being equal. Pheromones thus amplify the limited intelligence of the individual ants into something more powerful.
In 1992 Dr Dorigo and his group began developing Ant Colony Optimisation (ACO), an algorithm that looks for solutions to a problem by simulating a group of ants wandering over an area and laying down pheromones. ACO proved good at solving travelling-salesman-type problems. Since then it has grown into a whole family of algorithms, which have been applied to many practical questions.
Its most successful application is in logistics. Migros, a Swiss supermarket chain, and Barilla, Italy’s leading pasta-maker, both manage their daily deliveries from central warehouses to local retailers using AntRoute. This is a piece of software developed by AntOptima, a spin-off from the Dalle Molle Institute for Artificial Intelligence in Lugano (IDSIA), one of Europe’s leading centres for swarm intelligence. Every morning the software’s “ants” calculate the best routes and delivery sequences, depending on the quantity of cargo, its destinations, delivery windows and available lorries. According to Luca Gambardella, the director of both IDSIA and AntOptima, it takes 15 minutes to produce a delivery plan for 1,200 trucks, even though the plan changes almost every day.
Ant-like algorithms have also been applied to the problem of routing information through communication networks. Dr Dorigo and Gianni Di Caro, another researcher at IDSIA, have developed AntNet, a routing protocol in which packets of information hop from node to node, leaving a trace that signals the “quality” of their trip as they do so. Other packets sniff the trails thus created and choose accordingly. In computer simulations and tests on small-scale networks, AntNet has been shown to outperform existing routing protocols.
It is better able to adapt to changed conditions (for example, increased traffic) and has a more robust resistance to node failures. According to Dr Di Caro, many large companies in the routing business have shown interest in AntNet, but using it would require the replacement of existing hardware, at huge cost. Ant routing looks promising, however, for ad hoc mobile networks like those used by the armed forces and civil-protection agencies.
Routing, of both bytes and lorries, is what mathematicians call a discrete problem, with a fixed, albeit large, number of solutions. For continuous problems, with a potentially infinite number of solutions—such as finding the best shape for an aeroplane wing—another type of swarm intelligence works better. Particle swarm optimisation (PSO), which was invented by James Kennedy and Russell Eberhart in the mid 1990s, is inspired more by birds than by insects.
When you place a bird feeder on your balcony, it may take some time for the first bird to find it, but from that moment many others will soon flock around. PSO algorithms try to recreate this effect. Artificial birds fly around randomly, but keep an eye on the others and always follow the one that is closest to “food”. There are now about 650 tested applications of PSO, ranging from image and video analysis to antenna design, from diagnostic systems in medicine to fault detection in industrial machines.
Digital ants and birds, then, are good at thinking up solutions to problems, but Dr Dorigo is now working on something that can act as well as think: robots. A swarm of small, cheap robots can achieve through co-operation the same results as individual big, expensive robots—and with more flexibility and robustness; if one robot goes down, the swarm keeps going. Later this summer, he will be ready to demonstrate his “Swarmanoid” project. This is based on three sorts of small, simple robot, each with a different function, that co-operate in exploring an environment. Eye-bots take a look around and locate interesting objects. Foot-bots then give hand-bots a ride to places identified by the eye-bots. The hand-bots pick up the objects of interest. And they all run home.
All this is done without any pre-existing plan or central co-ordination. It relies on interactions between individual robots. According to Dr Dorigo, bot-swarms like this could be used for surveillance and rescue—for example, locating survivors and retrieving valuable goods during a fire.
Swarmanoid robots may not much resemble the creatures that originally inspired the field, but insects continue to give programmers ideas. Dr Dorigo’s group has, for instance, developed a system to allow robots to detect when a swarm member is malfunctioning. This was inspired by the way some fireflies synchronise their light emissions so that entire trees flash on and off. The robots do the same, and if one light goes out of synch because of a malfunction the other bots can react quickly, either isolating the maverick so that it cannot cause trouble, or calling back to base to have it withdrawn.
All of which is encouraging. But anyone who is really interested in the question of artificial intelligence cannot help but go back to the human mind and wonder what is going on there—and there are those who think that, far from being an illusion of intelligence, what Dr Dorigo and his fellows have stumbled across may be a good analogue of the process that underlies the real thing.
For example, according to Vito Trianni of the Institute of Cognitive Sciences and Technologies, in Rome, the way bees select nesting sites is strikingly like what happens in the brain. Scout bees explore an area in search of suitable sites. When they discover a good location, they return to the nest and perform a waggle dance (similar to the one used to indicate patches of nectar-rich flowers) to recruit other scouts.
The higher the perceived quality of the site, the longer the dance and the stronger the recruitment, until enough scouts have been recruited and the rest of the swarm follows. Substitute nerve cells for bees and electric activity for waggle dances, and you have a good description of what happens when a stimulus produces a response in the brain.
Proponents of so-called swarm cognition, like Dr Trianni, think the brain might work like a swarm of nerve cells, with no top-down co-ordination. Even complex cognitive functions, such as abstract reasoning and consciousness, they suggest, might simply emerge from local interactions of nerve cells doing their waggle dances. Those who speak of intellectual buzz, then, might be using a metaphor which is more apt than they realise.
