Sunday, December 12, 2010

Shortest past algorithm solved by ants?

University of Syndey researchers are working on the next greatest optimization algorithms.  You would think they would be hunkered down in the math or computer science departments working with large multi-core processors.  Yet Chris Reid and Madeleine Beekman, working with David Sumpter of Uppsala Univ., are studying how ants solve the shortest path problem.  By studying how ants solve complex and dynamic problems such as getting food back to their colony they could unravel some new and innovative ways to solve routing problems.  The researchers published their results in Journal of Experimental Biology

There has already been some algorithms developed out of studying the ants.  One method is the Ant Colony Optimisation (ACO) algorithms.  Ants solve the complex problem of shortest path by communicating to other ants in the colony by pheromone trails.  Each ant leaves a pheromone trail as a signal back to a following ant.  The trail has a certain "optimal path" signal telling other ants the best way to get to the intended destination.

It would be really interesting to find out that the best shortest path algorithm might have been literally under our noses the entire time.  This will be an interesting study to follow for the Operations Research community.

2 comments:

Paul Rubin said...

(cringing at that last pun) This may turn out to be just brute force. My guess is that ants wander randomly until they find food, then head back (perhaps via a more direct route). The pheromone signal may just mean that the ants pick up an odor at the food site, and that it dies off gradually on the way back. The shorter the trek, the less fading of the odor, and subsequent ants take the stinkiest route.

Now if ants figure out how to hack the GPS system, I'll be impressed.

Larry said...

Yea okay. That was an awful pun. I was having too much fun with this entry.

It probably is brute force but its interesting that ants really don't consider brute force costly. Maybe we could learn to better brute force analysis from ants.