Topology in Motion Planning

Many motion planning, artificial intelligence, and mobile robot planning techniques exploit topology, as encoded in the free space, to aid in generating concise maps and efficient planners. Prior work of the authors has used the generalized Voronoi diagram, which is a topological map that has a natural embedding into the free space. Topological maps have been used in the AI community, starting with Ben Kuipers insightful work on distinctive places and edges that connected them (although he used a Voronoi diagram-like structure also). In this paper, we put forth a more rigorous definition of a topological map, and then overview problems that exploit a topological map to achieve tasks including path planning, SLAM, and hybrid controls.

Authors and Affiliations

1. Department of Mechanical Engineering, Carnegie Mellon University, USA

   Howie Choset

2. The Robotics Institute, Carnegie Mellon University, USA

   Alfred A. Rizzi

Editors and Affiliations

1. CRIM & ARTS Labs, Polo Sant’Anna Valdera, Scuola Superiore Sant’Anna, Viale Rinaldo Piaggio 34, 56025, Pontedera, Pisa, Italy

   Paolo Dario

2. LAAS-CNRS, 7, avenue du Colonel Roche, 31077, Toulouse cedex 4, France

   Raja Chatila

Reprints and permissions

© 2005 Springer-Verlag Berlin Heidelberg

Policies and ethics