|
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 |
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)