Not Logged In

A Heuristic-Based Approach to Multi-Agent Moving-Target Search

The main focus of this study is to consider strategies for several agents that try to capture a single moving target, that is, multi-agent moving-target search. Until now, researches have treated the moving-target search problem as a single-agent search problem by using single-agent search algorithms such as as A* and single-agent search heuristic functions such as Manhattan distance. This thesis shows how coordinating multiple agents can be achieved with a simple algorithm, CRA, that uses the cover heuristic -- a new heuristic function designed for multi-agent search. We show that CRA is optimal in graphs for which one pursuer has a winning strategy and we compare the performance of CRA with optimal strategies on small problems, showing that CRA is within 10% of optimal on this set of problems. Finally, we show that CRA has a higher success rate and a lower capture time than the previous state-of-the-art algorithms.

Citation

A. Isaza. "A Heuristic-Based Approach to Multi-Agent Moving-Target Search". MSc Thesis, University of Alberta, August 2008.

Keywords: moving-target search, cover, single-agent search, heuristic search, moving-target pursuit
Category: MSc Thesis
Related Publication(s): A Cover-Based Approach to Multi-Agent Moving Target Pursuit

BibTeX

@mastersthesis{Isaza:08,
  author = {Alejandro Isaza},
  title = {A Heuristic-Based Approach to Multi-Agent Moving-Target Search},
  School = {University of Alberta},
  year = 2008,
}

Last Updated: May 02, 2009
Submitted by Alejandro Isaza

University of Alberta Logo AICML Logo