For this question assume that the following things are unknown:
Also assume that the following things are constant:
And assume that the robot has the following properties:
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?)
Take a look at SLAM http://openslam.org/ and for more Wiki