ABSTRACT
A probabilistic roadmap is a network of simple paths connecting collision-free configurations obtained by sampling a robot’s configuration space at random. Several probabilistic roadmap planners have solved un usually difficult path-planning problems, but their effi ciency remains disappointing when the free space con tains narrow passages. This paper provides foundations for understanding the effect of passages on the con nectedness of probabilistic roadmaps. It also proposes a new random sampling scheme for finding such pas sages. An initial roadmap is built in a “dilated” free space allowing some penetration distance of the robot into the obstacles. This roadmap is then modified by resampling around the links that do not lie in the true free space. Experiments show that this strategy allows relatively small roadmaps to reliably capture the free space connectivity.
