  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.
