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

We propose a truly incremental exact navigation algorithm for general articulated robots: the robot may start with no apriori information about its environment, and is guaranteed to find the goal if it is reachable, or halt otherwise. The algorithm, termed the incremental roadmap algorithm, constructs a roadmap based on distance data collected online and encoded as repulsive potential field. The incremental behavior is achieved with two novel abstract sensors: a critical point detector and a minimum passage detector. We show by examples which environmental features must be measured by the detectors for a planar-body robot