Robot Navigation within the Hybrid Spatial Semantic Hierarchy

Robot (and human) navigation takes place at two distinct scales of space. Large-scale space is space whose structure is larger than the sensory horizon of the agent. This is the space of the cognitive map, which must be learned by merging information gathered during exploration. Small-scale space is within the sensory horizon of the agent, where the agent can reliably localize itself and can build an accurate map within a local frame of reference.

The Spatial Semantic Hierarchy (SSH) is a sensor-independent structure that shows how several different ontologies can be used together to represent knowledge of large-scale and small-scale space. The basic SSH uses hill-climbing and trajectory-following control laws to explore large-scale space even with very limited knowledge of sensor semantics. The Hybrid SSH (HSSH) includes both large and small scales, and exploits knowledge of the sensors to build local maps.

At the local metrical level, the robot builds a bounded local perceptual map (LPM) representing the hazards and free-space in the small-scale space around it. The LPM scrolls with the robot's motion, and provides an accurate metrical model of local space for motion planning, using any SLAM algorithm. Since the LPM is a bounded map within the agent's sensory horizon, updates require constant time and the problem of closing large loops does not arise.

At the global topological level, the agent describes large-scale space as a graph of places and paths, which is a compact, scalable representation for planning and navigation. A place is represented by a node in the topological map, and is linked with a local metrical map describing the place neighborhood as a small-scale space. The problem of closing large loops during map-building is represented and solved much more naturally as a problem in topological mapping, not of metrical mapping. After planning a route in the global topological map, execution consists of hazard-avoiding motion in the small-scale space of the scrolling LPM.

The abstraction relation between local metrical and global topological maps is maintained by continually identifying the local decision structure of the LPM. The multiple ontologies in the HSSH naturally support robust representation and learning of spatial knowledge, and implementation in three-tier planning and execution architectures. They also naturally support multiple levels of human-robot interaction.

Benjamin Kuipers joined the University of Michigan in January 2009 as Professor of Computer Science and Engineering. Prior to that, he held an endowed Professorship in Computer Sciences at the University of Texas at Austin. He received his B.A. from Swarthmore College, and his Ph.D. from MIT. He investigates the representation of commonsense and expert knowledge, with particular emphasis on the effective use of incomplete knowledge. His research accomplishments include developing the TOUR model of spatial knowledge in the cognitive map, the QSIM algorithm for qualitative simulation, the Algernon system for knowledge representation, and the Spatial Semantic Hierarchy model of knowledge for robot exploration and mapping. He has served as Department Chair at UT Austin, and is a Fellow of AAAI and IEEE.