OBPRM: An Obstacle-Based PRM for 3D Workspaces

Nancy M. Amato
Texas A&M University
amato@cs.tamu.edu
O. Burchan Bayazit
Texas A&M University
burchanb@cs.tamu.edu
Lucia K. Dale
Texas A&M University
dalel@cs.tamu.edu

Christopher Jones
Texas A&M University
cvj3341@cs.tamu.edu
Daniel Vallejo
Texas A&M University
dvallejo@cs.tamu.edu

Abstract

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 of representative paths in C-space (a roadmap) whose vertices correspond to collision-free configurations of the robot and in which two vertices are connected by an edge if a path between the two corresponding configurations can be found by a local planning method.

This work describes and evaluates various node generation and connection strategies for one such PRM, the obstacle-based probabilistic roadmap method (OBPRM), in cluttered 3-dimensional Workspaces. Various node generation strategies are evaluated in terms of their ability to produce nodes in difficult regions of C-space; our results include recommendations for selecting appropriate node generation strategies for different types of objects, and a default strategy for use when objects cannot be classified easily. We also propose and analyze a multi-stage strategy for connecting the roadmap nodes; the use of different local planners at different stages is shown to enhance the connectivity of the resulting roadmap significantly.

In Proceedings of the Workshop on Algorithmic Foundations of Robotics (WAFR'98), pp. 155-168, 1998. Full Paper (postscript)