A Divide-and-Conquer Articulated-Body Algorithm for Parallel O(log(n)) Calculation of Rigid-Body Dynamics. Part 1: Basic Algorithm

TLDR

The paper introduces a recursive divide‑and‑conquer algorithm for computing forward dynamics of rigid‑body systems on parallel computers, focusing on unbranched kinematic chains in this first part. The algorithm recursively constructs the articulated‑body equations of motion by combining the equations of two independent subassemblies and their connection description, enabling exact, noniterative computation for any joint type or topology. It achieves O(log n) time complexity on O(n) processors, outperforming existing algorithms for systems with many processors and low communication overhead. General‑case details are provided in Part 2.

Abstract

This paper presents a recursive, divide-and-conquer algorithm for calculating 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) processors and is the fastest available algorithm for a computer with a large number of processors and low communications costs. It is an exact, noniterative algorithm and is applicable to mechanisms with any joint type and any topology, including branches and kinematic loops. The algorithm works by recursive application of a formula that constructs the articulatedbody equations of motion of an assembly from those of its constituent parts. The inputs to this formula are the equations of motion of two independent subassemblies, 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 unconnected rigid bodies, the equations of motion of any rigid-body system can be 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. Details of the general case are presented in Part 2.