Topology in Motion Planning

Abstract

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.