An Efficient Algorithm for Multiple-Pursuer-Multiple-Evader Pursuit/Evasion Game
Josh Bertram, Peng Wei
Abstract
View Video Presentation: https://doi.org/10.2514/6.2021-1862.vid We present a method for pursuit/evasion from the Artificial Intelligence community that is highly efficient and and scales to large teams of aircraft. The underlying algorithm, FastMDP, is an efficient algorithm for solving Markov Decision Processes (MDPs) that supports fully continuous state spaces. We demonstrate the algorithm in a team pursuit/evasion setting in a 3D environment and study performance by varying sizes of teams up to 100 vs 100. We show that as the number of aircraft in the simulation grows, computational performance remains efficient and is suitable for real-time systems. To the authors knowledge this is the first approach for large scale pursuit-evasion problems that remains efficient enough to be deployed on embedded hardware. We use probability-to-win and survivability metrics that describe the teams' performance over multiple trials to show that the algorithm performs consistently. We provide numerical results showing control inputs for a typical 1v1 encounter and provide videos for 1v1, 2v2, 3v3, 4v4, and 10v10 contests to demonstrate the ability of the algorithm to adapt seamlessly to complex environments.