Recently, a new class of randomized path planning methods, known as Probabilistic Roadmap Methods (PRMs) have shown great potential for solving complicated high-dimensional problems. PRMs use randomization (usually during preprocessing) to construct a graph (a roadmap) of representative paths in the robot's con guration space. Vertices correspond to collision-free con gurations of the robot. An edge exists between two vertices if a path between the two corresponding con gurations can be found by a local planning method.

PRMs solve many high degree of freedom (dof) motion planning problems. Unfortunately, for some problems running times may still be unacceptably large and solutions sub-optimal. We provide speed and quality optimization strategies applicable in cluttered 3-dimensional workspaces. Speed improvements for roadmap construction are accomplished by parallel processing and faster failure detection techniques. Quality improvements for the roadmap constructed are accomplished by new roadmap building methods which result in roadmaps that better represent the connectivity of the free con guration space. Quality is also improved by building roadmaps iteratively using information gained at each iteration to control and drive following iterations. Since there is no single generally accepted way of judging roadmap quality, several measures are considered.