On the Fundamental Importance of Gauss-Newton in Motion Optimization

Nathan D. Ratliff, Marc Toussaint, Jeannette Bohg, Stefan SchaalarXiv 2016 · OpenReview

TL;DR

This paper provides theoretical backing for using the Gauss-Newton approximation of the Hessian in motion optimization, showing it converges to the true Hessian for many common objective functions as time discretization becomes finer. This allows for computationally efficient optimization, particularly for complex terms like kinetic energy, by reformulating them to leverage this approximation.

What Problem Does This Paper Address?

Motion optimization, especially for high-degree-of-freedom robots, often relies on efficient Hessian approximations to speed up convergence. While the Gauss-Newton approximation is empirically effective, there's a lack of theoretical understanding about how much accuracy is lost compared to the true Hessian. This gap makes it difficult to design optimal objective functions and understand the trade-offs involved. The paper aims to bridge this gap by analyzing the convergence of the true Hessian to the Gauss-Newton approximation for a broad class of objective terms.

Methods

The core of the paper is a theoretical analysis that proves the convergence of the true Hessian to the Gauss-Newton Hessian for objective terms defined on task-space derivatives. This convergence is shown to be at a rate of $O(\Delta t^{2k})$, where $\Delta t$ is the time discretization and $k$ is the order of the derivatives used.

To leverage this theoretical result, the authors propose:

  • A novel reformulation of rigid body kinetic energy: This reformulation expresses kinetic energy as a squared velocity norm in a higher-dimensional task space. This allows the Gauss-Newton Hessian to efficiently capture the kinetic energy's curvature with computational cost comparable to a single evaluation of the traditional inertia matrix.
  • Cholesky approximations: For cases where explicit task map reformulations are difficult, a technique using Cholesky decompositions of Riemannian metrics is introduced to implicitly approximate the Gauss-Newton Hessian.

Datasets

Not discussed in the paper. The experiments use simulated and real-world robot systems for validation.

Key Insights and Ideas

  • Gauss-Newton is surprisingly good: For many common objective functions in motion optimization (like those involving task-space velocities and accelerations), the Gauss-Newton approximation is not just a heuristic but a theoretically sound approximation that becomes increasingly accurate as the time discretization gets finer.
  • Kinetic energy can be cheap to optimize: By reformulating kinetic energy as a squared velocity norm in a specially constructed task space, its curvature can be efficiently captured by the Gauss-Newton Hessian, avoiding the computationally expensive derivatives of the traditional inertia matrix.
  • Task maps are powerful: The paper highlights the importance of finding appropriate task maps that can simplify complex dynamics and make them amenable to efficient optimization using Gauss-Newton methods. This is further supported by the Nash Embedding Theorem, which suggests that any Riemannian manifold can be mapped to a higher-dimensional Euclidean space.

Key Results

  • Theoretical Convergence: The paper proves that for objective terms involving finite-differenced task-space derivatives, the true Hessian converges to the Gauss-Newton Hessian at a rate of $O(\Delta t^{2k})$. Specifically, velocity terms converge at $O(\Delta t^2)$ and acceleration terms at $O(\Delta t^4)$.
  • Efficient Kinetic Energy: The reformulated kinetic energy using the Rigid Body Inertial Map results in a Gauss-Newton Hessian computation that is as complex as a single evaluation of the traditional inertia matrix, significantly reducing computational burden.
  • Experimental Validation: Experiments on a simulated and a real-world 8-DOF manipulation system demonstrate:
  • The predicted convergence rates of Hessians to Gauss-Newton.
  • The effectiveness of the reformulated kinetic energy and Cholesky approximation for optimization.
  • Successful application of the full motion optimization system for tasks like reach-preshape and obstacle avoidance.

Limitations and Future Work

  • Cholesky Approximation Limitations: The paper acknowledges that the Cholesky approximation can sometimes struggle, especially with larger term weights, and suggests that understanding when it performs well is an area for future work.
  • Finding Task Maps: While the Nash Embedding Theorem guarantees the existence of task maps, finding them for complex scenarios can be challenging. The paper hints at this difficulty in Section 5.
  • Empirical Analysis: The authors suggest that a more extensive empirical analysis of their approach, particularly integrating vision for object localization, would be valuable.
  • Generalization: The theoretical results are primarily for objective terms defined on task-space derivatives. Extending this to other types of objective functions could be a future direction.

Summary updated

Abstract

Hessian information speeds convergence substantially in motion optimization. The better the Hessian approximation the better the convergence. But how good is a given approximation theoretically? How much are we losing? This paper addresses that question and proves that for a particularly popular and empirically strong approximation known as the Gauss-Newton approximation, we actually lose very little--for a large class of highly expressive objective terms, the true Hessian actually limits to the Gauss-Newton Hessian quickly as the trajectory's time discretization becomes small. This result both motivates it's use and offers insight into computationally efficient design. For instance, traditional representations of kinetic energy exploit the generalized inertia matrix whose derivatives are usually difficult to compute. We introduce here a novel reformulation of rigid body kinetic energy designed explicitly for fast and accurate curvature calculation. Our theorem proves that the Gauss-Newton Hessian under this formulation efficiently captures the kinetic energy curvature, but requires only as much computation as a single evaluation of the traditional representation. Additionally, we introduce a technique that exploits these ideas implicitly using Cholesky decompositions for some cases when similar objective terms reformulations exist but may be difficult to find. Our experiments validate these findings and demonstrate their use on a real-world motion optimization system for high-dof motion generation.
BibTeX
@misc{ratliff2016fundamental,
  author = {Nathan D. Ratliff and Marc Toussaint and Jeannette Bohg and Stefan Schaal},
  title = {{On the Fundamental Importance of Gauss-Newton in Motion Optimization}},
  year = {2016},
  eprint = {1605.09296},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1605.09296},
}
Figure