Ants lay trail to complex problem-solving.

http://www.abc.net.au/science/articles/2010/12/09/3089168.htm



Ants lay trail to complex problem-solving

Thursday, 9 December 2010 Carl Holm
ABC



Ant algorithms A species of ant could lend important clues to solving problems in telephone networks, traffic circulation and computer networks.

An international team of scientists, who have been studying the way ants navigate, found ants are better problem solvers than had previously been thought.

Their research, published today in the Journal of Experimental Biology, suggets problem-solving in natural systems is a rich source of inspiration for computer scientists.
Towers of Hanoi

In the study, Argentine ants were collected in the grounds of University of Sydney were introduced to a specially designed maze modelled on the 'Towers of Hanoi' puzzle.

The puzzle, also called 'Towers of Brahma', consists of three rods and a number of different-sized discs which have to be moved from one rod to the next without placing a larger disc on top of a smaller one. In legend, Brahmin priests are working to solve such a puzzle comprising 64 discs. When the puzzle is complete, the legend says, the world will end.

The rules for solving the problem with the minimum number of steps is called an algorithm.

Lead author Chris Reid, a PhD candidate at the University of Sydney, says that the best known nature inspired algorithm of this type is 'ant colony optimisation'. This involves finding the optimal path based on the behaviour of foraging ants.

Because the pheromones that ants use to mark their pathways are volatile and gradually evaporate, over time the colony selects the shortest path so that the signal remains stronger for longer.

The researchers say that most nature-inspired algorithms take only superficial inspiration from nature, and little is known about how real biological systems solve difficult problems.
When virtual ants get loopy

Data packets find their way through a computer network in a similar way to foraging ants. They map the most efficient route they can find between two points, leaving a trail of code behind as a 'virtual pheromone trail'.

These have a 'virtual evaporation rate' which results in less used paths eventually being abandoned as the data follows the best marked pathway. In spite of this similarity to foraging ants, those paths are not always the shortest between two points.

Professor David Sumpter at Uppsala University in Sweden, a co-author on the paper, says when ant algorithms were first proposed it was thought that they needed added bits of human ingenuity to get them to solve really complex problems.

"For example," he says, "the original ant algorithms would lead to virtual ants getting stuck in loops when faced with complex mazes. We now see that the ants can avoid loops."

To better understand how ants avoid these loops, the researchers looked at how they solved the Tower of Hanoi puzzle.

In some of the experiments, a small number of ants were allowed to explore a diamond-shaped maze, made up of 64 hexagons, for two hours, without a food source being present.

Reid says that a food source was then introduced and the colony was allowed in. He says that the ants were able to find the optimal route much quicker than in experiments where they were introduced without the exploratory scouts going first.

The maze was then altered, interrupting the well established trails. After a short period exploring new pathways, the ants again found the shortest route available.

"The ants didn't become locked into a redundant trail," Reid says, "and were able to to switch from a strong trail onto new ones that were more efficient."

"We don't really know how natural systems solve these kinds of dynamic problems," he says. "They're the ones that are most commonly seen in nature and they're also the ones that are the most difficult for us to solve in our everyday lives."

"They're the things we have to look at if we want to improve our own algorithms." Tweet