Robot exploration algorithm

Question

I'm trying to devise an algorithm for a robot trying to find the flag(positioned at an unknown location), which is located in a world containing obstacles. Robot's mission is to capture the flag and bring it to his home base(which represents his starting position). The robot, at each step, sees only a limited neighborhood (he does not know how the world looks in advance), but he has an unlimited memory to store already visited cells.

I'm looking for any suggestions about how to do this in an efficient manner. Especially the first part; namely getting to the flag.

 

Answer 1

As searching for an unknown area, for an unknown object.

You can use something like Pledge's algorithm until you've found the boundaries of your space, record all information as you go. Then go have a look at all unseen squares using your favorite drift/pathfinding algorithm. If, at any point along the way, you see the flag, stop what you're doing and use your favorite pathfinding algorithm to go home.

A simple Breadth First Search/Depth First Search will work, but they are slow algorithms. 

A* is the more elegant approach, especially if you know the location of the flag relative to yourself. The classic heuristic to use is the manning distance (number of moves assuming no obstacles) to the destination.

These approaches involve creating objects that represent squares on your map and creating "paths" or series of the square to hit (or steps to take).

These algorithms are useful for the return trip as the robot's mission is to capture the flag and bring it to his home base(which represents his starting position).