Robot Navigation within the Hybrid Spatial
Semantic Hierarchy
Professor Benjamin Kuipers
Computer
Science & Engineering
University of Michigan
Abstract 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.
Bio: 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.
Friday, January 30, 2009
3:30 – 4:30p.m
Rm. 1500 EECS