Featherstone's algorithm for simulating articulated bodies

Featherstone's method allows the fast simulation of the dynamics of a tree-like chain of N articulated links in a computational time linearly proportional with N.

One alternative to this method is the use of elastic penalty forces to enforce constraints, an option with obvious problems. Another alternative to the Featherstone algorithm is the Witkin/Baraff Lagrange multiplier approach. It has the advantages that it is modular, easy to implement, and it allows adding constraints at run-time. It also has the disadvantages that it is slower and it operates in Cartesian space, dealing with link positions and orientations instead of the more intuitive joint space of reduced coordinates that deals directly with the joint angles. As a result, common tasks such as evaluating joint angles and velocities, enforcing joint limits, and even applying internal torques to achieve a specific motion require awkward conversions between the two spaces. Additionally, inaccuracy in numerical integration can cause links to drift apart leaving the articulated body in an invalid state. Thus, Featherstone's method seems to be more suitable in many situations.

The derivation and implementation of the Featherstone's algorithm requires some complex notations, and because of that many people find it hard to understand. I needed myself a few weeks of full time work to fully understand Featherstone's method and its derivation. It seems that the alternative (Lagrange multiplier) approach was derived by Baraff because he could not understand Featherstone's method (reference). Another top expert in computer simulation, the creator of the ODE physics SDK, believes that "contact & friction modelling with a Featherstone method either require springs & dampers (bad for speed and stability), or a hybrid reduced coordinate / cartesian coordinate approach (tricky to implement)" (reference). In fact, this is not true, and this is proved by the integration of the Featherstone method with contact resolution in Thyrix and by this paper by Kokkevis.

Here are some links to papers available online that present Featherstone's articulated body method:

Featherstone, D. and Orin, D. E. (2000). Robot Dynamics: Equations and Algorithms. IEEE Int. Conf. Robotics & Automation, pp. 826-834.

Fontijne, D. (2000), Rigid Body Simulation and Evolution of Virtual Creatures, M.S. Thesis, University of Amsterdam.

Kokkevis E. (2004), Practical Physics for Articulated Characters, Game Developers Conference 2004.

McMillan, S. (1994), Computational dynamics for robotic systems on land and under water, Ph.D. Thesis, The Ohio State University, Columbus, OH.

McMillan, S., Orin, D. E. and McGhee, R. B. (1995a), Dynamechs: An object oriented software package for efficient dynamic simulation of underwater robotic vehicles, in J. Yuh, ed., ‘Underwater Robotic Vehicles: Design and Control’, TSI Press, pp. 73–98.

McMillan, S., Orin, D. E. and McGhee, R. B. (1995b), ‘Efficient dynamic simulation of an underwater vehicle with a robotic manipulator’, IEEE Transactions on Robotics and Automation pp. 606–611.

McMillan, S., Orin, D. E. and McGhee, R. B. (1996), ‘A computational framework for simulation of underwater robotic vehicle systems’, Journal of Autonomous Robots 3, 253–268.

Mirtich, B. (1996), 'Impulse based Dynamic Simulation of Rigid Body Systems', PhD Thesis, University of California at Berkeley.

Pai, D. K., Ascher, U. M., and Kry, P. G. (2000). Forward dynamics algorithms for multibody chains and contact. In IEEE International Conference on Robotics and Automation, pp. 857-863.

Razvan Florian, July 27, 2005