ALGAMES: A Fast Augmented Lagrangian Solver for Constrained Dynamic Games
This addresses the problem of efficient and robust control for autonomous driving in interactive scenarios, representing an incremental improvement with specific gains over existing methods.
The paper tackles trajectory optimization for multi-actor dynamic games with nonlinear constraints by introducing ALGAMES, a solver that uses an augmented Lagrangian method and quasi-Newton root-finding, resulting in solving ramp merging with three vehicles three times faster than a state-of-the-art DDP-based approach and enabling MPC at over 60 Hz to mitigate the 'frozen robot' problem.
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.