PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Iterative Linear-Quadratic Approximations for Nonlinear Multi-Player General-Sum Differential Games

David Fridovich-Keil, Ellis Ratner, Lasse Peters, Anca D. Dragan, Claire J. Tomlin

arXiv:1909.04694v4eess.SYcs.RO

TL;DR

Robotics needs efficient ways to reason about interacting agents, but differential-game solvers scale poorly and decoupling agents can discard their interactive dependence. The paper repeatedly solves linear-quadratic game approximations inspired by ILQR, obtaining complex interactive strategies that converge reliably in real-time examples.

Abstract

from arXiv · show

Many problems in robotics involve multiple decision making agents. To operate efficiently in such settings, a robot must reason about the impact of its decisions on the behavior of other agents. Differential games offer an expressive theoretical framework for formulating these types of multi-agent problems. Unfortunately, most numerical solution techniques scale poorly with state dimension and are rarely used in real-time applications. For this reason, it is common to predict the future decisions of other agents and solve the resulting decoupled, i.e., single-agent, optimal control problem. This decoupling neglects the underlying interactive nature of the problem; however, efficient solution techniques do exist for broad classes of optimal control problems. We take inspiration from one such technique, the iterative linear-quadratic regulator (ILQR), which solves repeated approximations with linear dynamics and quadratic costs. Similarly, our proposed algorithm solves repeated linear-quadratic games. We experimentally benchmark our algorithm in several examples with a variety of initial conditions and show that the resulting strategies exhibit complex interactive behavior. Our results indicate that our algorithm converges reliably and runs in real-time. In a three-player, 14-state simulated intersection problem, our algorithm initially converges in < 0.25s. Receding horizon invocations converge in < 50 ms in a hardware collision-avoidance test.

I. INTRODUCTION

Multi-agent robotics requires reasoning about interacting decisions, but differential games are difficult to solve numerically at useful scales. The paper proposes a local iterative method that preserves interactions while enabling real-time computation.

Motivation

  • Differential games formalize multi-agent decision making without requiring a priori predictions of other agents’ behavior.They model settings such as cars and pedestrians coordinating to reach goals without collisions or lane departures.Source: §I · p. 1

Challenges

  • Most differential games lack analytic solutions, while numerical methods face dimensionality, offline-computation, and scalability challenges.Games with more than two players remain especially difficult for online use.Source: §I · p. 1, A. General-sum games · p. 2

Motivation

  • Decoupling agents into single-agent optimal-control problems can miss strategies exploiting others’ reactions and may produce unsafe behavior under nominal predictions.The red-car example illustrates the risk of assuming that a pedestrian will move out of the way.Source: §I · p. 1

Contribution

  • The proposed local algorithm recovers interactive strategies by repeatedly solving linear-quadratic game approximations inspired by ILQR.Local solutions avoid searching for global Nash equilibria while retaining the game’s interactive structure.Source: §I · pp. 1–2

B. Approximation techniques

The paper situates its approach among approximate methods for general-sum games and formulates an N-player nonlinear finite-horizon game with state-feedback strategies. It extends iterative LQ ideas from optimal control to general-sum games.

Approximation techniques

  • Coupled Hamilton-Jacobi equations for general-sum games require exponential time and memory, leaving online real-time scalability challenging.Approximate methods relax settings through linear dynamics, decomposability, dynamic programming, or altered information structures.Source: B. Approximation techniques · p. 2
  • Iterative best response reduces a game to repeated optimal-control problems, but solving these problems for every player can be computationally inefficient.Recent applications include lane changes and multi-vehicle racing.Source: B. Approximation techniques · p. 2

Iterative LQ methods

  • The paper’s method replaces ILQR’s LQR subproblem with an LQ game, extending iterative LQ approximations to N-player general-sum games.The work also experimentally characterizes solution quality and demonstrates real-time operation.Source: C. Iterative linear-quadratic (LQ)… · p. 2

Problem formulation

  • The modeled game has nonlinear dynamics, player-specific running costs, and controls whose effects are coupled through the shared state trajectory.The formulation assumes continuous-time dynamics and differentiable dynamics and costs.Source: §III · p. 2
  • The target strategies are time-varying state-feedback mappings from time and system state to each player’s control input.Players observe the system state but are unaware of other players’ control strategies.Source: §III · p. 2

Equilibrium concept

  • A global Nash equilibrium requires that no player can improve by unilaterally changing strategy, but the paper instead seeks a related local equilibrium concept.Local Nash conditions apply only within a neighborhood of the strategy space.Source: §III · pp. 2–3

IV. ITERATIVE LINEAR-QUADRATIC GAMES

The algorithm approaches nonlinear general-sum games through successive linear-quadratic approximations. Each approximation is connected to the coupled Riccati equations characterizing finite-horizon LQ-game equilibria.

IV. ITERATIVE LINEAR-QUADRATIC GAMES

  • Finite-horizon LQ-game Nash strategies satisfy coupled Riccati differential equations derived from generalized Hamilton-Jacobi equations and first-order optimality conditions.The coupled equations can be solved approximately in discrete time using dynamic programming.Source: §IV · p. 3

A. Iterative LQ game algorithm

