Exploration and Reasoning in Large-Scale and Visual Spaces

Benjamin Kuipers
Computer Sciences Department
The University of Texas at Austin


We have developed the Spatial Semantic Hierarchy (SSH) as a heterogeneous representation for knowledge of large-scale space: the cognitive map. Each level of the SSH has its own descriptive ontology and its own mathematical foundation. The objects, relations, and assumptions at each level are abstracted from the levels below. The control level allows the robot and its environment to be formalized as a continuous dynamical system, whose stable equilibrium points can be abstracted to a discrete set of ``distinctive states.'' Trajectories linking these states can be abstracted to actions, giving a discrete causal graph representation of the state space. The causal graph of states and actions can in turn be abstracted to a topological network of places and paths. Local metrical models, such as occupancy grids, of neighborhoods of places and paths can then be built on the framework of the topological network without their usual problems of global consistency.

We are extending these ideas in two directions. First, we are exploring the hypothesis that a similar hierarchy of representations can be used for acquisition and use of knowledge of visual space, building from active feature trackers to multiple frames of reference for spatial relations. Second, we are applying our ideas to the development of an intelligent wheelchair, intended to serve a driver with normal cognition but severely impaired mobility and communication capabilities. The intelligent wheelchair application raises a number of exciting issues in spatial reasoning about both large-scale and visual space, multi-modal sensor integration, and mixed-initiative human-computer interfaces.

Eyal Amir
Last modified: Sun Apr 12 18:31:00 PDT 1998