Probabilistic Multi-Robot Search for an Adversarial Target

University of Michigan APRIL Laboratory, 2019

PDF thumbnail
(PDF, 521.9 KB )

Abstract

The problem of planning the actions of several robots (pursuers) who are searching for another agent (an evader) has been frequently studied, with most methods focusing on finding strategies that guarantee capture of even a worst-case evader. However, in many real-world situations, the environment may be too complex or the pursuers too few in number to ensure capture. In such cases, the best that the pursuers can do is select actions that maximize the probability of capture for a given type of evader. In this paper, we propose Probabilistic Adversarial Target Search (PATS), which computes joint search actions that approximately maximize capture probability against an evader with perfect knowledge but finite speed. PATS uses Monte Carlo tree search (MCTS) to compute pursuit plans given the pursuers' probabilistic belief about the evader's location. PATS then evolves this belief forward in time based on the expected actions of the evader, which are obtained from the search tree's empirical statistics. We show that PATS outperforms an existing probabilistic search method in a simulated search setting for which guaranteed search is impossible.


bibtex

@techreport{marcotte2019search,
    AUTHOR     = {Ryan J. Marcotte and Acshi Haggenmiller and Gonzalo Ferrer and Edwin
                 Olson},
    TITLE      = {Probabilistic Multi-Robot Search for an Adversarial Target},
    INSTITUTION = {University of Michigan APRIL Laboratory},
    YEAR       = {2019},
    MONTH      = {June},
}