Iterative Linear-Quadratic Games - a new, real-time solver for N-player general differential games.
NOTE that this project is still under active development and is only intended to be used as an academic reference at this stage. However, my intent is that it should eventually become stable enough for use as a reliable substitute for a model-predictive control backend.
For a full description of the algorithm itself and examples of how it can be applied in collision-avoidance problems, please refer to the paper, which was presented at ICRA 2020.
If you find this repository useful, please do cite the paper:
@inproceedings{fridovich2020efficient,
title={Efficient iterative linear-quadratic approximations for nonlinear multi-player general-sum differential games},
author={Fridovich-Keil, David and Ratner, Ellis and Peters, Lasse and Dragan, Anca D and Tomlin, Claire J},
booktitle={2020 IEEE International Conference on Robotics and Automation (ICRA)},
pages={1475--1481},
year={2020},
organization={IEEE}
}
If you are interested in the feedback linearized version of this algorithm, please also refer to that paper, which is also published at ICRA 2020:
@inproceedings{fridovich2020iterative,
title={An iterative quadratic method for general-sum differential games with feedback linearizable dynamics},
author={Fridovich-Keil, David and Rubies-Royo, Vicenc and Tomlin, Claire J},
booktitle={2020 IEEE International Conference on Robotics and Automation (ICRA)},
pages={2216--2222},
year={2020},
organization={IEEE}
}
The primary contributor is David Fridovich-Keil, a recent PhD grad from Claire Tomlin's group in the EECS department at UC Berkeley. David is currently an assistant professor at UT Austin. The best way to contact David is by email, dfk at utexas dot edu, or if you have specific questions about this repository, please post an issue.
Documentation is automatically generated by a continuous integration service with each push to the master branch, and it may be found here. Additionally, a more high-level form of documentation is available in PDF form here.
An early version of the iterative linear-quadratic game algorithm was implemented in Python; it is now deprecated and stored in the python/ directory. Ongoing and future development will proceed primarily in C++, although a colleague has built a standalone version in Julia here
ilqgames has been tested both in OS X and Ubuntu. Depending on your version of Ubuntu, you may notice a linker error related to aclocal-XX, which may be fixed by symlinking Ubuntu's native aclocal to the desired executable aclocal-XX. Otherwise, external dependencies are standard:
glog(Google's logging tools)gflags(Google's command line flag tools)opengl,glut(graphics tools)eigen3(linear algebra library)
This repository uses the cmake build system and may be compiled following standard cmake protocols:
mkdir build && cd build
cmake ..
make -j8
Executables will be stored in the bin/ directory, with the exception of build/run_tests, which runs unit tests. To run unit tests from the build directory, simply execute:
./run_tests
To run a particular example from the bin/ directory, e.g., the three-player intersection:
./three_player_intersection
With any executable, a full explanation of command line arguments can be found by running:
./<name-of-executable> --help
All specific examples, e.g. the three-player intersection, inherit from the base class Problem. This base class provides a number of utilities, such as warm starting, and also wraps the solver. To inherit, simply write a constructor which instantiates the appropriate solver with costs, and also set the initial state, operating point, and strategies. To see an example, consult the ThreePlayerIntersectionExample class.
There is a companion ROS extension under development, which may be found here. It is currently still marked private, but rest assured that the usage of the ilqgames toolbox in ROS is straightforward! If you want to implement this yourself for a custom application it is not too hard.
The native ilqgames graphical user interface can be a very useful tool in debugging algorithm changes, new costs, etc. Currently, it supports so-called TopDownRenderableProblem games, where the state encodes x-y position and (potentially) heading information. To extend the GUI to other types of games, simply write a custom renderer, e.g. mirroring the TopDownRenderer class. All GUI functionality is based on the DearImGui library, a copy of which is maintained locally in the external/ directory.