Not Logged In

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

Full Text: cmtp.pdf PDF

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.

Citation

A. Isaza, J. Lu, V. Bulitko, R. Greiner. "A Cover-Based Approach to Multi-Agent Moving Target Pursuit". Artificial Intelligence and Interactive Entertainment Conference (AIIDE), October 2008.

Keywords: moving-target search, planning, search
Category: In Conference

BibTeX

@incollection{Isaza+al:AIIDE08,
  author = {Alejandro Isaza and Jieshan Lu and Vadim Bulitko and Russ Greiner},
  title = {A Cover-Based Approach to Multi-Agent Moving Target Pursuit},
  booktitle = {Artificial Intelligence and Interactive Entertainment Conference
    (AIIDE)},
  year = 2008,
}

Last Updated: July 07, 2008
Submitted by Alejandro Isaza

University of Alberta Logo AICML Logo