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, divide-and-conquer algorithm for calculating the forward dynamics of a robot mechanism, or a general rigid-body system, on a parallel computer This paper presents the general version of the algorithm. The derivation begins with an algorithm for kinematic trees, which is then extended to closed-loop systems. The general algorithm achieves O(log(n)) time complexity on O(n) processors 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 results of some numerical accuracy tests that compare both versions with the standard articulated-body algorithm. The tests use rigid-body systems containing up to 1024 bodies, and they show that the divide-and-conquer algorithm is substantially less accurate than the best serial algorithm but still accurate enough to be useful.