A Cover-Based Approach to Multi-Agent Moving Target Pursuit


  • Alejandro Isaza University of Alberta
  • Jieshan Lu University of Alberta
  • Vadim Bulitko University of Alberta
  • Russell Greiner University of Alberta




We explore the task of designing an efficient multi-agent system that is capable of capturing a single moving target, assuming that every agent knows the location of all agents on a fixed known graph. Many existing approaches are suboptimal as they do not coordinate multiple pursuers and are slow as they re-plan each time the target moves, which makes them fare poorly in real-time pursuit scenarios such as video games. We address these shortcomings by developing the concept of cover set, which leads to a measure that takes advantage of information about the position and speed of each agent. We first define cover set and then present an algorithm that uses cover to coordinate multiple pursuers. We compare the effectiveness of this algorithm against several classic and state-of-the-art pursuit algorithms, along several performance measures. We also compute the optimal pursuit policy for several small grids, and use the associated optimal scores as yardsticks for our analysis.




How to Cite

Alejandro Isaza, A. I., Lu, J., Bulitko, V., & Greiner, R. (2021). A Cover-Based Approach to Multi-Agent Moving Target Pursuit. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 4(1), 54-59. https://doi.org/10.1609/aiide.v4i1.18672