Factoring the Mapping Problem

To solve the mapping problem, an autonomous robot explores an unknown environment and uses its own observations to build a useful map. Maps have a variety of different uses, including route planning, local motion control with hazard avoidance, estimating distances and directions, localization, and place recognition. Although important progress has been made on the SLAM (simultaneous localization and mapping) problem within a single global frame of reference, metrical uncertainty can still accumulate over time, making it difficult to close large loops with confidence. In recent work to address this problem, we have revised the basic Spatial Semantic Hierarchy (SSH) to become the hybrid SSH, by defining a clean interface to the local perceptual map. We exploit the strengths of three different map representations to factor the mapping problem into three distinct sub-problems that can be solved reliably:

local metrical mapping in the scrolling local perceptual map;
global topological mapping given the local metrical maps, generating a tree of all possible maps to resolve structural ambiguities;
a global metrical map, given the local metrical and global topological maps.

By factoring the problem in this way, we can build an accurate global metrical map on the skeleton provided by the accurate global topological map. The factored problem also leads to a robust and useful map: the local metrical map is useful for place recognition and local motion control with hazard avoidance; the global topological map is useful for localization and route planning; and the global metrical map is useful for estimating distances and directions.

References

This ICRA-05 paper describes how places are detected during continuous motion through a continuous environment. It provides an extension to the Voronoi Graph that overcomes a number of problems.
Patrick Beeson, Nicholas K. Jong, and Benjamin Kuipers. 2005.
Towards Autonomous Topological Place Detection Using the Extended Voronoi Graph.
IEEE International Conference on Robotics and Automaton (ICRA-05).
This ICRA-04 paper describes the scrolling local perceptual map, the abstraction from place neighborhoods in small-scale space to local topological descriptions in large-scale space, and the map-tree algorithm for generating possible topological maps and filtering them for consistency.
Benjamin Kuipers, Joseph Modayil, Patrick Beeson, Matt MacMahon, and Francesco Savelli. 2004.
Local metrical and global topological maps in the hybrid Spatial Semantic Hierarchy.
IEEE International Conference on Robotics and Automation (ICRA-04).
This IROS-04 paper shows how we can build a highly accurate global metrical map, by using the structure of the topological map as a skeleton.
Joseph Modayil, Patrick Beeson and Benjamin Kuipers. 2004.
Using the topological skeleton for scalable global metrical map-building.
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS-04).
This IROS-04 papers describes a consistency test for proposed topological maps based on planarity. This test prunes the tree of possible maps dramatically.
Francesco Savelli and Benjamin Kuipers. 2004.
Loop-closing and planarity in topological map-building.
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS-04).
This AIJ paper, describing Emilio's PhD thesis, gives an axiomatization in non-monotonic logic for the topological map. Potential maps are pruned from the tree of maps if they violate any of these axioms.
Emilio Remolina and Benjamin Kuipers. 2004.
Towards a general theory of topological maps.
Artificial Intelligence 152: 47-104, 2004.
This AIJ paper gives an overview of the Spatial Semantic Hierarchy, which decomposes knowledge of large-scale space into several different representations, each with its own distinctive ontology for space.
Benjamin Kuipers. 2000.
The Spatial Semantic Hierarchy.
Artificial Intelligence Journal 119: 191-233.

[QR home]

BJK