Parallel Multi-speed Pursuit-Evasion Game Algorithms

Pursuit-Evasion Game (PEG) is important in the robotics field. Determining the optimal strategy, such as the minimum number of pursuers needed, often require exponential time. We propose a novel parallel algorithm that significantly reduces the computation time for PEG, making it feasible to analyze games with a large number of states and transitions. This algorithm also extends to the heterogeneous/multi-speed players and incorporates advanced strategies. Additionally, we introduce a resource allocation algorithm for heterogeneous multi-agent teams, ensuring efficient resource sharing and real-time agent replacement to maintain fault tolerance. Our simulations demonstrate that our parallel algorithm significantly outperforms existing approaches, achieving up to 8.13 times speedup compared to the state-of-the-art. Furthermore, our algorithms enhance the scalability and practical applicability of solving PEGs.