Entire Forum This board This topic Members Entire Site
 Pages: [1]
 Author Topic: Blind Maze Search Algorithm  (Read 1648 times) 0 Members and 1 Guest are viewing this topic.
MoarK
Newbie

Offline

Posts: 23

Thank You
-Given: 11

 « on: July 21, 2010, 03:56:35 03:56 »

The problem:
a robotic vacuum cleaner must clean an unknown space.

The rules:
it has no previous knowledge of the space
it may take one step at a time in any of 4 directions
it must visit every open location at least 1 time
it must not visit any location more than 2 times

The very simple algorithm presented accomplishes this.
There are 4 possible directions to move. The order of priority does not matter and will be intrinsic to the order of the tests in the software.
This algorithm was implemented and tested using a bitmap as the space. Obstacles were placed into the space  and the virtual robot was placed randomly and allowed to search. There are about 8000 units of space in the bitmap.

The robot knows 3 kinds of entity: UNKNOWN, OBSTACLE and VISITED ONCE, which are represented in colors in the figure. VISITED TWICE is a color used only for testing the algorithm. Here have been placed various obstacles of different shapes in to bounded space. The robot will search and map it as shown in the animated gif.

Although it has been made into a .gif, it is still 153kB in size, so I have placed it on a host in consideration of any members with a slow connection.
http://img441.imageshack.us/img441/5585/success002.gif

The robot preferentially chooses to move to any location it does not know.
Within that set of options, the robot preferentially chooses to move next to a known obstacle.
This is called thigmotaxis (like a cockroach) and results in successful traverse of a maze.
If there is no known obstacle, the robot then will choose to move next to a space it has visited once.
Otherwise it will try anything available.
A successful move is pushed on a stack.
All obstacles and moves are recorded on a map.
If there are no unvisited locations available for a move, the robot will reverse its path, popping the stack of previous moves in order, until it finds a location that it has not yet visited and will proceed there.

As you can see, the algorithm is extremely simple and requires no fore-knowledge of the area. Almost every location is visited twice but not every one. Enlarge the animated gif to see.

Further work:
At each location, an image is taken by a 1 pixel high 256 bit wide  360 degree scan using a laser pointer. This image is used for the robot to calibrate its position as it explores the space.

I hope you found it interesting how a very simple program using only proximal sensory data could accomplish so much so well with less than the brain of a bug.

 Logged

P-}
 Pages: [1]