Ants solve dynamic optimisation puzzle

An international study of how Argentine ants find their way through a changing maze could lead to more flexible computer algorithms, researchers say.

Biologist Chris Reid of the University of Sydney collected 60 ant colonies from university grounds, and forced them to navigate a diamond-shaped maze to reach a food source one metre away.

The Perspex maze was a graphical representation of a three-disc, three-rod version of the Towers of Hanoi puzzle, and allowed for 32,768 possible paths from one end to another.

All ant colonies were able to construct a trail between the nest and food source, with 93.3 percent of the colonies finding the shortest route within one hour.

Researchers then blocked off certain paths with a vertical plastic wall to find out how ants would adapt to a change in the maze.

Ants navigate around an obstruction, 80 minutes into the experiment.

Ants first used sideways corrective moves to bypass the block. Three-quarters of the colonies were then able to determine the next best route from the nest to the food source.

Colonies that had been allowed to explore the entire maze for more than two hours before the experiment performed better, with 93.3 percent finding the next best path when blocked.

Reid acknowledged that the three-disc, three-rod version of Towers of Hanoi was "easy for a computer to solve". More complicated versions of the puzzle were deemed too large and unwieldy for the experiment.

He hoped the findings, published this month in the Journal of Experimental Biology, would take nature-inspired computing in a new direction, revealing new ways to adapt an optimal solution for a changing problem.

"[Ant colony optimisation research] has gone further and further away from finding one algorithm that can solve lots of problems, or one problem that is constantly changing," he told iTnews.

Ants as virtual data packets

Ants establish optimal routes by leaving behind trails of pheromones that are attractive to other ants.

Because the pheromones evaporate over time, shorter, more well-travelled trails become increasingly attractive.

Reid speculated that ants and their pheromones could be modelled by data packets that left behind a line of code that expired after a set period of time.

Different lines of code with different "evaporation rates" could be used to model trail pheromones, and the exploration pheromones that were likely laid during the pre-exposure period, he said.

He expected more flexible, nature-inspired algorithms to improve logistical programs to maximise efficiency of industrial processes.

"Contrary to previous belief, the pheromone system of ants does not mean they get stuck in a particular path and can't adapt," Reid said.

"Having at least two separate pheromones gives them much more flexibility and helps them to find good solutions in a changing environment."

Computer scientist David Sumpter from the Uppsala University in Sweden was a co-author of the Argentine ant study. iTnews was unable to reach Sumpter for comment.