A divide-and-conquer articulated-body algorithm for parallel O(log(n)) calculation of rigid-body dynamics. Part 2: Trees, loops, and accuracy

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.