Computation of configuration-space obstacles using the fast Fourier transform

A method is proposed for computing the configuration-space map of obstacles. The map is used in motion-planning algorithms. The method derives from the observation that, when the robot is a rigid object that can only translate, the configuration space is a convolution of the workspace and the robot. It makes use of the fast Fourier transform (FFT) algorithm to compute this convolution. The method is particularly promising for workspaces with many and/or complicated obstacles, or when the shape of the robot is not simple. It is an inherently parallel method, and it can significantly benefit from existing experience and hardware on the FFT