Creating and Utilizing Symbolic Representations of Spatial Knowledge using Mobile Robots

Patrick Beeson. Creating and Utilizing Symbolic Representations of Spatial Knowledge using Mobile Robots. Ph.D. Thesis, The University of Texas at Austin, 2008.

Abstract

A map is a description of an environment allowing an agent---a human, or in our case a mobile robot---to plan and perform effective actions. From a single location, an agent's sensors can not observe the whole structure of a complex, large environment. For this reason, the agent must build a map from observations gathered over time and space. We distinguish between large-scale space, with spatial structure larger than the agent's sensory horizon, and small-scale space, with structure within the sensory horizon. We propose a factored approach to mobile robot map-building that handles qualitatively different types of uncertainty by combining the strengths of topological and metrical approaches. Our framework is based on a computational model of the human cognitive map; thus it allows robust navigation and communication within several different spatial ontologies. Our approach factors the mapping problem into natural sub-goals: building a metrical representation for local small-scale spaces; finding a topological map that represents the qualitative structure of large-scale space; and (when necessary) constructing a metrical representation for large-scale space using the skeleton provided by the topological map. The core contributions of this thesis are a formal description of the Hybrid Spatial Semantic Hierarchy (HSSH), a framework for both small-scale and large-scale representations of space, and an implementation of the HSSH that allows a robot to ground the large-scale concepts of place and path in a metrical model of the local surround. Given metrical models of the robot's local surround, we argue that places at decision points in the world can be grounded by the use of a primitive called a gateway. Gateways separate different regions in space and have a natural description at intersections and in doorways. We provide an algorithmic definition of gateways, a theory of how they contribute to the description of paths and places, and practical uses of gateways in spatial mapping and learning.

BibTeX

@PhdThesis{Beeson-phd-08,
  author =       {Patrick Beeson},
  title =        {Creating and Utilizing Symbolic Representations of Spatial
                  Knowledge using Mobile Robots},
  school =       {The University of Texas at Austin},
  year =         2008,
  month =        {August},
  abstract =     {A map is a description of an environment allowing an
                  agent---a human, or in our case a mobile robot---to plan and
                  perform effective actions. From a single location, an
                  agent's sensors can not observe the whole structure of a
                  complex, large environment. For this reason, the agent must
                  build a map from observations gathered over time and
                  space. We distinguish between large-scale space, with
                  spatial structure larger than the agent's sensory horizon,
                  and small-scale space, with structure within the sensory
                  horizon. We propose a factored approach to mobile robot
                  map-building that handles qualitatively different types of
                  uncertainty by combining the strengths of topological and
                  metrical approaches. Our framework is based on a
                  computational model of the human cognitive map; thus it
                  allows robust navigation and communication within several
                  different spatial ontologies. Our approach factors the
                  mapping problem into natural sub-goals: building a metrical
                  representation for local small-scale spaces; finding a
                  topological map that represents the qualitative structure of
                  large-scale space; and (when necessary) constructing a
                  metrical representation for large-scale space using the
                  skeleton provided by the topological map. The core
                  contributions of this thesis are a formal description of the
                  Hybrid Spatial Semantic Hierarchy (HSSH), a framework for
                  both small-scale and large-scale representations of space,
                  and an implementation of the HSSH that allows a robot to
                  ground the large-scale concepts of place and path in a
                  metrical model of the local surround. Given metrical models
                  of the robot's local surround, we argue that places at
                  decision points in the world can be grounded by the use of a
                  primitive called a gateway. Gateways separate different
                  regions in space and have a natural description at
                  intersections and in doorways. We provide an algorithmic
                  definition of gateways, a theory of how they contribute to
                  the description of paths and places, and practical uses of
                  gateways in spatial mapping and learning.},
  bib2html_pubtype ={PhD Thesis},
  bib2html_rescat ={Topological/Hybrid Map-Building}
}

Download:

[3.7MB pdf]