Facebook
Twitter
Pocket
Reddit
Email
As someone so flummoxed by traffic I wrote a book about it, I have a near-clinical aversion to vehicular congestion. My global default strategy is to simply drive as little as possible, but there are times when I simply must put foot to gas pedal. Like many, I have become increasingly dependent on the Waze app, which, via each drivers’ smartphone, turns an inchoate, undifferentiated mass of drivers into something resembling a collective form of networked intelligence.
Waze, it occurred to me the other day while stuck in a bit of unexpected congestion (which had been duly flagged by at least 13 “Wazers”), is helping us turn into ants. Every time drivers travel down a path, Waze tracks their speed—information that can then be broadcast to every following driver. Should something threaten to disrupt that path—a stalled car, a crash, or the vaguely sinister “hazard on road”—the first drivers to encounter it can leave little electronic bread crumbs in their wake; if enough of these ghostly trails are left, some percentage of subsequent Waze users may be redirected to another path.
All this is strikingly similar to the dynamics of movement found in ant colonies; small wonder, then, that ants have proved so endurably fascinating to network researchers.
The Belgian researcher Marco Dorigo is credited with the first work, in the early 1990s, in what is now broadly called “ant colony optimization” (usually shorted to ACO), a strategy for organizing movement largely based on actual ant behavior. As he described it in an early paper, “while walking from food sources to the nest and vice versa, ants deposit on the ground a substance called pheromone, forming in this way a pheromone trail. Ants can smell pheromone and, when choosing their way, they tend to choose, in probability, paths marked by strong pheromone concentrations.”
In a sort of virtuous circle (Dorigo calls it “autocatalytic feedback”), the shorter the route is, the quicker the accumulation of pheromone (and hence the more desirable the path). Pheromone concentrations evaporate over time, leaving the sub-optimal paths to wither away. Similarly, on Waze, drivers can “thumb” reports of congestion up or down, a kind of “e-pheromone” that helps other drivers avoid the more sluggish routes. (What and how much information should actually be given to drivers to achieve the most widely optimal solution is a tricky problem.)
These “traces in the environment,” in a process generally referred to as “stigmergy,” help explain how simple agents, without a larger meta-ability to communicate, coordinate, or structure their transport networks, can display such “surprisingly intelligent collective behavior.” Humans are not so ruthlessly efficient—the University of Minnesota transportation researcher David Levinson found, in one study, that only 15 percent of daily commuters were on the shortest route possible.
One reason ants seem to perform so well is their strict, non-selfish adherence to these evolved algorithms for behavior.
Ant colony optimization has itself migrated with impressive speed and range, and has been taken up residence in all kinds of research pursuits, from estimating electricity consumption in Turkey to designing supply chains to the design of tall bridge piers to robot learning.
But as you might imagine, transport researchers have been particularly drawn to the approach—and, it seems, with good reason. In a 2012 paper, civil engineers from Texas A&M University wanted to see if ant colony optimization held its ground against a “genetic algorithm” approach for a common problem in traffic engineering: How to best coordinate timing for groups of traffic signals when traffic had reached “oversaturation” levels.
A genetic algorithm, as its name reflects, mimics the process of natural selection; it “searches” for the best solution to a problem—just as evolution seems to do, in adapting organisms to their environment—by modifying potential solutions, in this case traffic-light coordination, in an iterative process.
The ACO began to exceed the genetic algorithm as the number of “model executions” went up; as the authors noted, “this suggests that ACO may better handle more complicated real world traffic situations that would require large numbers of simulations to reach convergence.” (Of course, ant colony optimization varies in all kinds of ways from “real world” traffic; drivers, for instance, have pre-determined destinations, while ants do not, and so varying refinements have been made to try and make ACO more, well, human). “This indicates,” the authors go on to say, “that better solutions for the same computational power are identified, especially when the computational time can be afforded to search for the best possible solution, and that ACO may be a good alternative for solving very complicated networks.”
One reason ants seem to perform so well is their strict, non-selfish adherence to these evolved algorithms for behavior. In a fascinating experiment published in April, ants were placed in a chamber with two exits. Varying proportions of citronella oil—which ants intensely dislike—were added to the chamber (“All efforts were made to minimize suffering”), and the scientists tracked how ants exited the chamber. For comparison, a computer simulation was run to see how humans would have egressed (using Dirk Helbing’s “Social Force Model” of pedestrian behavior). As the researchers noted, “the differences between the predictions of the Social Force Model and behaviors of ants are remarkable.” Where humans immediately made for—and began jamming—the exits, “the ants spread out over the majority of the area,” utilizing a wider area (except that closest to the offensive citronella). In a sort of “slower-is-faster” effect, by more carefully arranging themselves ahead of time, they avoided jamming the exits.
This tendency for humans to pursue “selfish routing” strategies, at the cost of the larger network, has long been noted in traffic. As the English mathematician and transport researcher John Glen Wardrop first articulated, in the famous “Wardrop equilibrium,” what is best for individual driver (“user equilibrium”) is not necessarily that which is best for traffic as a whole (“system equilibrium”). In a Boston-area study that used anonymized cellphone data, for instance, a team from the Massachusetts Institute of Technology found that canceling a mere 1 percent of trips from a geographically targeted section of commute origins would reduce all drivers’ trips by 18 percent.
The endlessly cooperative and eusocial ants would not let this larger network inefficiency stand. The outsized traffic impact of one miniscule sector of human commuters shows the distinct weakness in our transport networks: Who is going to tell that 1 percent of Boston commuters not to drive, or to change their routes, while everyone else carries on as usual?
Tom Vanderbilt writes on design, technology, science, and culture, among other subjects. Follow him on Twitter @tomvanderbilt.
The lead photograph is courtesy of Bernardinus Nugraha via Flickr.
Get the Nautilus newsletter
Cutting-edge science, unraveled by the very brightest living thinkers.
