Locating and capturing an Evader in a polygonal environment

Volkan Isler, Sampath Kannan, Sanjeev Khanna

Research output: Chapter in Book/Report/Conference proceedingChapter

4 Scopus citations


This paper contains two main results: First, we revisit the well-known visibility based pursuit-evasion problem and show that, in contrast to deterministic strategies, a single pursuer can locate an unpredictable evader in any simply-connected polygonal environment using a randomized strategy. The evader can be arbitrarily faster than the pursuer and it may know the position of the pursuer at all times but it does not have prior knowledge of the random decisions made by the pursuer. Second, using the randomized algorithm together with the solution of a known lion and man problem [12] as subroutines, we present a strategy for two pursuers (one of which is at least as fast as the evader) to quickly capture an evader in a simply-connected polygonal environment.

Original languageEnglish (US)
Title of host publicationAlgorithmic Foundations of Robotics VI
PublisherSpringer Verlag
Number of pages16
ISBN (Print)9783540257288
StatePublished - 2005

Publication series

NameSpringer Tracts in Advanced Robotics
ISSN (Print)1610-7438
ISSN (Electronic)1610-742X


Dive into the research topics of 'Locating and capturing an Evader in a polygonal environment'. Together they form a unique fingerprint.

Cite this