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 a...

Full description

Saved in:
Bibliographic Details
Published in:The International journal of robotics research 1999-09, Vol.18 (9), p.876-892
Main Author: Featherstone, Roy
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0278-3649
1741-3176
DOI:10.1177/02783649922066628