ALGAMES: A Fast Solver for Constrained Dynamic Games

@inproceedings{le_cleach_algames_2020,
  title = {{ALGAMES}: {A} {Fast} {Solver} for {Constrained} {Dynamic} {Games}},
  isbn = {978-0-9923747-6-1},
  shorttitle = {{ALGAMES}},
  url = {http://www.roboticsproceedings.org/rss16/p091.pdf},
  abstract = {Dynamic games are an effective paradigm for dealing with the control of multiple interacting actors. Current algorithms for solving these problems either rely on HamiltonJacobi-Isaacs (HJI) methods, dynamic programming (DP), differential dynamic programming (DDP), or an iterative best response approach (IBR). The ﬁrst two approaches have strong theoretical guarantees; however they becomes intractable in high-dimensional real-world applications. The third approach is grounded in the success of iLQR. It is scalable, but it cannot handle constraints. Finally, the iterative best response algorithm is a heuristic approach with unknown convergence properties, and it can suffer from stability and tractability issues. This paper introduces ALGAMES (Augmented Lagrangian GAMEtheoretic Solver), a solver that handles trajectory optimization problems with multiple actors and general nonlinear state and input constraints. We evaluate our solver in the context of autonomous driving on scenarios involving numerous vehicles such as ramp merging, overtaking, and lane changing. We present simulation and timing results demonstrating the speed and the ability of the solver to produce efﬁcient, safe, and natural autonomous behaviors.},
  language = {en},
  urldate = {2020-09-15},
  booktitle = {Robotics: {Science} and {Systems} {XVI}},
  publisher = {Robotics: Science and Systems Foundation},
  author = {Le Cleac'h, Simon and Schwager, Mac and Manchester, Zachary},
  month = jul,
  year = {2020},
  keywords = {game\_theoretic\_planning},
  month_numeric = {7}
}