Randomized pursuit-evasion with local visibility

Volkan Isler, Sampath Kannan, Sanjeev Khanna

Research output: Contribution to journalArticlepeer-review

62 Scopus citations

Abstract

We study the following pursuit-evasion game: One or more hunters are seeking to capture an evading rabbit on a graph. At each round, the rabbit tries to gather information about the location of the hunters but it can see them only if they are located on adjacent nodes. We show that two hunters suffice for catching rabbits with such local visibility with high probability. We distinguish between reactive rabbits who move only when a hunter is visible and general rabbits who can employ more sophisticated strategies. We present polynomial time algorithms that decide whether a graph G is hunter-win, that is, if a single hunter can capture a rabbit of either kind on G.

Original languageEnglish (US)
Pages (from-to)26-41
Number of pages16
JournalSIAM Journal on Discrete Mathematics
Volume20
Issue number1
DOIs
StatePublished - 2006

Keywords

  • Local information
  • Path planning
  • Pursuit-evasion games
  • Visibility

Fingerprint Dive into the research topics of 'Randomized pursuit-evasion with local visibility'. Together they form a unique fingerprint.

Cite this