Artificial ants solve network problems

Individually ants may be stupid, but they work together

By BBC News Online technology correspondent Mark Ward in Prague

Ants might be able to run telecommunication networks better than humans.

Researchers have found that control programs based on the foraging behaviour of ants can keep data networks running more efficiently and cope with congestion better than many human alternatives.

They believe that other computational problems could also be tackled using algorithms or techniques derived from the behaviour of ants.

Already some companies are using the ant systems to do a better job of managing delivery networks and supply chains.

Powerful together

Individually, ants may be stupid, but put enough of them together and they manage to build nests, grow fungus as food, farm other insects, and even weave their own shelters.

They were able to say to any packet of data with a given destination what is the next node it should travel to

Marco Dorigo

Marco Dorigo and colleagues at the Free University of Brussels are creating small, smart computer programs that mimic the behaviour of ants to find novel, efficient ways of tackling many tricky computational and organisational problems.

When ants forage, they randomly wander the forest or jungle floor and lay a trail for nest-mates to lead them to a source of food. Many individual ants may discover different routes to the same food but the shortest path that leads to it will have the strongest concentration of pheromone, a chemical indicator laid down by the ants.

It will swiftly become the most popular path because it is the smelliest and easiest for the ants to spot and track.

"What they find in the environment is determined by what's done previously by other members of their colony," said Professor Dorigo.

Artificial ants

To apply this neat organisational ability to data networks, Professor Dorigo and his colleagues have created artificial ants that can lay and sniff pheromone trails and can learn their way around a network.

The artificial ants were let loose on simulations of the US National Science Foundation network and the telecommunications network run by NTT in Japan.

At periodic intervals, artificial ants were let loose from each node on these networks and told to find a route to a given destination. By simply laying and smelling the strength of the pheromones along each potential path, the ants swiftly generated maps that showed the fastest route to any end point.

"They were able to say to any packet of data with a given destination what was the next node it should travel to," said Professor Dorigo.

When congestion was simulated on the artificial networks, the ants beat all the other popular routing systems in the speed with which they reconfigured the network to avoid the traffic jams.

Exceptional abilities

The artificial ants are also good at solving a version of a knotty computational problem known as the Travelling Salesman Problem, which involves finding the shortest route that takes in all destinations on a given map.

The ants have turned out to be exceptional at tackling a variant of this problem known the Sequential Ordering Problem (SOP), in which a number of locations have to be visited and goods either have to be dropped off or picked up.

Professor Dorigo applied ant-derived algorithms to 23 SOP problems and found that in 14 cases they produced the best solution ever, in a further six they did as well as the previous best and in a final three cases the results were well within acceptable limits.

A fuel firm on the Italian-Swiss border is using ant-derived algorithms to work out the best route for its drivers delivering supplies to petrol stations.