Random Networks in Configuration Space for Fast Path Planning

摘要

In the main part of this dissertation we present a new path planning method whichcomputes 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 second part of this dissertation, we present a new method for computing the obstacle map used in motion planning algorithms. The method, which is practical only for two-dimensional workspaces, computes a convolution of the workspace and the robot with the use of the Fast Fourier Transform (FFT). It is particularly promising for workspaces with many and/or complicated obstacles, or when the shape of the robot is not simple. Futhermore, it is an inherently parallel method that can significantly benefit from existing experience and hardware on the FFT. In the third part, we consider a problem from assembly planning. In assembly planning we are interested in generating feasible sequences of motions that construct a mechanical product or take it apart to its individual parts.