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
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.
Problem
Differential games capture multi-agent interactions, but existing numerical methods scale poorly, while decoupling agents can miss reaction-dependent strategies and risk unsafe nominal predictions.
Method
The algorithm repeatedly linearizes dynamics and quadratizes costs around a trajectory, then solves successive linear-quadratic game approximations.
Results
The resulting strategies exhibit complex interactive behavior, and the algorithm converges reliably in Monte Carlo, intersection, and hardware collision-avoidance tests.
Takeaways & Limitations
The approach provides a way for optimal-control practitioners to account for multi-agent interactions through differential games in real-time operation.
Takeaways & Limitations
The method is not guaranteed to converge from arbitrary initializations because noncooperative players’ costs may conflict.
Abstract
from arXiv · showhide
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.
- 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.
- 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.
- 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.
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.
- Approximation techniques: 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.
- 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.
- 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.
- Problem formulation: 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.
- 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.
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.
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.
- The method constructs quadratic running-cost approximations using gradients and Hessians, while neglecting mixed state-control partials that rarely appear in practical cost structures.
- The resulting finite-horizon LQ game is solved through coupled Riccati differential equations to produce affine feedback strategies.
- 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.
- The approach is not guaranteed to converge from arbitrary initializations because conflicting player costs prevent a standard cost-decreasing line search.
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.
- Fixed-point strategies are the global Nash equilibrium of a local LQ approximation around the limiting operating point.
- The approximation can miss higher-order coupling effects between each player’s running cost and other players’ inputs.
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.
- O(N^3n^3) complexity solves the coupled Riccati equations per time step, compared with O(n^3) for ILQR.
- O(Nn^2) partial derivatives quadraticize player costs per time step, compared with O(n^2) for ILQR.
- < 50 ms solves receding-horizon invocations in a hardware collision-avoidance test.
- The reported computation times use single-threaded operation on a 2017 MacBook Pro, and comparisons involve different game dynamics or costs.
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.
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.
- 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.
- 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.
- State trajectories converged within an ℓ∞ tolerance of 0.01 in well under 100 iterations.
- 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.
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.
- 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.
- 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.
- 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.
- The red car turns right to pass the green car, then slows and turns left to give the pedestrian time and space to cross.
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.
- The demonstrated trajectories show the algorithm planning and executing interactive collision-avoiding maneuvers in real time.Planned and predicted trajectories are shown for the robot and both humans.
- Re-solving along a receding horizon accounts for deviations between other agents’ actual decisions and their game-predicted decisions.
- The hardware test models the robot and humans as agents seeking goals while maintaining more than 1 m clearance.All agents’ state information is obtained through a motion-capture system.
- An unanticipated sharp right turn by the red participant forces the robot to alter its previous plan to maintain separation from both humans.The robot stays right before turning left.
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.
- 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.
- 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.
- 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.
- 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.