Carnegie Mellon University
The
A Linear-Time Variational Integrator for Multibody Systems

Jeongseok Lee, C. Karen Liu, Frank C. Park, and Siddhartha Srinivasa
The 12th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2016), September, 2016.


Download
  • Adobe portable document format (pdf) (376KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
We present an efficient variational integrator for multibody systems. Variational integrators reformulate the equations of motion for multibody systems as discrete Euler-Lagrange (DEL) equations, transforming forward integration into a root-finding problem for the DEL equations. Variational integrators have been shown to be more robust and accurate in preserving fundamental properties of systems, such as momentum and energy, than many frequently used numerical integrators. However, state-of-the-art algorithms suffer from O(n3) complexity, which is prohibitive for articulated multibody systems with a large number of degrees of freedom, n, in generalized coordinates. Our key contribution is to derive a recursive algorithm that evaluates DEL equations in O(n), which scales up well for complex multibody systems such as humanoid robots. Inspired by recursive Newton-Euler algorithm, our key insight is to formulate DEL equation individually for each body rather than for the entire system. Furthermore, we introduce a new quasi-Newton method that exploits the impulse-based dynamics algorithm, which is also O(n), to avoid the expensive Jacobian inversion in solving DEL equations. We demonstrate scalability and efficiency, as well as extensibility to holonomic constraints through several case studies.

Keywords
variational integrator, discrete mechanics, multibody systems, dynamics, computer animation & simulation

Notes
Associated Center(s) / Consortia: Quality of Life Technology Center, National Robotics Engineering Center, and Center for the Foundations of Robotics
Associated Lab(s) / Group(s): Personal Robotics
Note: This is a preprint version that is uploaded to arXiv (https://arxiv.org/abs/1609.02898).

Text Reference
Jeongseok Lee, C. Karen Liu, Frank C. Park, and Siddhartha Srinivasa, "A Linear-Time Variational Integrator for Multibody Systems," The 12th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2016), September, 2016.

BibTeX Reference
@inproceedings{Lee_2016_8219,
   author = "Jeongseok Lee and C. Karen Liu and Frank C. Park and Siddhartha Srinivasa",
   title = "A Linear-Time Variational Integrator for Multibody Systems",
   booktitle = "The 12th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2016)",
   month = "September",
   year = "2016",
   Notes = "This is a preprint version that is uploaded to arXiv (https://arxiv.org/abs/1609.02898)."
}