Basic continuous 2D map exploration ( with obstacles ) algorithms

Question

Here is the problem: There is a map which size is anywhere from 200*200 pixels to 1000*1000 pixels. Each pixel is a third of an inch in length/width.

The map has walls coming from it (which can be of any size), and can be pre-processed by any means. However, when the problem starts, a robot (of pixel size 18*18) is placed in an unknown location, along with several obstacles and one goal, all of which are in an unknown location.

If the robot bumps into any wall/object/goal it immediately dies. As such it has a simple laser scanner that perfectly sees an 80*80 pixel square ahead of it,centered on the robot.

I have already solved the problem of localizing the robot and determining its position (within a small error) on the grid. I am having a bit of trouble with making a good algorithm for going across the entire map until the goal is found.

I have the idea of making the robot go to the lower right, and somehow sweeping left to right, avoiding obstacles, and walls, until the goal is found, however I am unsure of a good way to do that.

Are there any decent algorithms for such a thing, or are there better ones for what I am trying to do?

Answer 1

You are looking for Pathfinding Algorithms

Some suggestions include "Flood Fill" algorithm or "Dijkstra’s algorithm" very similar to Lee's algorithm (I might even argue they are the same), but it's just another term to search for

This is probably the most popular simple path finding algorithm: "A*search" (a star Search) this link also showcases a few other path finding algorithms. (Another helpful link).

The key with a*star search is that you must know where you are (localization) and where the goal is. Dijkstra type algorithms are able to find the goal without prior knowledge of its location.