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 - http://www.scopus.com/inward/record.url?scp=67349286971&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=67349286971&partnerID=8YFLogxK
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 -