Monday, November 22, 2010

Bees solve the TSP

From the Media Center at Queen Mary, University of London:
Scientists at Queen Mary, University of London and Royal Holloway, University of London have discovered that bees learn to fly the shortest possible route between flowers even if they discover the flowers in a different order. Bees are effectively solving the 'Travelling Salesman Problem',
Of course it's not as mathematically formal as the preceding suggets. Here's the abstract from The American Naturalist.
Animals collecting resources that replenish over time often visit patches in predictable sequences called traplines. Despite the widespread nature of this strategy, we still know little about how spatial memory develops and guides individuals toward suitable routes. Here, we investigate whether flower visitation sequences by bumblebees Bombus terrestris simply reflect the order in which flowers were discovered or whether they result from more complex navigational strategies enabling bees to optimize their foraging routes. We analyzed bee flight movements in an array of four artificial flowers maximizing interfloral distances. Starting from a single patch, we sequentially added three new patches so that if bees visited them in the order in which they originally encountered flowers, they would follow a long (suboptimal) route. Bees’ tendency to visit patches in their discovery order decreased with experience. Instead, they optimized their flight distances by rearranging flower visitation sequences. This resulted in the development of a primary route (trapline) and two or three less frequently used secondary routes. Bees consistently used these routes after overnight breaks while occasionally exploring novel possibilities. We discuss how maintaining some level of route flexibility could allow traplining animals to cope with dynamic routing problems, analogous to the well‐known traveling salesman problem.
In the PR release Dr Nigel Raine from Royal Holloway's school of biological sciences is quoted as saying,
Despite their tiny brains bees are capable of extraordinary feats of behaviour.
Of course this is not quite so extraordinary. All they need do is keep track of the distance for any route and then through experimentation among different routes select the shortest found so far. Even that's not trivial, but it's a lot less sophisticated than "solving" TSP.

No comments: