Visibility-based pursuit-evasion in an unknown planar environment

Shai Sachs, Steven M. LaValle, Stjepan Rajko

Research output: Contribution to journalReview articlepeer-review


We address an on-line version of the visibility-based pursuit-evasion problem. We take a minimalist approach in modeling the capabilities of a pursuer robot. A point pursuer moves in an unknown, simply-connected, piecewise-smooth planar environment, and is given the task of locating any unpredictable, moving evaders that have unbounded speed. The evaders are assumed to be points that move continuously. To solve the problem, the pursuer must for each target have an unobstructed view of it at some time during execution. The pursuer is equipped with a range sensor that measures the direction of depth discontinuities, but cannot provide precise depth measurements. All pursuer control is specified either in terms of this sensor or wall-following movements. The pursuer does not have localization capability or perfect control. We present a complete algorithm that enables the limited pursuer to clear the same environments that a pursuer with a complete map, perfect localization, and perfect control can clear (under certain general position assumptions). Theoretical guarantees that the evaders will be found are provided. The resulting algorithm to compute this strategy has been implemented in simulation. Results are shown for several examples. The approach is efficient and simple enough to be useful towards the development of real robot systems that perform visual searching.

Original languageEnglish (US)
Pages (from-to)3-26
Number of pages24
JournalInternational Journal of Robotics Research
Issue number1
StatePublished - 2004


  • Bug algorithms
  • On-line algorithms
  • Pursuit-evasion
  • Sensing uncertainty
  • Sensor-based planning
  • Surveillance
  • Visibility

ASJC Scopus subject areas

  • Software
  • Modeling and Simulation
  • Mechanical Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'Visibility-based pursuit-evasion in an unknown planar environment'. Together they form a unique fingerprint.

Cite this