# ALGAMES: A Fast Augmented Lagrangian Solver for Constrained Dynamic Games

arXiv: https://arxiv.org/abs/2104.08452 · HTML: https://mlsanity.com/paper/2104.08452/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Apr 2021.

## Built on by (most cited first, 16 of 16)

- [Deep Interactive Motion Prediction and Planning: Playing Games with Motion Prediction Models](https://mlsanity.com/paper/2204.02392/) (2022)
- [Energy-based Potential Games for Joint Motion Forecasting and Control](https://mlsanity.com/paper/2312.01811/) (2023)
- [SOCIALMAPF: Optimal and Efficient Multi-Agent Path Finding with Strategic Agents for Social Navigation](https://mlsanity.com/paper/2210.08390/) (2022)
- [Multi-Agent Inverse Reinforcement Learning in Real World Unstructured Pedestrian Crowds](https://mlsanity.com/paper/2405.16439/) (2024)
- [SOCIALGYM 2.0: Simulator for Multi-Agent Social Robot Navigation in Shared Human Spaces](https://mlsanity.com/paper/2303.05584/) (2023)
- [A Game-Theoretic Framework for Joint Forecasting and Planning](https://mlsanity.com/paper/2308.06137/) (2023)
- [On a Connection between Differential Games, Optimal Control, and Energy-based Models for Multi-Agent Interactions](https://mlsanity.com/paper/2308.16539/) (2023)
- [Auto-Encoding Bayesian Inverse Games](https://mlsanity.com/paper/2402.08902/) (2024)
- [Mixed Strategy Nash Equilibrium for Crowd Navigation](https://mlsanity.com/paper/2403.01537/) (2024)
- [Collaborative Navigation and Manipulation of a Cable-towed Load by Multiple Quadrupedal Robots](https://mlsanity.com/paper/2206.14424/) (2022)
- [Decentralized Social Navigation with Non-Cooperative Robots via Bi-Level Optimization](https://mlsanity.com/paper/2306.08815/) (2023)
- [How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Games](https://mlsanity.com/paper/2210.13064/) (2022)
- [GTP-UDrive: Unified Game-Theoretic Trajectory Planner and Decision-Maker for Autonomous Driving in Mixed Traffic Environments](https://mlsanity.com/paper/2406.14077/) (2024)
- [Constraint Learning in Multi-Agent Dynamic Games from Demonstrations of Local Nash Interactions](https://mlsanity.com/paper/2508.19945/) (2025)
- [Game-theoretic Objective Space Planning](https://mlsanity.com/paper/2209.07758/) (2022)
- [Bayesian Inverse Games with High-Dimensional Multi-Modal Observations](https://mlsanity.com/paper/2601.00696/) (2026)

## Abstract (arXiv)

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.