A divide-and-conquer articulated-body algorithm for parallel O(log(n)) calculation of rigid-body dynamics. Part 1: Basic algorithm

This paper presents a recursive, divide-and-conquer algorithm for calculati ng the forward dynamics of a robot mechanism, or general rigid-body system, on a parallel computer: It features O(log(n)) time complexity on O(n) proc essors and is the fastest available algorithm for a computer with a large n umber of processors and low communications costs. It is an exact, noniterat ive algorithm and is applicable to mechanisms with any joint type and any t opology, including branches and kinematic loops. The algorithm works by rec ursive application of a formula that constructs the articulated body equati ons of motion of an assembly from those of its constituent parts. The input s to this formula are the equations of motion of two independent subassembl ies, plus a description of how they are to be connected, and the output is the equation of motion of the assembly. Starting with a collection of uncon nected rigid bodies, the equations of motion of any rigid-body system can b e constructed by repeated application of this formula. This paper being the first in a two-part series, presents an overview of the new algorithm and a detailed description of the simplest case: unbranched kinematic chains. D etails of the general case are presented in Part 2.