ALGAMES: A Fast Solver for Constrained Dynamic Games
ALGAMES: A Fast Solver for Constrained Dynamic Games
复制标题
DOI：
10.15607/rss.2020.xvi.091
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Simon Le Cleac'h;M. Schwager;Zachary Manchester
中科院分区：
文献类型：
--
作者：
Simon Le Cleac'h;M. Schwager;Zachary Manchester
动态博弈是处理多个相互作用的参与者控制问题的一种有效范式。本文介绍了ALGAMES（增广拉格朗日博弈论求解器），这是一种能够处理具有多个参与者以及一般非线性状态和输入约束的轨迹优化问题的求解器。其新颖之处在于使用拟牛顿求根算法满足一阶最优性条件，并使用增广拉格朗日公式严格执行约束。我们在车辆之间具有高度交互性的自动驾驶场景中对我们的求解器进行了评估。我们使用蒙特卡洛模拟评估求解器的鲁棒性。它能够可靠地解决诸如三辆车合流这样的复杂问题，且速度比最先进的基于动态规划算法（DDP）的方法快三倍。该算法的模型预测控制（MPC）实现展示了在复杂自动驾驶场景中的实时性能，更新频率高于60赫兹。
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.