A general framework for PRM motion planning

An important property of PRM roadmaps is that they provide a good approximation of the connectivity of the free C-space. We present a general framework for building and querying probabilistic roadmaps that includes all previous PRM variants as special cases. In particular, it supports no, complete, or partial node and edge validation and various evaluation schedules for path validation, and it enables path customization for variable, adaptive query requirements. While each of the above features is present in some PRM variant, the general framework proposed here is the only one to include them all. Our framework enables users to choose the best approximation level for their problem. Our experimental evidence shows this can result in significant performance gains.

1 Introduction

Probabilistic Roadmap (PRM) motion planning methods have been the subject of much recent work. These methods create a graph of randomly generated collision-free configurations which are connected by a simple and fast local planning method. Actual global planning (queries) is carried out on this graph. The initial PRMs were shown to be very successful in solving difficult problems in high-dimensional configuration spaces (C-space) that had previously resisted efficient solution [16]. These successes motivated the application of PRMs to challenging problems arising in a variety of fields including robotics (e.g., closed-chain systems 114, 19]), CAD (e.g., maintainability [6], [11], deformable objects [2], [5], [15]), and even computational Biology and Chemistry (e.g., ligand docking [7], [22], protein folding [3], [23], [24]). Indeed, it can be argued that the PRM framework was instrumental in this broadening of the range of applicability of motion planning, as many of these problems had never before been considered candidates for automatic methods.