We call them social insects, but ants don’t communicate much. Despite a simplicity of language , they are able to solve problems in surprisingly efficient ways. Ants send out scouts to find food, eventually leaving trails for worker ants in the colony to follow. They can find the shortest possible route between food source and nest with ease. If the food source is too large for a single ant, a group can lift and carry it together, even navigating around obstacles that might fall in the way.
Scientists of many kinds are interested in just how ants do this. They want to know why it’s efficient, and how to keep it efficient with minimal data. If they can replicate how ants navigate in swarms, they can advance technologies in telecommunications traffic control and maybe even swarms of nanobots. In today’s post, we’ll consider the first of several tricks ant colonies possess: finding the shortest distance between two locations.
Tale as Old as Travel
In the 1800’s, two mathematicians considered the plight of a theoretical salesman. He must pass through all the major cities of some country, but he doesn’t want to waste time or money on the trips in between sales stops. What is the shortest path to take between all cities, without doubling back or repeating through any one city?
Turns out, the traveling salesman problem is a challenging problem to solve, with no general solution currently available. And yet, animals (and some non-animals) can do this well. Slime molds for example, have been put into petri dishes with food sources matching maps of major cities like Tokyo. Guess what? They can replicate – even improve on – our highways and transit systems. Ants will also determine the shortest possible route between its nest and some food source. They do this collectively, with nothing but pheromones – pheromones planted by ants taking any old route, whether it’s efficient or not. It’s a simple system, to be sure, but what makes it work so well?
To begin considering this problem, a group of researchers set up an elegant experiment to observe ant swarms. They placed an ant nest at the edge of a bridge. This bridge gave the ants a choice: turn to the left, or turn to the right. The left branch was much longer than the short branch, but they tested the branch in the dark just to make sure they couldn’t see if one was preferable. The bridge had two branches like this, with the second fork having a long and short route on opposite sides than the first. Finally, both paths converged to a food source.
They made the following hypotheses:
- As distances between short and long paths increase, ants will get better at picking the short path.
- If the long path is available first, and a short one only available later, the ants won’t be able to find the short path.
- If ants only leave a trail when they return from food to nest (and not in both directions), the colony will be unable to determine the shortest route.
Let’s assume that ants plant their trails with pheromones both when they leave the nest and when they return. Now, let’s follow Scout A and Scout B after they leave the nest in search of a meal. Scout A takes, by chance, the long path. It takes the wrong turn at both forks in the road, so it takes her a while to reach the food. Scout B, by a stroke of serendipity, chooses the shortest possible route, and is first to reach the food. Excited, both ants will, upon discovery, hurry back to the nest. As each ant hurries back, the pheromones double up on the path. Since the shortest traveling ant gets home first, ants leaving the nest will have a biased choice: take the once-scented long route, or the twice-scented short route. Guess which they’ll prefer? As ants continue making this (now biased) decision, the short route gets more and more pheromone. It’s a positive feedback loop. Without speaking (or dancing, like your friendly neighborhood bees), the ants have found the shortest distance.
Now it is clear why the second premise is true. If ants only have a long path available, it will receive all their pheromones. Add the short path later on, and there’s just no good reason, as far as the ants can tell, to travel down this new, unscented road.
Finally, the third premise is the trickiest. But if ants are only lying pheromone on their route on the way back, the doubling up discussed above doesn’t occur, and it’s that much more difficult to distinguish between the long and short paths. Spoiler alert: this premise was untested at the time of publication for this paper, and also, we know it to be false. There are ant species who only deposit pheromone on trails while travelling back from a food source, and they can still determine shortest routes.
The researchers were able to confirm the first two hypotheses, however. They checked them mathematically, and then they set up their experiments to compare the model with actual ant behavior.
It’s Good to be Random – But Not Too Random
You can model this sort of thing. The researchers had to translate all the ant travels into mathematical equations. That means a variable (a Greek letter, no doubt, because this is fancy math) for features like how many ants travel across the bridge per second, the concentration of pheromone on each branch, and the difference between the short and long paths. These variables are placed into equations, which can be used to run Monte Carlo simulations. Now, we have simulations predicting ant behavior. Will they hold up to the actual activity of the ants?
A Monte Carlo Simulation is a statistical tool that allows you to set a few variables and run random simulations. It can be run thousands of times to get an average outcome, which is the model’s prediction.
For the most part, yes – the models matched ant behaviors admirably. But the Monte Carlo simulations also tended to predict success too well. With the ants, you saw more random noise in success or failure at finding the right path.
While at first blush this seems like a weakness in the ant colony, there is actually a good reason to throw some randomness into the mix.
Random noise is random data collected in an experiment that is impossible to avoid. It usually cancels itself out and is distinct from the general pattern of the data.
The pheromones, you’ll recall, act as a positive feedback loop. Once pheromones have been established on the shortest path, that’s where the ants go. If the short path is gone, they get established on the longer path. No hope for discovery elsewhere. Ants can even get stuck in death loops, where they march dutifully in a circular path that somehow caught the most pheromones, until they drop dead from exhaustion.
In these cases, a few random rebels have a chance at tipping the scales. While the simulations predict little to no discovery of short paths after a long path had been established, in real life, this wasn’t the case. Some – not many, but some – of the ant colonies were able to find the short one. This is because that for all pheromones are worth, there is still enough randomness in individual ant behavior to (sometimes) rescue the whole colony and break away from a deadly (or maybe just inconvenient) pheromone-scented path.
From Biology to Technology
Observing the collective genius of an ant colony may be fascinating (well, to some people), but, a less discovery-oriented scientist might ask, what’s the point?
By translating ant behavior into a set of reasonably well-match equations, however, we can not only describe ant behavior in a computer. We can use it to solve problems of our own.
A second paper, published some years later, takes equations tracking ants in a colony and applies it to a routing algorithm.
Routers direct Internet traffic. They send information where it’s needed, and prevent data from clogging connections.
They named their biologically inspired traffic-routing algorithm AntNet, and compared it to a bunch of other routing algorithms. They found AntNet to be remarkably efficient. They also compared it to a “Daemon” algorithm, which is a trick algorithm that acts as a kind of control. This trick algorithm asks, “What if the algorithm knew everything in this system, so could act perfectly every time?” AntNet actually behaved closely to this ideal. This robustness held true whether bit rates (the speed of information traveling through the network) was at a constant rate or a variable one, and whether traffic was distributed throughout the network in a uniform or random manner.
And that is how you can stare at ant colonies, make a few observations, and eventually, improve modern technology. In the next hymenopteran post, we’ll take a look at how ants move large objects as a group, and how that might inform future attempts in swarm robotics.
References
di Caro, G., & Dorigo, M. (1998). Mobile agents for adaptive routing. Proceedings of the Hawaii International Conference on System Sciences, 7(August 2017), 74–83. https://doi.org/10.1109/hicss.1998.649179
Goss, S., Aron, S., Deneubourg, J. L., & Pasteels, J. M. (1989). Self-organized shortcuts in the Argentine ant. Naturwissenschaften, 76(12), 579–581. https://doi.org/10.1007/BF00462870
Bio by the Bay 