R. Featherstone, A divide-and-conquer articulated-body algorithm for parallel O(log(n)) calculation of rigid-body dynamics. Part 2: Trees, loops, and accuracy, INT J ROB R, 18(9), 1999, pp. 876-892
This paper is the second in a two-part series describing a recursive, divid
e-and-conquer algorithm for calculating the forward dynamics of a robot mec
hanism, or a general rigid-body system, on a parallel computer This paper p
resents the general version of the algorithm. The derivation begins with an
algorithm for kinematic trees, which is then extended to closed-loop syste
ms. The general algorithm achieves O(log(n)) time complexity on O(n) proces
sors for all kinematic trees and a large subset of closed-loop systems.
This paper also presents a more accurate version of the algorithm and the r
esults of some numerical accuracy tests that compare both versions with the
standard articulated-body algorithm. The tests use rigid-body systems cont
aining up to 1024 bodies, and they show that the divide-and-conquer algorit
hm is substantially less accurate than the best serial algorithm but still
accurate enough to be useful.