Stagewise Newton Method for Dynamic Game Control With Imperfect State Observation

Armand Jordana, Bilal Hammoud, Justin Carpentier, Ludovic Righetti

TL;DR

This paper introduces a computationally efficient, iterative algorithm for solving dynamic games where the state of the system is not perfectly known. By combining minimax Differential Dynamic Programming (DDP) with a risk-sensitive Kalman smoother into a unified "Stagewise Newton Method," the authors achieve linear complexity relative to the time horizon, making robust, "worst-case" planning feasible for high-frequency robotic control.

What Problem Does This Paper Address?

In traditional robotics, we often separate estimation (figuring out where the robot is) from control (deciding where it should go). This "certainty equivalence" approach works well until things get messy—like when sensors are noisy or disturbances are unpredictable.

Dynamic game control offers a more robust alternative: it treats disturbances as an "adversarial player" and looks for a Nash equilibrium where the controller minimizes cost while the adversary tries to maximize it. However, solving these minimax problems for nonlinear systems with imperfect observations is notoriously difficult. Previous methods were either too slow for real-time use (like interior-point methods) or lacked theoretical convergence guarantees. This paper aims to bridge that gap with an algorithm that is both fast and provably convergent.

Methods

The authors derive a Stagewise Newton Method specifically tailored for this minimax formulation. The key technical contribution is exploiting the temporal sparsity of the problem's Hessian matrix to ensure the computational cost only grows linearly with the time horizon ($O(T)$), rather than cubically ($O(T^3)$).

The algorithm operates through three main components:

  1. Future Stress Recursion: A backward pass (similar to DDP or LQR) that calculates how future control actions should respond to state changes.
  2. Past Stress Recursion: A forward pass (resembling a risk-sensitive Kalman Filter) that updates the state estimate based on past measurements and disturbances.
  3. Coupling Equation: A unique step that links the estimation and control passes, ensuring the final control command explicitly accounts for the uncertainty in the estimate.

To ensure the solver doesn't diverge on complex nonlinear landscapes, the authors introduce a merit function and a line search procedure, providing a global convergence guarantee to a local Nash equilibrium.

Datasets

The paper evaluates the algorithm using two simulated robotic benchmarks:

  • Planar Quadrotor: A 6D state-space model where the drone must navigate to a target while avoiding an obstacle represented by a high-cost exponential field.
  • KUKA LWR iiwa Robot: A 7-Degree-of-Freedom (DoF) industrial manipulator with a 14D state space. This test demonstrates the algorithm's ability to scale to high-dimensional systems typical of modern industrial robotics.

Key Insights and Ideas

  • Unification of Estimation and Control: The method shows that risk-sensitive smoothing and minimax control are two sides of the same coin. The "coupling" step is the "aha moment" where the controller's awareness of its own ignorance (estimation error) directly influences its physical actions.
  • Linear Complexity is Key: By structuring the Newton step as a series of recursions, the authors prove you don't need to invert massive matrices to get the benefits of a second-order optimization method.
  • Risk-Sensitivity as a Limit: The authors highlight that dynamic game control can be viewed as the limit of risk-sensitive control as noise tends to zero. This provides a bridge between stochastic and deterministic robust control.
  • Generalization: The framework is highly general; if you set the sensitivity parameter ($\mu$) to zero, you recover standard DDP and iterative Kalman smoothing.

Key Results

  • Risk-Averse Behavior: In the quadrotor simulations, the "dynamic game" controller chose trajectories significantly further from obstacles than a "neutral" controller. It effectively "planned for the worst," assuming disturbances might push it toward the danger zone.
  • Robustness to Noise: In closed-loop simulations with Gaussian noise, the proposed controller maintained a larger safety margin, resulting in fewer "near-misses" with obstacles.
  • Scalability: The KUKA robot experiment showed that the solver could handle 14 states and 7 control inputs efficiently. The controller demonstrated a "cautious" approach, slowing down the reaching task to account for potential estimation errors.
  • Convergence: The inclusion of the merit function allowed the solver to converge reliably even when the initial guess was far from the solution.

Limitations and Future Work

  • The Sensitivity Limit: There is a maximum value for the sensitivity parameter $\mu$. If $\mu$ is too high, the "adversary" becomes too powerful, and the problem becomes ill-defined (the Hessian is no longer positive-definite). The authors note this limit but do not provide a general way to calculate it for nonlinear systems.
  • Second-Order Derivatives: The method ideally requires second-order derivatives of the system dynamics. For the KUKA robot, the authors approximated these as zero (a common "Gauss-Newton" style simplification). While it worked, a full second-order implementation might offer even faster convergence at a higher computational cost.
  • Real-Time MPC: While the complexity is linear, the next step is implementing this in a true real-time Model Predictive Control (MPC) loop on physical hardware to see how it handles sub-millisecond constraints.

Summary updated

Abstract

In this letter, we study dynamic game optimal control with imperfect state observations and introduce an iterative method to find a local Nash equilibrium. The algorithm consists of an iterative procedure combining a backward recursion similar to minimax differential dynamic programming and a forward recursion resembling a risk-sensitive Kalman smoother. A coupling equation renders the resulting control dependent on the estimation. In the end, the algorithm is equivalent to a Newton step but has linear complexity in the time horizon length. Furthermore, a merit function and a line search procedure are introduced to guarantee convergence of the iterative scheme. The resulting controller reasons about uncertainty by planning for the worst case disturbances. Lastly, the low computational cost of the proposed algorithm makes it a promising method to do output-feedback model predictive control on complex systems at high frequency. Numerical simulations on realistic robotic problems illustrate the risk-sensitive behavior of the resulting controller.
BibTeX
@article{jordana2022stagewise,
  author = {Armand Jordana and Bilal Hammoud and Justin Carpentier and Ludovic Righetti},
  title = {{Stagewise Newton Method for Dynamic Game Control With Imperfect State Observation}},
  journal = {IEEE Control. Syst. Lett.},
  year = {2022},
  doi = {10.1109/lcsys.2022.3184657},
}

Loading related content...

Figure