Some folks over in the UK decided they wanted to know how the Bombus terristrus (a bumble bee) figured out and remembered the path along which it visited flowers for nectar. What they did was pretty clever. They first developed these computer controlled flowers that they could activate how they saw fit. Then the introduced one flower to the bees at a time (over the course of about two days). If the bees continued to visit these sucrose dispensaries in the order they were introduced they would be traveling along the least optimal path (i.e. flying over a far greater distance than they had to).
Instead the researchers found that over the course of just a few days the bees most often favored an optimal path to visit the flowers (213 times versus 110 trips along the discovery route). Additionally, after two days the optimal route was traveled over 30 times as often as the discovery route.
Essentially the bees had solved the traveling salesman problem (visiting each "house" once in an optimal way) which is an NP-Hard problem. In fact, for n houses the direct algorithm should take something on the order of O(n!) time to run. This means that for 2 flowers there are 2 "checks" needed to solve the problem, but for 3 flowers there are 6 checks and for 4 there are 24! Indeed, it would only take 5 flowers to require over 100 checks (120!!). This problem with the bee flight is even more complex because the bee is also weighing in the decision to spend energy along the trip (see this for more details) which makes the problem something like F raised to the NP-Hard. Ouch! Humans have been tested doing this too. I'm afraid we didn't do as well as the bees.
So how do they do it? ;)
ReplyDeleteThere wasn't any real indication of how. But bees communicate via dancing and can transmit information like where they went and what they found. Presumably a bee could witness several dances and conclude which was better. Some sort of distributed computing/ simultaneous processessing phenomena. Like a networked quantum processor.
ReplyDelete