Capturing an evader in polygonal environments with obstacles: The full visibility case

Deepak Bhadauria, Kyle Klein, Volkan I Isler, Subhash Suri

Research output: Contribution to journalArticlepeer-review

52 Scopus citations


Suppose an unpredictable evader is free to move around in a polygonal environment of arbitrary complexity that is under full camera surveillance. How many pursuers, each with the same maximum speed as the evader, are necessary and sufficient to guarantee a successful capture of the evader? The pursuers always know the evader's current position through a camera network, but need to physically reach the evader to capture it. We allow the evader knowledge of the current positions of all the pursuers as well-this accords with the standard worst-case analysis model, but also models a practical situation where the evader has 'hacked' into the surveillance system. Our main result is to prove that three pursuers are always sufficient and sometimes necessary to capture the evader. The bound is independent of the number of vertices or holes in the polygonal environment.

Original languageEnglish (US)
Pages (from-to)1176-1189
Number of pages14
JournalInternational Journal of Robotics Research
Issue number10
StatePublished - Sep 2012


  • Path planning for multiple mobile robot systems
  • mobile and distributed robotics SLAM sensor networks
  • pursuit evasion games
  • sensing and perception computer vision
  • sensing and perception computer vision surveillance systems


Dive into the research topics of 'Capturing an evader in polygonal environments with obstacles: The full visibility case'. Together they form a unique fingerprint.

Cite this