Constraint Conditions of Successful Capture in Multi-Pursuers vs One-Evader Games
FANG Baofu1,2, PAN Qishu1, HONG Bingrong1, DING Lei2, CAI Zesu1
1. School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China; 2. School of Computer and Information, Hefei University of Technology, Hefei 230009, China
Abstract：The constraint conditions of successful capture in multi-robot 2D pursuit-evasion game with n pursuers and one evader are researched. Based on the theoretical analyses, under the condition that all robots have global visual field, the pursuers using appropriate strategy can always capture the evader, even if the top speed of the pursuers is lower than that of the evader when the following two conditions are both satisfied. One is that the speed ratio of each pursuer to the evader is higher than sin (π/n), and the other is that the evader should be located in the convex polygon which takes the multiple pursuers as vertexes, and that the adjacent Apollonius circles formed by the evader and each pursuer should be intersected or tangent. In addition, the pursuit-evasion strategies for pursuer and evader are designed under the proposed constraint conditions. Results of many simulation experiments can also prove that the constraint conditions are correct.
[1] Isaacs R. Differential games: A mathematical theory with applications to warfare and pursuit, control and optimization［M］. Hoboken, NJ, USA: John Wiley & Sons Inc., 1965: 1-102. [2] Vidal R, Shakernia O, Kim H J, et al. Probabilistic pursuit-evasion games: Theory, implementation, and experimental evaluation［J］. IEEE Transactions on Robotics and Automation, 2002, 18(5): 662-669. [3] 周浦城,洪炳镕,王月海.动态环境下多机器人合作追捕研究［J］.机器人,2005,27(4): 289-295. Zhou P S, Hong B R, Wang Y H. Multi-robot cooperative pursuit under dynamic environment［J］. Robot, 2005, 27(4): 289-295. [4] Lazhar K, Farid T, Kamel B, et al. Mobile robot navigation based on Q-learning technique［J］. International Journal of Advanced Robotic Systems, 2011, 8(1): 45-51. [5] Zhou P C, Hong B R, Wang Y H, et al. Multi-agent cooperative pursuit based on extended contract net protocol[C]//In-ternational Conference on Machine Learning and Cybernetics. Piscataway, NJ, USA: IEEE, 2004: 169-173. [6] Cai Z S, Sun L N, Gao H B, et al. A novel hierarchical decomposition for multi-player pursuit evasion differential game with superior evaders[C]//World Summit on Genetic and Evolutionary Computation. New York, NY, USA: ASSOC Computing Machinery, 2009: 795-798. [7] Steven L, Robert W. Automatic methods for continuous state space abstraction[R]. Menlo Park, CA, USA: AAAI, 2010: 48-53. [8] Piater J, Jodogne S, Detry R, et al. Learning visual representations for perception-action systems［J］. International Journal of Robotics Research, 2011, 30(3): 294-307. [9] Herrero-Pérez D, Martinez-Barberá H, LeBlanc K. Fuzzy uncertainty modeling for grid based localization of mobile robots［J］. International Journal of Approximate Reasoning, 2010, 51(8): 912-932. [10] 苏治宝,陆际联,童亮.一种多移动机器人协作围捕策略［J］.北京理工大学学报,2004,24(5): 403-406. Su Z B, Lu J L, Tong L. Strategy of cooperative hunting by multiple mobile robots［J］. Transactions of Beijing Institute of Technology, 2004, 24(5): 403-406. [11] 付勇,汪浩杰.一种多机器人围捕策略［J］.华中科技大学学报,2008,36(2):26-29. Fu Y, Wang H J. A new capture strategy of multi-robots［J］. Journal of Huazhong University of Science and Technology: Natural Science Edition, 2008, 36(2): 26-29. [12] Jin S Y, Qu Z H. Pursuit-evasion games with multi-pursuer vs. one fast evader[C]//8th World Congress on Intelligent Control and Automation. Piscataway, NJ, USA: IEEE, 2010: 3184-3189.
