TABLE OF CONTENTS Alexander B. Kyatkin, Johns Hopkins University, Maryland, USA
Gregory S. Chirikjian, Johns Hopkins University, Maryland, USA
In this paper we develop and apply a fast Fourier transform on the "discrete motion group" to the problem of computing the configuration space obstacles of mobile robots and the problem of finding the workspace density of discretely actuated manipulators with many states. Fast transforms allow us to compute efficiently convolution-like integrals that arise in robot kinematics and motion planning. The results of the implementation are discussed for particular examples.
In this paper we address two problems in robotics which may be solved using similar mathematical tools: (1) the problem of computing the configuration space obstacles of mobile robots which move in a static environment; (2) the problem of computing the workspaces of discretely actuated m-link revolute manipulators. Both of these problems may be posed as convolutions on the Euclidean motion group. [1] SE( n) can be viewed as the set of all ( n + 1) ( n + 1) homogeneous transform matrices of the form
where R ? SO( n) (i.e., R is an n n proper orthogonal matrix: RR T = 1 and det( R) = +1), 
, and the group operation is matrix multiplication of two homogeneous transform matrices. For the case of rigid body motion in the plane the homogeneous transforms take the simple form
A particularly useful subgroup of SE(2) is the one...
