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.
[1] Roman S M, Rota G C. The umbral calculus[J]. Advances in Mathematics, 1978, 27(2): 95-188. [2] Aumann R J, Dreze J H. Cooperative games with coalition structures[J]. International Journal of Game Theory, 1974, 3(4): 217-237. [3] Shapley L S. A value for n-person games[M]//Contributions to the Theory of Games II. Annals of Mathematics Study. Princeton, USA: Princeton University Press, 1953: 307-317.[4] Sandholm T, Larson K, Andersson M, et al. Coalition structure generation with worst case guarantees[J]. Artificial Intelligence, 1999, 111(1/2): 209-238.[5] Dang V D, Jennings N R. Generating coalition structures with finite bound from the optimal guarantees[C]//Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems. New York, USA: ACM, 2004: 564-571.[6] Michalak T, Sroka J, Rahwan T, et al. A distributed algorithm for anytime coalition structure generation[C]//Proceedings of the 9th International Conference on Autonomous Agents and Multi agent Systems. Toronto, Canada: International Foundation for Autonomous Agents and Multiagent Systems, 2010: 1007-1014.[7] Rahwan T, Jennings N R. An algorithm for distributing coalitional value calculations among cooperating agents[J]. Artificial Intelligence, 2007, 171(8/9): 535-567.[8] 刘惊雷,张伟,童向荣,等.一种O(2.983～ n)时间复杂度的最优联盟结构生成算法[J].软件学报,2011,22(5):938-950. Liu J L, Zhang W, Tong X R, et al. O(2.983～ n) time complexity algorithm for optimal coalition structure generation[J]. Journal of Software, 2011, 22(5): 938-950.[9] 张新良,石纯一.多Agent联盟结构动态生成算法[J].软件学报,2007,18(3):574-581. Zhang X L, Shi C Y. A dynamic formation algorithm of multi-agent coalition structure[J]. Journal of Software, 2007, 18(3): 574-581.[10] Fang B F, Pan Q S, Hong B R, et al. A hierarchical approach based on fast marching method in multi player pursuit-evasion game[J]. Chinese Journal of Electronics, 2012, 21(1): 59-63.
