  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(n^3)$ 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.
