What algorithm should I implement to program a room cleaning robot?

Question

For this question assume that the following things are unknown:

• The size and shape of the room
• The location of the robot
• The presence of any obsticles

Also assume that the following things are constant:

• The size and shape of the room
• The number, shape and location of all (if any) obsticles

And assume that the robot has the following properties:

• It can only move forward in increments of absolute units and turn in degrees. Also the operation that moves will return true if it succeeded or false if it failed to move due to an obstruction
• A reasonably unlimited source of power (let's say it is a solar powered robot placed on a space station that faces the sun at all times with no ceiling)
• Every movement and rotation is carried out with absolute precision every time (don't worry about unreliable data)

I was asked a much simpler version of this question (room is a rectangle and there are no obstacles, how would you move over it guaranteeing you could over every part at least once) and after I started wondering how you would approach this if you couldn't guarantee the shape or the presence of obstacles. I've started looking at this with Dijkstra's algorithm, but I'm fascinated to hear how others approach this (or if there is a well accepted answer to this? (How does Roomba do it?)

Answer 1

Take a look at SLAM http://openslam.org/ and for more Wiki

Answer 2

You further should look into

Mark de Berg: Computational Geometry Algorithms and Applications Chapter 13 Robot Motion Planning