ALGAMES: A Fast Solver for Constrained Dynamic Games
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.
Code (1)
Tasks
Autonomous DrivingModel Predictive ControlSimilar Papers 제목 키워드 기반
On the Geometry of Games and their Solvers
A central challenge in game theory and learning systems such as GANs is understanding which algorithms can efficiently compute equilibria across the heterogeneous landscape of games. Equilibrium computation is typically …
Rapid Learning in Constrained Minimax Games with Negative Momentum
In this paper, we delve into the utilization of the negative momentum technique in constrained minimax games. From an intuitive mechanical standpoint, we introduce a novel framework for momentum buffer updating, which ex…
FormA Complete Solver for Constraint Games
Game Theory studies situations in which multiple agents having conflicting objectives have to reach a collective decision. The question of a compact representation language for agents utility function is of crucial impor…
Modelling Behavioural Diversity for Learning in Open-Ended Games
Promoting behavioural diversity is critical for solving games with non-transitive dynamics where strategic cycles exist, and there is no consistent winner (e.g., Rock-Paper-Scissors). Yet, there is a lack of rigorous tre…
DiversityPoint ProcessesA Simple Reward-free Approach to Constrained Reinforcement Learning
In constrained reinforcement learning (RL), a learning agent seeks to not only optimize the overall reward but also satisfy the additional safety, diversity, or budget constraints. Consequently, existing constrained RL s…
Diversityreinforcement-learningReinforcement LearningReinforcement Learning (RL)