Approximate Solutions to a Class of Reachability Games
This work addresses real-time control challenges in multi-agent systems, though it appears incremental as it builds on existing optimization techniques.
The paper tackles the problem of finding approximate Nash equilibria in reachability games used for collision avoidance and goal satisfaction, presenting a computationally efficient method that runs in real-time for multi-player scenarios with over ten state dimensions.
In this paper, we present a method for finding approximate Nash equilibria in a broad class of reachability games. These games are often used to formulate both collision avoidance and goal satisfaction. Our method is computationally efficient, running in real-time for scenarios involving multiple players and more than ten state dimensions. The proposed approach forms a family of increasingly exact approximations to the original game. Our results characterize the quality of these approximations and show operation in a receding horizon, minimally-invasive control context. Additionally, as a special case, our method reduces to local gradient-based optimization in the single-player (optimal control) setting, for which a wide variety of efficient algorithms exist.