OBPRM: An Obstacle-Based PRM for 3D Workspaces

Abstract

Recently, a new class of randomized p ath 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 c on gurations of the robot and in which two vertices are c onnected b y an edge if a path between the two corresponding con gurations 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 p r obabilistic roadmap method obprm, in cluttered 3-dimensional Workspaces.Various node generation strategies are evaluated in terms of their ability to produce n o des in di cult regions of C-space; our results include recommendations for selecting appropriate node generation strategies for di erent types of objects, and a default strategy for use when objects cannot be classi ed e asily.We also propose and analyze a multi-stage strategy for connecting the roadmap nodes; the use of di erent local planners at di erent stages is shown to enhance the connectivity of the resulting roadmap signi cantly.