A Divide-and-Conquer Articulated-Body Algorithm for Parallel O(log(n)) Calculation of Rigid-Body Dynamics. Part 2: Trees, Loops, and Accuracy

Abstract

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.