Multi-player Reach-Avoid Game in Dynamic Environment

With autonomy gaining popularity and acceptance in various fields, humans have begun shifting to employing autonomous vehicles to perform risky tasks in hostile environment. Therefore, it is crucial that we investigate motion planning problem with safety in mind. In this sense, reach-avoid game is a good problem to analyze due to its complex nature and the fact that worst-case disturbance is considered. In this work we present an iterative open-loop formulation for a reach-avoid game with multiple attackers and defenders. We show the proposed method can find more direct paths compared to the basic open-loop formulation, and perhaps more importantly, the algorithm can find feasible paths in situation where open-loop formulation simply cannot. By solving the game with the proposed method we can guarantee the safety of the planned path, despite the dynamic environment with the presence of unpredictable obstacles, adversarial defender, as well as other attackers. In addition, we offer a practical method that ensures agents with minimum turning radius only take paths that respect the constraints. We verify the effectiveness of our method through a series of simulations.