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

IEEE International Conference on Robotics and Automation (ICRA), 2020

[arXiv] [PDF] [Code]

@inproceedings{fridovich2020ilqgames,
    title     = {Efficient Iterative Linear-Quadratic Approximations for Nonlinear Multi-Player General-Sum Differential Games},
    author    = {Fridovich-Keil, David and Ratner, Ellis and Peters, Lasse and Dragan, Anca D. and Tomlin, Claire J.},
    booktitle = {IEEE International Conference on Robotics and Automation (ICRA)},
    year      = {2020},
    url       = {https://arxiv.org/abs/1909.04694},
    doi       = {10.1109/icra40945.2020.9197129},
    pages     = {1475--1481},
}

Abstract

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.

Video

Code

The code for this work is available as C++ implemenation and in Julia. There is also a ROS extension in the making.