Constructing roadmaps of semi-algebraic sets I: completeness

Abstract

Abstract This paper describes preliminary work on an algorithm for planning collision-free motions for a robot manipulator in the presence of obstacles. The physical obstacles lead to forbidden regions in the robots configuration space, and for collision-free motion we need paths through configuration space which avoid these regions. Our method is to construct a certain one-dimensional subset or “roadmap” of the space of allowable configurations. If S denotes the set of allowable configurations, the roadmap has the property that any connected component of S contains a single connected component of the roadmap. It is also possible, starting from an arbitrary point p ∈ S to rapidly construct a path from p to a point on the roadmap. Thus given any two points in S we can rapidly determine whether they lie in the same connected component of S, and if they do, we can return a candidate path between them. We do not give a complete description of the algorithm here, but we define the roadmap geometrically, and verify that it has the necessary connectivity.