Steiner tree problem http://en.wikipedia.org/wiki/Steiner_tree_problem

Ants model a Steiner minimum tree. Credit: Tanya Latty et al

Steiner minimum tree with an extra edge. Credit: Tanya Latty et al.

Supercolony trails follow mathematical Steiner tree.
By Liz Tay on Feb 18, 2011 7:08 AM

An interdisciplinary study of ant colonies that live in several, connected nests has revealed a natural tendency toward networks that require the minimum amount of trail.

Researchers studied ‘supercolonies’ of Argentine ants with 500, 1000 or 2000 workers to identify methods for self-organising sensors, robots, computers, and autonomous cars.

They put three or four nests of ants in empty, one-metre-wide circular arenas to observe how they went about connecting the nests.

As with railway networks, directly connecting each nest to every other nest would allow individual ants to travel most efficiently, but required a large amount of trail to be established.

Instead, the ants used central hubs in their networks – an arguably complex design for creatures that University of Sydney biologist Tanya Latty described as having “tiny brains and simple behaviours”.

“We found that ants almost always made networks that minimised the total amount of trail, consistent with optimisation at a colony level, rather than at an individual level,” Latty told iTnews.

“In many cases, they did a remarkable job of making networks that looked almost exactly like the mathematical shortest path, called a ‘Steiner tree’.”

Argentine ants form trails by tapping the ground with their abdomens to leave behind trails of pheromones that attract other ants.

Because pheromones evaporate over time, trails have a “maintenance cost” of worker ants that continuously march along the trail to lay down pheromones.

Kai Ramsch and Martin Middendorf of the University of Leipzig’s Parallel Computing and Complex Systems Group hoped to apply the ants’ networking methods to organic computing systems.

“Clearly, in order to work together the components of an organic computing system need to be connected,” said Ramsch and Middendorf, who collaborated with Latty for the study.

“Hence, a central question is: How can many components be connected by a network that is formed by the components themselves in a self-organized way?”

In a separate study of Argentine ants last year, University of Sydney biologist Chris 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.

The German computer scientists noted that the digital “evaporation rate” of artificial pheromones would be varied according to speed, distance, number of information packets and network structure of a computer network.

“It is necessary to change the evaporation rate for the artificial pheromones so that they fit to application,” they told iTnews in an e-mail exchange. “This can be simulated with our models.”

A network in four hours

The team found that ant colonies completed the majority of network formation within their first two hours in the arena.

Each experiment lasted a total of six hours, although very few topological changes were observed after four hours.

Latty said she initially suspected that the ants were building low-maintenance networks because they had too few resources to directly connect each nest.

That theory was deemed unlikely, when the researchers found larger supercolonies dedicated their additional resources to building paths that essentially improved the robustness of the network.

The researchers hoped that their study of ant colonies would also yield “self-healing” organic computing networks, since nodes were controlled individually and not by a central control unit.

Copyright © iTnews.com.au . All rights reserved.