Robot Dynamics: Equations and Algorithms

Roy Featherstone, David Orin

IEEE International Conference on Robotics and Automation

Pages 826-834, 2000

Motivation

There has been a great deal of work in robot dynamics, the earliest being before 1980. Much of this work is applicable to a wide range of fields, even outside of robotics.

The goal is to identify major contributions in robot dynamics as of the year 2000, especially efficient low-order algorithms for inverse dynamics, forward dynamics, and computation of the inertia matrix of a system.

Goal of This Paper

This paper presents three algorithms for robots with a tree structure:

Recursive Newton-Euler Algorithm: Given the velocity and acceleration of the base of the robot, the velocity and acceleration of each link is computed, working outward from the base to the terminal links. The force transmitted through each link is then computed working backward from the terminal links to the base. The force in each joint is computed from all of this information.
Composite-Rigid-Body Algorithm: The joint-space inertia matrix of a system is computed column-by-column in an efficient manner by computing the forces in the system resulting from unit accelerations to each joint. The forces transmitted through each joint are then computed using the inertia matrix.
Articulated-Body Algorithm: The accelerations of bodies in a rigid-body system are always affine functions of the applied forces. If the chosen body's motion is unconstrained, this can be inverted to write the applied forces as an affine function of the accelerations. The coefficient and translation in this affine equation can be computed for each link starting from the terminal links and working toward the base. Then the forces can be computed using this affine equation.

Then two other topics are discussed:

Closed-loop systems: First, a spanning tree of the connectivity graph for the robot is extracted. The equations of motion are computed for the spanning tree using methods for open-loop systems. Then loop-closure forces are added to mimic the effects of the closed loops, and the system is solved using open-loop techniques.
Global analysis techniques: The spatial operator algebra is used to compactly represent an entire rigid-body system using very few variables. The resulting unified framework is described in which the RNEA and ABA are simply variations of the same basic approach.

Related Work

[7] and [11] are early books referencing the extensive work in robot dynamics.

The classical approach to expression the equations of motion were based on a Lagrangian formulation [18] [31], but these led to O(N⁴) algorithms. The first O(N) algorithms for inverse dynamics for robotics used a Newton-Euler formulation [30] [26]. The most cited O(N) algorithm is the Recursive Newton-Euler Algorithm (RNEA) [23]. A recursive Lagrangian O(N) formulation was found to be slower than RNEA [16]. Speedups of RNEA up to a factor of 1.7 for a six-degree-of-freedom robot have since been developed [4] [15].

RNEA was used to develop the Composite-Rigid-Body Algorithm (CRBA) for forward dynamics, which runs in O(N³) time [33], which was quite efficient for small N . The efficiency is directly related to the efficiency of computing the inertia matrix. Further improvements [11] [3] [25] have led to a speedup of roughly a factor of two. The Modified Composite Rigid Body Algorithm is very efficient for computing the inertia matrix in operational space [22].

Dynamic programming was used to develop the earliest known O(N) algorithm for forward dynamics [32]. This algorithm was similar to the Articulated-Body Algorithm (ABA), but it lay in obscurity for a decade. An O(N) algorithm was developed for mechanisms with spherical joints [1] and then the ABA was developed [10] for manipulators with single-degree-of-freedom joints, followed by a version that included a general joint model and was faster [11]. [8] made further improvements to make the ABA comparable to the CRBA for N = 6 . More improvements have been made to the ABA [24].

An operational-space formulation of robot dynamics [20] has been useful in hybrid motion/force control and related applications [21]. The spatial operator algebra was developed using parallels between Kalman filtering and forward dynamics [28]. This allowed alternative factorizations of the inertia matrix to derive the ABA [29]. It also was used to develop a unified formulation for manipulator dynamics [17]. The spatial operator framework was used to show that both the CRBA and the ABA are two elimination methods to solve the same linear system [2]. The current version of spatial algebra (in which linear and angular components of quantities like velocity are expressed compactly as 6 x 1 vectors) is briefly described in the appendix of [12], and a detailed description of the previous version is given in [11].

