Featherstone: ABA, CRBA, and RNEA

Forward dynamics is the simulator's inner loop: given joint torques, solve

$$M(q)\,\ddot q = \tau - C(q,\dot q)\,\dot q - g(q)$$

for $\ddot q$. The question is how expensive that solve has to be.

The cost of doing it naively

The obvious method: build the mass matrix $M(q)$, then factorize the dense $n\times n$ system. Building $M$ with the Composite Rigid Body Algorithm is $O(n^{2})$; factorizing and solving is $O(n^{3})$. For a short arm that is fine. For a long chain it is wasteful, because the structure of a kinematic tree already tells you the answer more cheaply.

O(n) vs O(n³) forward dynamicsinteractive

links n = 20

ABA O(n)

form + solve O(n³)

At n = 20, the dense route does about 400× the work of ABA. CRBA (building M alone) sits in between at O(n²).

The articulated-body algorithm

Featherstone's Articulated-Body Algorithm computes $\ddot q$ in three sweeps over the tree, never forming $M$ explicitly.¹ Written in the spatial-vector notation, each sweep is a short recursion:

1. Outward (base to tips). Propagate link velocities and the velocity-product (bias) terms.
2. Inward (tips to base). Propagate articulated-body inertias and bias forces. This pass is the trick: it summarizes each subtree as an effective inertia its parent feels.
3. Outward again. With those articulated inertias in hand, solve for joint accelerations one link at a time.

Every link is touched a constant number of times, so the whole thing is $O(n)$. The propagation of articulated-body inertias is, in Featherstone and Orin's words, "the secret of the $O(N)$ complexity of the ABA."¹

Its siblings complete the toolkit:² RNEA does inverse dynamics ($\ddot q \to \tau$) in $O(n)$, and CRBA builds the mass matrix itself in $O(n^{2})$ when you actually want $M$ (for a controller, or an operational-space projection).

Why engines care

This recursion is the engine behind minimal-coordinate simulators: MuJoCo, Drake, and RaiSim all live here, and it is exactly the "reduced-coordinate articulation" mode that PhysX and Bullet fall back on for robot models (see the landscape). Two further points make it central: the algorithm is numerically well conditioned (no explicit inverse), and it has closed-form analytic derivatives, also $O(n)$,³ which is what lets these engines feed gradients into optimization and learning.

With state, equations of motion, and a fast way to solve them in hand, Part 3 turns to the other half of the loop: advancing that $\ddot q$ in time without leaking energy.

Footnotes

1. Featherstone & Orin, Robot Dynamics: Equations and Algorithms (ICRA 2000). ↩ ↩²

2. Featherstone, Rigid Body Dynamics Algorithms (Springer, 2008). ↩

3. Carpentier & Mansard, Analytical Derivatives of Rigid Body Dynamics Algorithms (RSS 2018). ↩