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
it must return to the location it started
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.gifThe 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.
