Optimization techniques for probabilistic roadmaps
Lucia K. Dale, Nancy M. Amato · 2000
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....