Markovian search games in heterogeneous spaces

Richard R. Brooks; Jason Schwier; Christopher Griffin

doi:10.1109/TSMCB.2008.2007743

Markovian search games in heterogeneous spaces

Richard R. Brooks
, Jason Schwier
, Christopher Griffin

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

In this paper, we consider how to search for a mobile evader in a large heterogeneous region when sensors are used for detection. Sensors are modeled using probability of detection. Due to environmental effects, this probability will not be constant over the entire region. We map this problem to a graph-search problem, and even though deterministic graph search is NP-complete, we derive a tractable optimal probabilistic search strategy. We do this by defining the problem as a dynamic game played on a Markov chain. We prove that this strategy is optimal in the sense of Nash. Simulations of an example problem illustrate our approach and verify our claims.

Original language	English (US)
Pages (from-to)	626-635
Number of pages	10
Journal	IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
Volume	39
Issue number	3
DOIs	https://doi.org/10.1109/TSMCB.2008.2007743
State	Published - 2009

All Science Journal Classification (ASJC) codes

Control and Systems Engineering
Software
Information Systems
Human-Computer Interaction
Computer Science Applications
Electrical and Electronic Engineering

Access to Document

10.1109/TSMCB.2008.2007743

Cite this

@article{bbb4bc949b8741a7b2104929bcf14b35,

title = "Markovian search games in heterogeneous spaces",

abstract = "In this paper, we consider how to search for a mobile evader in a large heterogeneous region when sensors are used for detection. Sensors are modeled using probability of detection. Due to environmental effects, this probability will not be constant over the entire region. We map this problem to a graph-search problem, and even though deterministic graph search is NP-complete, we derive a tractable optimal probabilistic search strategy. We do this by defining the problem as a dynamic game played on a Markov chain. We prove that this strategy is optimal in the sense of Nash. Simulations of an example problem illustrate our approach and verify our claims.",

author = "Brooks, \{Richard R.\} and Jason Schwier and Christopher Griffin",

note = "Funding Information: Manuscript received February 1, 2008; revised October 7, 2008. This work was supported by the Office of Naval Research Code 311 under Grant N00014-06-C-0022. The work of R. R. Brooks was supported in part by the U.S. Army Research Laboratory and the U.S. Army Research Office under Award W911NF-05-1-0226. The work of C. Griffin was supported by the U.S. Department of Energy under Contract DE-AC05-00OR22725. This paper was recommended by Associate Editor T. Vasilakos.",

year = "2009",

doi = "10.1109/TSMCB.2008.2007743",

language = "English (US)",

volume = "39",

pages = "626--635",

journal = "IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics",

issn = "1083-4419",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "3",

}

TY - JOUR

T1 - Markovian search games in heterogeneous spaces

AU - Brooks, Richard R.

AU - Schwier, Jason

AU - Griffin, Christopher

N1 - Funding Information: Manuscript received February 1, 2008; revised October 7, 2008. This work was supported by the Office of Naval Research Code 311 under Grant N00014-06-C-0022. The work of R. R. Brooks was supported in part by the U.S. Army Research Laboratory and the U.S. Army Research Office under Award W911NF-05-1-0226. The work of C. Griffin was supported by the U.S. Department of Energy under Contract DE-AC05-00OR22725. This paper was recommended by Associate Editor T. Vasilakos.

PY - 2009

Y1 - 2009

N2 - In this paper, we consider how to search for a mobile evader in a large heterogeneous region when sensors are used for detection. Sensors are modeled using probability of detection. Due to environmental effects, this probability will not be constant over the entire region. We map this problem to a graph-search problem, and even though deterministic graph search is NP-complete, we derive a tractable optimal probabilistic search strategy. We do this by defining the problem as a dynamic game played on a Markov chain. We prove that this strategy is optimal in the sense of Nash. Simulations of an example problem illustrate our approach and verify our claims.

AB - In this paper, we consider how to search for a mobile evader in a large heterogeneous region when sensors are used for detection. Sensors are modeled using probability of detection. Due to environmental effects, this probability will not be constant over the entire region. We map this problem to a graph-search problem, and even though deterministic graph search is NP-complete, we derive a tractable optimal probabilistic search strategy. We do this by defining the problem as a dynamic game played on a Markov chain. We prove that this strategy is optimal in the sense of Nash. Simulations of an example problem illustrate our approach and verify our claims.

UR - https://www.scopus.com/pages/publications/67349286971

UR - https://www.scopus.com/pages/publications/67349286971#tab=citedBy

U2 - 10.1109/TSMCB.2008.2007743

DO - 10.1109/TSMCB.2008.2007743

M3 - Article

C2 - 19174351

AN - SCOPUS:67349286971

SN - 1083-4419

VL - 39

SP - 626

EP - 635

JO - IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics

JF - IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics

IS - 3

ER -

Markovian search games in heterogeneous spaces

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this