Markovian search games in heterogeneous spaces

Richard R. Brooks, Jason Schwier, Christopher Griffin

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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 languageEnglish (US)
Pages (from-to)626-635
Number of pages10
JournalIEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
Issue number3
StatePublished - 2009

All Science Journal Classification (ASJC) codes

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


Dive into the research topics of 'Markovian search games in heterogeneous spaces'. Together they form a unique fingerprint.

Cite this