Ja Odometrie über die Räder wäre eine Möglichkeit, kommt eben auch die Umgebung sehr an (Muss der Roboter über Schwellen oder kleine Stufen laufen, z.B. Teppich?).
Die Idee mit der Karte finde ich eine wesentlich bessere und interessantere Lösung. Du könntest die Karte in Kästchen unterteilen und diesen Werten (z.B. 0/1) zuordnen, je nach dem ob sie befahrbar sind oder nicht (z.B.: Tisch, Sofa, etc.). Dann kannst du dir einen schönen Labyrinth-Algorithmus raussuchen, bei dem er alle befahrbaren Felder abfährt und musst ihm nur noch eine fixe Startposition zuweisen. Auch hier wirst du eine Art der Positionsbestimmung brauchen.