Bees, ants, space and algorithm

In 2011, Science Daily reported on a study done at Queen Mary University of London and published in Biology Letters.  The study examined the foraging strategies of bumblebees and found that “after extensive training (80 foraging bouts and at least 640 flower visits), bees reduced their flight distances and prioritized shortest possible routes.” The bees were able to solve complex routing problems through experience and, it seems, without requiring a sophisticated cognitive representation of space. Science Daily made these observations:

Surprisingly, the bees almost never followed a nearest-neighbor strategy (in which the bee would fly to the nearest unvisited flower until all flowers are visited).  Instead they prioritized following the shortest possible route by learning and memorizing individual flower locations.

Dr. Lihoreau, who headed the team, was quoted as saying: “Despite having tiny brains, bees effectively used gradual optimization (comparing several different routes), to solve this famously complex routing problem which still baffles mathematicians 80 years after it was first posed.”

What strikes me first about these studies is the absence of the need for a “cognitive representation of space.”  It happens in physics and mathematics that a set of parameters, which don’t define a physical space, may be put in a kind of spatial relationship in order to be better understood.  But here, it is a physical space that comes to be analyzed algorithmically, with the iteration of a series of judgments.  The ‘space,’ then, while not actually constructed, is understood.

A more recent study, led again by Mathieu Lihoreau, examined the bees’ foraging with the aid of radar tracking and motion-sensitve cameras.

How, then, did the bees optimise their routes? Based on our detailed analysis of bee movement patterns, we implemented a simple iterative improvement heuristic, which, when applied to our experimental situation, matched the behaviour of real bees exceptionally well. The proposed heuristic demonstrates that stable efficient routing solutions can emerge relatively rapidly (in fewer than 20 bouts in our study) with only little computational demand. Our hypothetical model implies that a bee keeps in memory the net length of the shortest route experienced so far and compares it to that of the current route traveled. If the novel route is found to be shorter, the bee is more likely to repeat the flight vectors comprising this route. Hence, through a positive feedback loop certain flight vectors are reinforced in memory, while others are “forgotten”, allowing the bee to select and stabilize a short (if not optimal) route into a trapline. These assumptions are compatible with well-established observations that bees compute and memorise vector distances between locations using path integration. For instance, bees visiting the same feeders over several bouts learn flight vectors encoding both direction and travel distance to each site, by associating specific visual scenes (such as salient landmarks or panoramas) with a motor command.

The optimisation process we describe is analogous to the iterative improvement approach developed in “ant colony optimisation” heuristics, which has been increasingly used to explore solutions to combinatorial problems in computer sciences. The rationale of these swarm intelligence heuristics is based on a model describing how ants collectively find short paths between a feeding location and their nest using chemical signals. “Memory” in ant colony optimisation algorithms has no neurobiological basis but instead takes the form of pheromone trails marking established routes. The shortest route becomes more attractive due to increases in pheromone concentration as multiple ants forage simultaneously along it and continue to lay pheromone, while longer routes are abandoned because of pheromone evaporation. (emphasis my own)

A bit more that a year ago, I blogged about this vector approach to navigation as it was seen in ants.

When Science Magazine reported on the bee study, they also took note of the fact that the bees were solving what mathematicians call the traveling salesman problem – calculating the shortest possible route given a theoretical arrangement of cities.  The problem was given mathematical definition in the 1800’s by W. R. Hamilton and Thomas Kirkman.  The general form of the problem was studied in the 1930’s by Karl Menger who makes the observation that “The rule that one first should go from the starting point to the closest point, then to the point closest to this, etc., in general does not yield the shortest route.”  The bees, it seems, know this instinctively.

In the 1950’s and 1960’s the problem became more popular, new methods for solving it were developed and the shortest routes involving 49 cities were solved.  By the 1980’s, instances with up to 2392 cities were solved.  To look directly at the possibilities for a solution would mean to try all permutations of possible routes and select the shortest.  But the running time for this approach makes it impractical for even 20 cities.  It was in 1997 that Marco Dorgio described a method for generating ‘good solutions’ using a simulation of ant colony navigation.  It happens that the traveling salesman problem has application, not only in logistics, but in microchips and even DNA sequencing where the concept city represents DNA fragments, and the concept distance, a similarity measure between DNA fragments.

It’s probably important that in computer science the ant colony optimization algorithm  (ACO) is a probalistic technique for solving certain kinds of computational problems.  And I find that there is, in more than one sense, an interesting coincidence of things here.  There is the encoding of distance and direction in creatures who don’t have what we would call spatial cognition, the very effective understaning of spatial relationships in an iterative, trial and error way, and the application of an insect’s foraging strategy to modern problems in mathematics and computer science.  We might want to say that we can now describe bee and ant behavior algotithmically, but I would say they are describing algorithms with their behavior.