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.

http://i.stanford.edu/pub/cstr/reports/cs/tr/95/1535/CS-TR-95-1535.pdf