2-D Search Algorithims

Darin Sunley (rsunley@escape.ca)
Mon, 16 Aug 1999 18:30:15 -0500

An article in a recent issue of Scientific American (I believe) described a simple algorithim that duplicated to a surprising degree the algorithim that a cockroach uses as it searches for food. As I recall, the algorithim went roughly like this.

smell for food
move forward a random number of steps
repeat until we've found food:

smell for food
if we are closer to food then we were

walk forward a random number of steps else

        spin in a random direction
        walk forward a random number of steps

Does anybody recall the particular issue of Scientific American this article appeared in, or have a URL to any other references on this. I am attempting to implement this algorithim in a robot built with the Lego Mindstorms kit and I want to make sure I have the algorithim right.

On a related note, has anybody ever heard of the term "retreating search curve" used to describe a search for a particular point on a two dimensional surface. If so, could you please direct me to any sources you may know of?

Thank you in advance...
Darin Sunley