Monday, October 25, 2010

The Bee and the Travelling Salesman


According to an article that appeared yesterday on the Web site for The Guardian, a bee can solve the Travelling Salesman Problem (TSP).  Here is a more specific account of that claim:

Bees can solve complex mathematical problems which keep computers busy for days, research has shown.

The insects learn to fly the shortest route between flowers discovered in random order, effectively solving the "travelling salesman problem" , said scientists at Royal Holloway, University of London.

The conundrum involves finding the shortest route that allows a travelling salesman to call at all the locations he has to visit. Computers solve the problem by comparing the length of all possible routes and choosing the one that is shortest.

Bees manage to reach the same solution using a brain the size of a grass seed.

Dr Nigel Raine, from Royal Holloway's school of biological sciences, said: "Foraging bees solve travelling salesman problems every day. They visit flowers at multiple locations and, because bees use lots of energy to fly, they find a route which keeps flying to a minimum."

Using computer-controlled artificial flowers to test bee behaviour, his wanted to know whether the insects would follow a simple route defined by the order in which they found the flowers, or look for the shortest route.

After exploring the location of the flowers, the bees quickly learned to fly the best route for saving time and energy.

If this is to be more than sensationalist journalism (if one believes that mathematics can ever be a topic for sensationalist journalism), however, there are a few questions that we cannot allow to get swept under the rug.  If this is, indeed, a question of learning, what is the nature of the learning process and how long does it take?  Related to this question of efficiency is the question of how many flowers were in the controlled experiment, which might imply that a bee has only so much channel capacity for planning its route.  (This would make sense under the assumption that there is only so much nectar that the bee can harvest on a single trip.)

The problem is that the lead sentence is about as misleading as it is attractive.  Evidence that bees may be good at route planning within their own behavioral constraints does not warrant the conclusion that they “can solve complex mathematical problems.”  Solving the TSP in its full generality is just not a part of what bees do, particularly when we may not yet have a good idea how many flowers a bee can visit in a single trip.  To reason from the example given in the Wikipedia entry for the TSP, if a bee can visit fifteen flowers, then the number of possible routes from which it would have to select the shortest is 43,589,145,600.  If Raine ran his test on fifteen flowers, then I might be willing to take notice, even if the bee could not come up with a closed-form solution for the general case!

As I recently observed, even a comedian like Ricky Gervais would immediately recognize that this has more to do with Wittgenstein’s Lion than with the mathematics of complexity.  In the spirit of Wittgenstein’s assertion that we could not understand what a lion would have to say, even if that lion had some version of what we would call speech, the bee would be no more capable of describing its “flight planning” than a centipede would in describing how it coordinates its legs.  Indeed, the very concept of “planning” is probably alien to both of these scenarios.  We invoke the concept because we believe it is necessary;  but James Gibson rejected that premise in his Ecological Approach to Visual Perception, where he considered the related problem of how birds seem to follow their migratory paths with great consistency.

According to the Guardian story, Raine’s results have been accepted for publication.  They are due to appear this week in The American Naturalist.  I suggest that anyone curious enough to read this document begin by checking if Gibson is in the bibliography.  If he is missing, then I would worry that Raine may have been a bit too myopic in both his methods and his conclusions.

No comments: