Dynamic Games Solver

Dynamic Games Solver

Dynamic games are an effective paradigm for dealing with the control of multiple interacting actors. We 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 formulation. 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 MonteCarlo 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 demonstrates real-time performance on complex autonomous driving scenarios with an update frequency higher than 60 Hz.

The code for ALGAMES is made available on RexLab’s GitHub ALGAMES.jl.

The paper is available at ALGAMES.

Related Papers

2021
April
PDF ALGAMES: A Fast Augmented Lagrangian Solver for Constrained Dynamic Games
Simon Le Cleac'h, Mac Schwager, and Zac Manchester
Autonomous Robots (AuRo). (Accepted)
2021
May
PDF LUCIDGames: Online Unscented Inverse Dynamic Games for Adaptive Trajectory Prediction and Planning
Simon Le Cleac'h, Mac Schwager, and Zac Manchester
Robotics Automation and Letters (RAL). (Accepted)
2020
July
PDF ALGAMES: A Fast Solver for Constrained Dynamic Games
Simon Le Cleac'h, Mac Schwager, and Zac Manchester
Robotics: Science and Systems (RSS). Corvallis, OR.

People

Zac Manchester
Assistant Professor
Simon Le Cleac'h
Boston Dynamics AI Institute
Last updated: 2020-03-04