An efficient recursive Lagrangian formulation of both inverse and forward dynamics for serial chains with flexible links (as opposed to rigid links as assumed by the above algorithms) was developed [6].

Systems with closed kinematic loops are more complicated than the tree-structure systems discussed above and are discussed at length in [27] and [34].

Exploiting the sparsity of matrices used in forward dynamics for kinematic trees yields an O(N) forward dynamics algorithm [5]. For the special case of an unbranched chain, an O(log(N)) algorithm exists for a parallel computer with O(N) processors, which is the key step in the Constraint-Force Algorithm [14] [13].

Results

No results are obtained in this paper.

What This Paper Contributes

This paper reviews important algorithms developed for inverse dynamics, forward dynamics, and inertia matrix computation for robotics, and shows how reduction of computational costs and simplicity of manipulation have been key in the development and effectiveness of these algorithms.

What This Paper Does Not Contribute

This paper does not discuss several important topics in robot dynamics, including:

Automatic generation and simplification of symbolic equations of motion
Algorithms for parallel computers
Kane's equations [19]

Bibliography

1: W. W. Armstrong.
Recursive solution to the equations of motion of an n-link manipulator.
In Proceedings of the 5th World Congress on Theory of Machines and Mechanisms, pages 1343-1346, 1979.
2: U. M. Ascher, D. K. Pai, and B. P. Cloutier.
Forward dynamics, elimination methods, and formulation stiffness in robot simulation.
International Journal of Robotics Research, 16(6):749-758, 1997.
3: C. A. Balafoutis and R. V. Patel.
Efficient computation of manipulator inertia matrices and the direct dynamics problem.
IEEE Transactions on Systems, Man, and Cybernetics, 19:1313-1321, 1989.
4: C. A. Balafoutis, R. V. Patel, and P. Misra.
Efficient modeling and computation of manipulator dynamics using orthogonal cartesian tensors.
IEEE Journal of Robotics and Automation, 4:665-676, 1988.
5: D. Baraff.
Linear-time dynamics using lagrange multipliers.
Computer Graphics (SIGGRAPH), pages 137-146, 1996.
Summary available .
6: W. J. Book.
Recursive lagrangian dynamics of flexible manipulator arms.
International Journal of Robotics Research, 3(3):87-101, 1984.
7: M. Brady, J. M. Hollerbach, T. L. Johnson, T. Lozano-Perez, and M. T. Mason.
Robot Motion: Planning and Control.
MIT Press, 1982.
8: H. Brandl, R. Johanni, and M. Otter.
A very efficient algorithm for the simulation of robots and similar multibody systems without inversion of the mass matrix.
In Proceedings of the IFAC/IFIP/IMACS International Symposium on Theory of Robots, pages 95-100, 1986.
9: R. E. Ellis and S. L. Ricker.
Two numerical issues in simulating constrained robot dynamics.
IEEE Transactions on Systems, Man, and Cybernetics, 24(1):19-27, 1994.
10: R. Featherstone.
The calculation of robot dynamics using articulated-body inertias.
International Journal of Robotics Research, 2(1):13-30, 1983.
11: R. Featherstone.
Robot Dynamics Algorithms.
Kluwer Academic Publishers, 1987.
12: R. Featherstone.
A divide-and-conquer articulated body algorithm for parallel o(log(n)) calculation of rigid body dynamics, part 1: Basic algorithm.
International Journal of Robotics Research, 18(9):867-875, 1999.
13: R. Featherstone and A. Fijany.
A technique for analyzing constrained rigid-body systems and its application to the constraint force algorithm.
IEEE Transactions on Robotics and Automation, 15(6):1140-1144, 1999.
14: A. Fijany, I. Sharf, and G. M. T. D'Eleuterio.
Parallel o(log(n)) algorithms for computation of manipulator forward dynamics.
IEEE Transactions on Robotics and Automation, 11(3):389-400, 1995.
15: X. He and A. A. Goldenberg.
An algorithm for efficient computation of dynamics of robotic manipulators.
In Proceedings of the Fourth International Conference on Advanced Robotics, pages 175-188, 1989.
16: J. Hollerbach.
A recursive lagrangian formulation of manipulator dynamics and a comparative study of dynamics formulation complexity.
IEEE Transactions on Systems, Man, and Cybernetics, SMC-10(11):730-736, 1980.
17: A. Jain.
Unified formulation of dynamics for serial rigid multibody systems.
Journal of Guidance, Control, and Dynamics, 14(3):531-542, 1991.
18: M. E. Kahn and B. Roth.
The near minimum-time control of open-loop articulated kinematic chains.
Journal of Dynamic Systems, Measurement, and Control, 93:164-172, 1971.
19: T. R. Kane and D. A. Levinson.
The use of kane's dynamical equations in robotics.
International Journal of Robotics Research, 2(3):3-21, 1983.
20: O. Khatib.
A unified approach to motion and force control of robot manipulators: The operational space formulation.
IEEE Journal of Robotics and Automation, 3(1):43-53, 1987.
21: O. Khatib.
Inertial properties in robotic manipulation: An object-level framework.
International Journal of Robotics Research, 14(1):19-36, 1995.
22: K. W. Lilly and D. E. Orin.
Alternate formulations for the manipulator inertia matrix.
International Journal of Robotics Research, 10:64-74, 1991.
23: J. Y. S. Luh, M. W. Walker, and R. P. C. Paul.
On-line computational scheme for mechanical manipulators.
Transactions of the ASME, Journal of Dynamic Systems, Measurement and Control, 102(2):69-76, 1980.
24: S. McMillan and D. E. Orin.
Efficient computation of articulated-body inertias using successive axial screws.
IEEE Transactions on Robotics and Automation, 11:606-611, 1995.
25: S. McMillan and D. E. Orin.
Forward dynamics of multilegged vehicles using the composite rigid body method.
In Proceedings of the IEEE International Conference on Robotics and Automation, pages 464-470, 1998.
26: D. E. Orin, R. B. McGhee, M. Vukobratovic, and G. Hartoch.
Kinematic and kinetic analysis of open-chain linkages utilizing newton-euler methods.
Mathematical Biosciences, 43:107-130, 1979.
27: R. E. Roberson and R. Schwertassek.
Dynamics of Multibody Systems.
Springer-Verlag, 1988.
28: G. Rodriguez.
Kalman filtering, smoothing, and recursive robot arm forward and inverse dynamics.
IEEE Journal on Robotics and Automation, RA-3(6):624-639, 1987.
29: G. Rodriguez, A. Jain, and K. Kreutz-Delgado.
Spatial operator algebra for manipulator modelling and control.
International Journal of Robotics Research, 10(4):371-381, 1991.
30: Y. Stepanenko and M. Vukobratovic.
Dynamics of articulated open-chain active mechanisms.
Mathematical Biosciences, 28:137-170, 1976.
31: J. J. Uicker.
Dynamic force analysis of spatial linkages.
Transactions of the ASME Journal of Applied Mechanics, 34:418-424, 1967.
32: A. F. Vereshchagin.
Computer simulation of the dynamics of complicated mechanisms of robot manipulators.
Engineering Cybernetics, 6:65-70, 1974.
33: M. W. Walker and D. E. Orin.
Efficient dynamic computer simulation of robotic mechanisms.
Transactions of the ASME, Journal of Dynamic Systems, Measurement and Control, 104:205-211, 1982.
34: J. Wittenburg.
Dynamics of Systems of Rigid Bodies.
B. G. Teubner, 1977.

ctj