The algorithm iteratively linearizes dynamics and quadraticizes costs around a current trajectory, solves the resulting LQ game, and takes a controlled step toward updated feedback strategies. It uses local approximations and fixed-step updates to address nonlinear multi-player interactions, while lacking an arbitrary-initialization convergence guarantee.

  • Each iteration simulates the current feedback strategies to obtain a trajectory, then linearizes the dynamics around that trajectory.Source: A. Iterative LQ game algorithm · p. 3
  • The method constructs quadratic running-cost approximations using gradients and Hessians, while neglecting mixed state-control partials that rarely appear in practical cost structures.Source: A. Iterative LQ game algorithm · p. 3
  • The resulting finite-horizon LQ game is solved through coupled Riccati differential equations to produce affine feedback strategies.Source: A. Iterative LQ game algorithm · p. 3
  • A step size η ∈ (0, 1] interpolates between the previous open-loop controls and the new LQ-game solution, reducing divergence risk from inaccurate local approximations.Source: A. Iterative LQ game algorithm · p. 3
  • The approach is not guaranteed to converge from arbitrary initializations because conflicting player costs prevent a standard cost-decreasing line search.Source: A. Iterative LQ game algorithm · pp. 3–4

B. Characterizing fixed points

At a fixed point, the converged strategies solve a local LQ approximation of the original game, but they need not form a local Nash equilibrium of the original nonlinear game.

C. Computational complexity and runtime

The method has per-iteration complexity comparable to ILQR, with polynomial dependence on player and state counts, and demonstrates sub-second or millisecond-scale runtimes in reported examples.

V. EXAMPLES

The examples demonstrate the algorithm experimentally in three-player noncooperative settings using both software simulation and hardware.

V. EXAMPLES

  • The algorithm is evaluated in three-player noncooperative settings across software simulation and hardware.Source: §V · p. 4

A. Monte Carlo study

In a three-player hallway game, Algorithm 1 converges from diverse initial strategies to distinct interaction modes, with most trajectories converging reliably.

  • The hallway game models three people exchanging positions over 10 s while maintaining at least 1 m clearance.Each player’s state includes position, heading, and speed, yielding 12 state dimensions and six input dimensions overall.Source: A. Monte Carlo study · p. 4
  • The proximity cost strongly couples players’ strategies because the hallway is too narrow for simultaneous crossing without a large penalty.The cost structure also penalizes hallway-center deviation, goal error, and control inputs.Source: A. Monte Carlo study · p. 4
  • 500 random initial strategies produced clustered trajectories representing qualitatively distinct modes of interaction.Each cluster reflects players taking slightly higher costs to make room for others to pass.Source: A. Monte Carlo study · p. 5, Figure 2 · p. 5
  • State trajectories converged within an ℓ∞ tolerance of 0.01 in well under 100 iterations.Source: A. Monte Carlo study · p. 5
  • Only 6 of 500 random samples failed to converge and required resampling, while 5 converged to outlier trajectories.In those five outlier cases, players came within 0.5 m of one another.Source: A. Monte Carlo study · p. 5

B. Three-player intersection

In a three-player intersection game, Algorithm 1 finds coordinated strategies for two cars and a pedestrian, including collision-avoidance maneuvers that redistribute progress among players.

  • Algorithm 1 terminates in under 0.25 s for a 14-dimensional, three-player intersection game.The game uses a 5 s horizon discretized at 0.1 s.Source: B. Three-player intersection · p. 5
  • Each car uses front-wheel angle dynamics and controls consisting of front-wheel angular rate and longitudinal acceleration.Together with the pedestrian, the game has 14 state dimensions.Source: B. Three-player intersection · p. 5
  • The converged strategies coordinate cars and pedestrian movements while sharing responsibility for collision avoidance.The paper notes that such competitive coordination is difficult for a decoupled optimal-control formulation to recover.Source: B. Three-player intersection · p. 5
  • The green car first seeks the lane center, then turns slightly to avoid the pedestrian.This behavior occurs between 0 and 0.8 s in the reported solution.Source: B. Three-player intersection · p. 5, Figure 3 · p. 5
  • The red car turns right to pass the green car, then slows and turns left to give the pedestrian time and space to cross.Source: B. Three-player intersection · p. 5, Figure 3 · p. 5

C. Receding horizon motion planning

In hardware, the robot repeatedly resolves a differential game over a receding horizon to adapt to human deviations and execute interactive collision-avoidance maneuvers in real time.

VI. DISCUSSION

The paper presents an efficient local algorithm for multi-player general-sum differential games and demonstrates interactive strategies across simulations and real-time hardware operation. Its comparisons remain challenging because solution quality depends on equilibrium concepts, information structures, and implementation details, while convergence lacks an a priori guarantee from arbitrary initializations.

  • The algorithm finds local solutions in multi-player general-sum differential games and accounts directly for multi-agent interactions.The approach is related to ILQR and targets practical differential-game solution methods.Source: §VI · p. 6
  • Monte Carlo experiments show reliable convergence and complex interactive strategies for multiple agents.The identified solutions display competitive behavior associated with local Nash equilibria, with subtle differences.Source: §VI · p. 6
  • A three-player 14-dimensional traffic example and a real-time hardware robot-navigation scenario demonstrate the method in progressively practical settings.The hardware test uses a receding time horizon.Source: §VI · p. 6
  • Quantitative comparison with other local-solution algorithms is challenging because equilibrium concepts, information structures, and implementation details differ.Different players may also prefer different equilibria in arbitrary general-sum games.Source: §VI · p. 6
  • The algorithm has no a priori theoretical guarantee of convergence from arbitrary initializations despite reliable empirical convergence.The paper identifies theoretical explanation of this empirical property as future work.Source: §VI · p. 6

Related papers

Loading 1909.04694v4…