Learning Geometrically-Constrained Hidden Markov Models for Robot Navigation: Bridging the Topological-Geometrical Gap

Such maps specify the topology of important landmarks and situations (states), and routes or transitions (arcs) between them. They are concerned less with the physical location of landmarks, and more with topological relationships between situations. Typically, they are less complex and support much more ecient planning than metric maps. Topological maps are built on lowerlevel abstractions that allow the robot to move along arcs (perhaps by wall-or road-following), to recognize properties of locations, and to distinguish signicant locations as states; they are exible in allowing a more general notion of state, possibly including information about the non-geometrical aspects of the robot's situation. There are two typical strategies for deriving topological maps: one is to learn the topological map directly; the other is to rst learn a geometric map, then to derive a topological model from it through some process of analysis. A nice example of the second approach is provided by Thrun and B--ucken (1996a, 1996b; Thrun, 1999), who use occupancy-grid techniques to build the initial map. This strategy is appropriate when the primary cues for decomposition and abstraction of the map are geometric. However, in many cases, the nodes of a topological map are dened in terms of other sensory data (e.g., labels on a door or whether or not the robot is holding a bagel). Learning a geometric map rst also relies on the odometric abilities of a robot; if they are weak and the space is large, it is very dicult to derive a consistent map.