ALGAMES: A Fast Augmented Lagrangian Solver for Constrained Dynamic Games
Preprint
Abstract
Dynamic games are an effective paradigm for dealing with the control of multiple interacting actors. This paper introduces ALGAMES (Augmented Lagrangian GAME-theoretic Solver), a solver that handles trajectory-optimization problems with multiple actors and general nonlinear state and input constraints. Its novelty resides in satisfying the first-order optimality conditions with a quasi-Newton root-finding algorithm and rigorously enforcing constraints using an augmented Lagrangian method. We evaluate our solver in the context of autonomous driving on scenarios with a strong level of interactions between the vehicles. We assess the robustness of the solver using Monte Carlo simulations. It is able to reliably solve complex problems like ramp merging with three vehicles three times faster than a state-of-the-art DDP-based approach. A model-predictive control (MPC) implementation of the algorithm, running at more than 60 Hz, demonstrates ALGAMES' ability to mitigate the "frozen robot" problem on complex autonomous driving scenarios like merging onto a crowded highway.Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Social behavior for autonomous vehiclesProceedings of the National Academy of Sciences, 2019
- New results on the existence of open loop Nash equilibria in discrete time dynamic games via generalized Nash gamesMathematical Methods of Operations Research, 2018
- Restricted generalized Nash equilibria and controlled penalty algorithmComputational Management Science, 2009
- Generalized Nash equilibrium problems and Newton methodsMathematical Programming, 2007
- Exact penalty functions for generalized Nash problems2006
- On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programmingMathematical Programming, 2005
- Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower gamesComputational Management Science, 2005
- Nonexistence and nonuniqueness of open-loop equilibria in linear-quadratic differential gamesJournal of Optimization Theory and Applications, 1982
- Constrained Optimization and Lagrange Multiplier Methods1982
- On the uniqueness of the Nash solution in Linear-Quadratic differential GamesInternational Journal of Game Theory, 1976