ALGAMES: A Fast Solver for Constrained Dynamic Games


Simon Le Cleac’h, Mac Schwager, Zachary Manchester

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, running at more than 60Hz, demonstrates ALGAMES' ability to mitigate the "frozen robot" problem on complex autonomous driving scenarios like merging onto a crowded highway.

Live Paper Discussion Information

Start Time End Time
07/16 15:00 UTC 07/16 17:00 UTC

Virtual Conference Presentation

Paper Reviews

Review 1

Clear introduction, including motivation and contribution statement. See my comments to the contribution statement in the answer in the first box. The remainder of the paper is also clear and well structured. The related works section provides a good overview of the state of the art, the different methodologies and how they compare to the method proposed by the authors. The following paper addressed similar scenarios to the ones proposed in this paper and might also be of interest to the authors: Social behavior for autonomous vehicles, by Wilko Schwarting, Alyssa Pierson, Javier Alonso-Mora, Sertac Karaman, Daniela Rus. Proceedings of the National Academy of Sciences, Dec 2019, 116 (50). Mostly clear problem formulation except for the constraints C in Eq (3). Here a forward reference to where they will be described (and a short intuitive description) might be enough. It is also worth to clarify that here both the X and U of all players are computed in the optimization, even if in the arg min only X and U^v are present. Finally, clarify why it is not required to have the cost function of all players in the optimization to solve a joint minimum. Method: In Eq 4 justify why a penalty term is added for C but not for D. In G^v the derivatives of D are present, yet in G the constraints D are directly stacked. Why are they treated differently? Function “IncreasingSchedules” is undefined. The discussion section is useful and fair. In the experimental setup, why do you choose unicycle kinematic model? Does the method not work well for bicycle model, which is more realistic for autonomous cars? In Fig.5 how is the maximum constraint violation defined? Are higher values (closer to 0) better or worse? Is your solver faster but provides less safe solutions? Sec. VII is a nice addition to adapt the plan. The current version is a proof of concept and should be treated as such since the authors show qualitative results of a single run. How does the proposed framework compare to standard MPC with constant velocity assumption? How is its performance over multiple runs? Where does it “break”? Nice video illustrating the approach. Suggestions and questions: - For the left turn scenario: how does the nash equilibrium strategy perform? You could compare both. - For the merging scenario. Why the car does not just merge behind the red one in some scenarios where it is more efficient? - Pedestrian scenario: the avoidance and adaptation would also be achieved with a standard MPC. What is the difference in performance with respect to the proposed approach? Minor comments: The notation m^v is confusing m_v might be clearer to not confuse the notation with exp(m,v).

Review 2

Pros: This paper is well written: The game theoretic formulation of the autonomous driving scenario is well motivated. A comprehensive review of the related works are provided in the second section, which identifies the limitations of the previous works. The discussion about the limitation of the proposed algorithm in Section IV is enlightening. The numerical results and comparisons are convincing. Cons: This article could be improved in the following ways: (1) A strong assumption of this work is the access to an accurate estimate of other agents' objective function. The evaluation uses a simple quadratic objective function, and the only interaction between agents are through the no-collision constraint. It seems questionable whether this proposed algorithm can handle the real-world situations in which the objective function of agents could be more complicated functions with significant modeling uncertainty. (2) The first stated contribution that "this work proposed a general solver for dynamic games aimed at identifying Generalized Nash Equilibrium strategies" seems to be a bit of an overclaim. As the proposed approach heavily relies on gradient-based optimization approach, it does not handle games of non-differentiable dynamics and objectives. (3) The second stated contribution that "A real time MPC implementation of the solver able to handle noise, disturbances, and collision constraints" is very incremental. Also, the achievement of safety without an accurate objective function seems to be due to MPC, not due to the proposed solver.

Review 3

The paper has developed a very nice Augumented Lagrangian GAME-theoretic Solver (ALGAMES), which is able to solve dynamic games with multiple players and nonlinear state/input constraints, satisfy the first-order optimality conditions with a quasi-Newton root-finding algorithm, enforce constraints with Lagrangian formulation. Robustness against noises/disturbance of the proposed algorithm has also been demonstrated by a MPC implementation in autonomous driving. Faster convergence of the proposed algorithm over existing methods such as iLQGames has also been provided by implementation.