ALGAMES: A Fast Solver for Constrained Dynamic Games

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 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 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 demonstrates real-time performance on complex autonomous driving scenarios with an update frequency higher than 60 Hz.

10 pages, 8 figures, submitted to Robotics: Science and Systems Conference (RSS) 2020

References in corpus (3)

• Differential Dynamic Programming for Nonlinear Dynamic Games
• First-Order Algorithms for Constrained Nonlinear Dynamic Games
• Efficient Iterative Linear-Quadratic Approximations for Nonlinear Multi-Player General-Sum Differential Games

Cited by in corpus (11)

• The Computation of Approximate Generalized Feedback Nash Equilibria
• Learning MPC for Interaction-Aware Autonomous Driving: A Game-Theoretic Approach
• Multimodal Trajectory Prediction via Topological Invariance for Navigation at Uncontrolled Intersections
• Strategic Decision-Making in Multi-Agent Domains: A Weighted Constrained Potential Dynamic Game Approach
• An Inverse Optimal Control Approach for Trajectory Prediction of Autonomous Race Cars
• Iterative Best Response for Multi-Body Asset-Guarding Games
• UMBRELLA: Uncertainty-Aware Model-Based Offline Reinforcement Learning Leveraging Planning
• Potential iLQR: A Potential-Minimizing Controller for Planning Multi-Agent Interactive Trajectories
• Decentralized Role Assignment in Multi-Agent Teams via Empirical Game-Theoretic Analysis
• Decentralized and Communication-Free Multi-Robot Navigation through Distributed Games
• Move Beyond Trajectories: Distribution Space Coupling for Crowd Navigation