Report Number: CS-TR-95-1535
Institution: Stanford University, Department of Computer Science
Title: Random Networks in Configuration Space for Fast Path Planning
Author: Kavraki, Lydia E.
Date: January 1995
Abstract: In the main part of this dissertation we present a new path
planning method which computes collision-free paths for
robots of virtually any type moving among stationary
obstacles. This method proceeds according to two phases: a
preprocessing phase and a query phase. In the preprocessing
phase, a probabilistic network is constructed and stored as a
graph whose nodes correspond to collision-free configurations
and edges to feasible paths between these configurations. In
the query phase, any given start and goal configurations of
the robot are connected to two nodes of the network; the
network is then searched for a path joining these two nodes.
We apply our method to 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 ($\approx$ 150 MIPS), after relatively short
preprocessing times (a few dozen to a few hundred seconds).
In the second part of this dissertation, we present a new
method that uses the the Fast Fourier Transform to compute
the obstacle map required by certain path planning
algorithms. In the final part of this dissertation, we
consider a problem from assembly planning. In assembly
planning we are interested in generating feasible sequences
of motions that construct a mechanical product from its
individual parts. We prove that the monotone assembly
partitioning problem in the plane is NP-complete.