David Hsu, Stanford University, Stanford, CA, USA
Lydia E. Kavraki, Rice University, Houston, TX, USA
Jean-Claude Latombe, Stanford University, Stanford, CA, USA
Rajeev Motwani, Stanford University, Stanford, CA, USA
Stephen Sorkin, Stanford University, Stanford, CA, USA

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 unusually difficult path-planning problems, but their efficiency remains disappointing when the free space contains narrow passages. This paper provides foundations for understanding the effect of passages on the connectedness of probabilistic roadmaps. It also proposes a new random sampling scheme for finding such passages. 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.