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

Authors

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

DOI:

https://doi.org/10.1609/aiide.v4i1.18672

Abstract

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.

Downloads

Published

2021-09-27

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