Random networks in configuration space for fast path planning

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. These paths are computed using a fast local planner. 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. The method is general and easy to implement. Increased efficiency can be achieved by tailoring some of its components (e.g. the local planner) to the considered robots. We apply the 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 ({dollar}approx{dollar}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 for computing the obstacle map used in motion planning algorithms. The method computes a convolution of the workspace and the robot using the Fast Fourier Transform (FFT). It is particularly promising for workspaces with many and/or complicated obstacles. Furthermore, it is an inherently parallel method that can significantly benefit from existing experience and hardware on the FFT.; In the third 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. The problem addressed is the following: given a planar assembly of polygons, decide if there is a proper subcollection of them that can be removed as a rigid body without colliding with or disturbing the other parts of the assembly. We prove that this problem is NP-complete. The result extends to several interesting variants of the problem.