Report Number: CS-TR-94-1519
Institution: Stanford University, Department of Computer Science
Title: Probabilistic Roadmaps for Path Planning in High-Dimensional
Configuration Spaces
Author: Kavraki, Lydia
Author: Svestka, Petr
Author: Latombe, Jean-Claude
Author: Overmars, Mark
Date: August 1994
Abstract: A new motion planning method for robots in static workspaces
is presented. This method proceeds according to two phases: a
learning phase and a query phase. In the learning phase, a
probabilistic roadmap is constructed and stored as a graph
whose nodes correspond to collision-free configurations and
edges to feasible paths between these configurations. These
paths are computed using a simple and fast local planner. In
the query phase, any given start and goal configurations of
the robot are connected to two nodes of the roadmap; the
roadmap is then searched for a path joining these two nodes.
The method is general and easy to implement. It can be
applied to virtually any type of holonomic robot. It requires
selecting certain parameters (e.g., the duration of the
learning phase) whose values depend on the considered scenes,
that is the robots and their workspaces. But these values
turn out to be relatively easy to choose. Increased
efficiency can also be achieved by tailoring some components
of the method (e.g., the local planner) to the considered
robots. In this paper the method is applied to planar
articulated robots with many degrees of freedom. Experimental
results show that path planning can be done in a fraction of
a second on a contemporary workstation (approximately 150
MIPS), after learning for relatively short periods of time (a
few dozen seconds).
http://i.stanford.edu/pub/cstr/reports/cs/tr/94/1519/CS-TR-94-1519.pdf