ABSTRACT
Probabilistic roadmap methods have recently received considerable attention as a practical approach for mo tion planning in complex environments. These algo rithms sample a number of configurations in the free space and build a roadmap. Their performance varies as a function of the sampling strategies and relative configurations of the obstacles. To improve the perfor mance of the planner through narrow passages in con figuration space, some researchers have proposed algo rithms for sampling along or near the medial axis of the free space. However, their usage has been limited be cause of the practical complexity of computing the me dial axis or the cost of computing such samples.