R. Featherstone, A divide-and-conquer articulated-body algorithm for parallel O(log(n)) calculation of rigid-body dynamics. Part 1: Basic algorithm, INT J ROB R, 18(9), 1999, pp. 867-875
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.