Construction of C-space roadmaps from local sensory data. What should the sensors look for?

This paper presents an incremental navigation strategy for general articulated robots: the robot may start with no a priori information about its environment, and is guaranteed either to find the goal if it is reachable or hair. The strategy, termed the incremental roadmap algorithm, constructs a roadmap based on on-line distance data which is encoded as a repulsive potential field. The incremental behavior is achieved with two novel abstract sensors: the critical-point detector and the passage-point detector. The detectors provide a complete characterization of what the robot should look for in its configuration space to achieve globally convergent navigation. The approach thus provides a new framework, which will hopefully yield the first navigation algorithm that is both completely general and practical.