Numerical convolution on the Euclidean group with applications to workspace generation

In this work, the concept of a convolution product of real-valued functions on the special Euclidean group, SE(D) (which describes all rigid body motions in D-dimensional Euclidean space), is applied to the determination of workspaces of discretely actuated manipulators. These manipulators have a finite number of joint states. If a discretely actuated manipulator consists of P actuated modules, each with K states, then it can reach K/sup p/ frames in space. Given this exponential growth in the number of reachable frames, brute force representation of discretely actuated manipulator workspaces is not feasible in the highly actuated case. However, by partitioning a discretely actuated manipulator into P modules, and approximating the workspace of each module as a density function on a compact subset of the special Euclidean group, the whole workspace can be approximated as an P-fold convolution of these densities. A numerical approximation of this convolution is presented in this paper which is O(P) for fixed taskspace dimension. In the special case when the manipulator is composed of P identical actuated modules, the workspace density for the whole manipulator can be calculated in O(log P) computation time. In either case, the O(K/sup p/) computations required by brute force workspace generation are avoided.