An algorithm that explains how ants create and repair trail networks

Deborah Gordon, professor of biology at Stanford University, set out to answer this and many other questions when she began studying these ants in 2011. Peering into the trees -- sometimes from atop a ladder -- Gordon spent hours recording which junctions the ants choose.

Gordon's work, published online Sept. 29 by American Naturalist, has led to the development of a simple algorithm that explains how ants create, repair and prune a network within a complex maze of vegetation. This algorithm could explain other biological processes or provide engineering solutions.

An ant algorithm

The ants Gordon studied never leave their forest canopy, moving instead through a tangle of vines, bushes and trees along a circuit of trails that link many nests and food sources. Because these food sources come and go, nests disappear and branches break, the circuit changes slightly from day to day.

Gordon mapped these complex trails and set up experiments to study how the ants responded when new food appeared or branches broke. Along with Arjun Chandrasekhar and Saket Navlakha of the Salk Institute of Biological Studies at the University of California, San Diego, Gordon analyzed the resulting data to model how the ants repair and prune their trail network.

"At every node, ants could get lost if others have not been there recently enough to leave a chemical trail," said Gordon. "So there is an ongoing process that creates not the network with the shortest path, but the network with the fewest junctions where ants have to make a decision and could make the wrong one. It seems that evolution has favored keeping the ants together on the same network, rather than saving them effort in how far they have to walk."

Ants of C. goniodontus choose which route to take at a junction by following pheromone laid by the ants that recently crossed that junction. The pheromone evaporates, so the path that recently had the most ants is the most attractive one. By marking the ants with nail polish, Gordon found that the same ants tend to go along the same trails from a nest.

But if a trail gets broken, the ants have a simple plan to reconnect with the trail network. They use what's known as "greedy search," working around the rupture in the path by moving back to the nearest junction and choosing a new path from that point.

"Even if there is what looks to us like a neater solution available by going back a few nodes, they never use that," said Gordon. "They always go right back to the node nearest the break and go from there to the nearest node, and so on. Because the vegetation is so tangled, they are able to find a way to the other side of the break."

As often happens in science, algorithms can offer nature-inspired solutions to engineered problems, leading to robust and elegant fixes. The algorithms that produce and repair natural networks, like the network of neurons and their synapses in the brain, help us to design and navigate many kinds of engineered networks, such as Facebook or subway systems. This algorithm, created by turtle ants in the tropical canopy, is another example of an excellent evolved solution, Gordon said.