RI | Seminar | November 14, 2008

Robotics Institute Seminar, November 14, 2008
Time and Place | Seminar Abstract | Speaker Biography | Speaker Appointments

---

Navigation within the Hybrid Spatial Semantic Hierarchy

Benjamin Kuipers

University of Texas at Austin
University of Michigan (starting January 2009)

Time and Place

Mauldin Auditorium (NSH 1305 )

Time: 3:30 to 4:30 pm

Abstract

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.

Speaker Biography

Benjamin Kuipers holds an endowed Professorship in Computer Sciences at the University of Texas at Austin. He investigates the representation of commonsense and expert knowledge, with particular emphasis on the effective use of incomplete knowledge. He received his B.A. from Swarthmore College, and his Ph.D. from MIT. He has held research or faculty appointments at MIT, Tufts University, and the University of Texas. 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, and is a Fellow of AAAI and IEEE. Beginning in January 2009, he will join the University of Michigan as Professor of Computer Science and Engineering.

Speaker Appointments

For appointments, please contact Reid Simmons (reids@cs.cmu.edu)

---

The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University.