Decoding the Remarkable Algorithms of Ants
Ants are capable of remarkable feats of coordination. They can forge complex paths through the jungle, build sophisticated structures, and adapt foraging patterns to fit their environment, all without orders from a centralized source. Deborah Gordon, a biologist at Stanford University, hopes to uncover the simple rules that produce complex patterns from simple individual actions.
Ants in particular excel at collective search, automatically tailoring their search strategy to efficiently cover large areas of ground. Gordon has found parallels between the algorithms ant colonies use for foraging and the man-made ones that underlie the Internet. Given how long ants have been solving these kinds of problems, Gordon hopes that she will uncover new algorithms that will ultimately make large-scale computing networks cheaper and more efficient.
Quanta met with Gordon at a social insects conference in Cold Spring Harbor, N.Y., shortly before she left for a trip to Mexico to study routing algorithms in arboreal ants. An edited and condensed version of the conversation follows.
QUANTA MAGAZINE: How did you first become interested in ants?
DEBORAH GORDON: I was originally interested in developmental biology and understanding how an embryo develops without any central control. I was looking for a system like an embryo, only one where I can see everything — it’s much easier for me to understand things I can see. I chose ants for that reason. Nowadays you can see a lot in a developing embryo. But that wasn’t true when I was starting out.
You’ve been studying the same ant colonies in Arizona for 30 years. Was that your intention from the start?
No. When I first started out, I was interested in variation among colonies, so I marked colonies so as to know when I was looking at the same one the following year. I noticed that some colonies got bigger from year to year, so I learned how a colony grows. At that point, no one knew how long a harvester ant colony could live. I went back to check the colonies every year — five years passed, then ten. Then I had no choice but to continue.
What has most impressed you about ants?
I’m impressed by the contrast between the coordinated responses of colonies and the ineffective and incomplete actions of individual ants. In other words, colonies accomplish a lot, but no ant is very competent on its own.
For example, ants are really good at collective search; a group of ants can cover the search area thoroughly without any central control. They do it through simple interactions, just touching antennae. When many ants are in a small space, they meet often and tend to take a convoluted path that keeps them stuck in one place. When few ants are in a large space, they don’t meet that often. They stretch out their paths and cover more ground.
For harvester ants, we’ve learned that an ant decides whether to go out of the nest and forage using the rate at which it meets ants coming in with food. It’s a form of positive feedback; the faster ants are coming in with food, the more ants go out. Each ant decides only when its rate of interaction is high enough to go out. Overall this system allows the colony to regulate foraging activity so that the ants don’t go out unless there’s enough food to make it worthwhile.
You called the harvester ant algorithm the “anternet.” Why?
I worked with Balaji Prabhakar, a colleague at Stanford, to figure out the algorithm that the harvester ants are using to regulate foraging. He pointed out that the algorithm is similar to the Transmission Control Protocol, which regulates data traffic on the Internet to make sure that data don’t go out unless there’s enough bandwidth. Both systems use simple, local feedback to regulate activity. I think we might be able to find other algorithms that ants use to solve engineering problems that we haven’t thought of yet. I am interested in the idea that evolution might produce different algorithms in different systems to solve the same problems.
But for evolution to produce algorithms that help the colony, evolution must work at the level of groups, not just individuals.
From the perspective of evolution, the colony is really the individual, because it is the colony that reproduces. Ants don’t make more ants, colonies make more colonies. So if we think about how ant behavior evolves, we have to look at colonies.
How do decisions made by individual ants alter the behavior of the colony as a whole?
In the desert, water is an important constraint. Ants lose water just being outside and meandering around. But they get their water from the seeds they eat, so they have to spend water to get water. No individual ant is making the decision to save water and stay home. But small differences in how ants respond to interactions can add up to big differences in how colonies forage, which in turn affects how many offspring colonies have. We found that natural selection favors the colonies that conserve water. I call it “the rewards of restraint.” I think this is the first study that’s been able to track the evolution of collective behavior in a natural population of animals. A simple, local behavior — how ants respond when one meets another — is being selected for because of the outcome for the whole colony.
Has evolution produced any other algorithms?
I’m working with another computer scientist on the routing networks that ants use. Arboreal ant species in Mexico follow very complicated paths through the tangle of trees and vines and other vegetation that connects nests and food sources. The trails break all the time, for instance when a twig snaps or an animal crosses the path. But the highway is easily repaired. How do they find a new route so quickly — on the scale of minutes — when there are so many different choices? We think they use a strategy that doesn’t take the shortest route but reestablishes the path very quickly and keeps the flow going. In some ways they have sacrificed what we think of as efficiency for resiliency. We think we have a model that makes sense, and we are testing it in field work.
How might this be important in computing?
In computing, there’s a tradeoff between the amount of information available and the cost of keeping and organizing that information. We’re interested in ways ants have evolved to solve this basic problem.
In this case, we are interested in the analogy to routing algorithms in computer systems where the straightest or shortest path might require a lot of information. Say you’re driving somewhere unfamiliar, and the exit you want to take is blocked. You can find your way around if you have a map. But how would you do that without any information? Without an address?
Collective search faces a similar problem. In robotics, there’s now a lot of interest in using the cheapest robots that require as little information as possible and that work together. A system like this is more robust to failure. Rather than sending one really complex robot to explore Mars or to search a burning building, it makes sense to send a group of cheap robots that will still work as a group even if one malfunctions. There are probably many new algorithms that ants have evolved to solve problems like this that we haven’t thought of. What we need to do is go take a look.
How do ant colonies change over time?
I found that a harvester ant colony’s behavior changes as it gets older and larger. Some aspects of network behavior just depend on size. In harvester ants, individual worker ants (other than the queen) live only a year, so it’s not the ants that get older and wiser, it’s the colony. That’s a puzzle, and it got me thinking about interaction networks, because I was looking for something that the ants could do in the same way but would have a different outcome if there are more ants. For example, I’m an ant, and I follow a rule that says, if I meet another ant at a certain rate, I do x. In a large colony, I might meet more ants. The same rule might have a different outcome if the colony is bigger because the rate of interaction would change.
We’re surrounded by giant networks — the Internet, our brains — so that got me interested in other systems. How does the behavior of a network scale as it gets larger?
How does it scale?
Older ant colonies are much more stable than young ones. If you create a disturbance, such as making a mess for them to clean up — I put out little piles of toothpicks — the older colonies eventually ignore the mess and get back to foraging. I think that in these colonies, with large numbers of foragers, the processes that drive them to forage override the response to the mess.
You’re also exploring how ants resemble neurons.
An ant adds up its recent interactions to decide what to do. A neuron adds up its recent stimulation from other neurons to decide whether to fire. Neuroscience already has a sophisticated modeling framework for understanding how that kind of system works. I am working with theoretical neuroscientists to apply this framework to ants.
You’ve launched a citizen science project to encourage the public to study different kinds of ants. What’s the benefit of studying new ant species?
Only 50 of the roughly 14,000 species of ants have ever been studied. It’s likely that if we study new species, we will uncover new algorithms. We developed a small kit for students to see how different species of ants do collective search. If kids try this with different species, they will probably make discoveries about species that no one has ever looked at.
This article was reprinted on ScientificAmerican.com.