A heuristic task scheduling for multi-pursuer multi-evader games

This paper introduces a divide-and-conquer, heuristic task scheduling optimization approach on the challenging multi-pursuer multi-evader (MPME) games in which pursuers attempt to minimize the time to capture all evaders whereas evaders try to maximize the capture time. The MPME task scheduling problem is solved through a two-step hierarchical approach. At the high level, the game is divided into a number of subgames or teams using a combination of Voronoi diagram and a negotiation-based mechanism (through heuristic objective functions) to make the pursuit more efficient. At the low level, pursuers within each team are directed locally by their team leader to pursue an evader which runs slower or faster. We mainly focus on a position scheduling problem of how pursuers in a team can surround a faster evader as quickly as possible before entering into the capture phase. Instead of using computation intensive approaches, we use heuristics to solve the complex scheduling problems. In addition to focusing on the pursuer side, evader cooperation is also briefly discussed. Simulation results show the effectiveness of the proposed approach.