ALGAMES:制約付き動的ゲームのための高速解法
ALGAMES: A Fast Solver for Constrained Dynamic Games
拡張ラグランジュ法と準ニュートン法を組み合わせ、複数エージェントの非線形制約付き軌道最適化を高速に解くソルバを提案し、自動運転の合流シナリオで従来法の3倍速を実現した。
著者: Simon Le Cleac'h, Mac Schwager, Zachary Manchester
分類: cs.RO, cs.AI, cs.GT
原文アブストラクト
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.
関連論文
- STLGame: 敵対的マルチエージェント系における信号時相論理ゲームマルチエージェント/ゲーム理論
- MPOGames: 効率的なマルチモーダル部分観測動的ゲームマルチエージェント/ゲーム理論
