Constructing roadmaps of semi-algebraic sets. I: Completeness (Q1117992)

Both collision-free motion of a robot arm and of the free polyhedron can be described in so-called configuration space. Physical obstacles are represented as forbidden regions, and collision-free motion is given by paths avoiding these regions. This paper indicates how to construct a one-dimensional subset C - the roadmap - in the set of allowable configurations S, so that every connected component of S contains exactly one connected component of C. - The author intends to describe an algorithm which uses the roadmap to decide whether two points in S belong to the same connected component and, if so, constructs a path between them, using the roadmap.