Pursuers-Coalition Construction Algorithm in Multi-robot Pursuit-Evasion Game

With the increasing number of robots, the time complexity of solving the optimal coalition problem increases exponentially, which brings difficulty to real-time computation. To solve the predicament, the independence of coalition gain is proved in pursuit-evasion games, and the number of sub pursuers-coalitions can be obtained according to the number of the evaders. Based on these, the pursuit-coalition algorithm based on greed optimal gains is proposed. In the algorithm, the number of pursuers-coalitions is determined according to the number of the evaders. Then, the sub pursuers-coalitions and the leaders of each sub pursuers-coalition are determined according to the corresponding pursuit gains of pursuers and evaders. Finally, all others pursuers are assigned to the each sub optimal coalition based on greed optimal method. The algorithm simplifies the search volume of each level in the coalition structure and greatly improves the search time to O(m×(n-m)). The experiments show the superiority of the proposed algorithm in pursuit search efficiency and pursuit time.