Pursuit-evasion using beam detection

Borislav H. Simov, Giora Slutzki, Steven M. LaValle

Research output: Contribution to journalConference articlepeer-review


We present an algorithm for searching a 2D environment for unpredictable moving targets using only beam-based detection. One or more pursuers move along the environment boundary, and carry a rotating beam that detects evaders. The beam could correspond in practice to a laser or a camera. The task is to compute motions for pursuers and their beams that ensure that all evaders will be detected. For a 2D polygonal environment, we solve a long-standing open problem by presenting a complete O(n3)-time algorithm that is guaranteed to find a successful motion strategy for a single pursuer and its beam, if a solution exists. This algorithm is extended to the case of coordinating multiple pursuers, but the number of pursuers used in a solution is not necessarily optimal. An implementation is presented, and several computed examples are shown.

Original languageEnglish (US)
Pages (from-to)1657-1662
Number of pages6
JournalProceedings - IEEE International Conference on Robotics and Automation
StatePublished - Dec 3 2000
Externally publishedYes
EventICRA 2000: IEEE International Conference on Robotics and Automation - San Francisco, CA, USA
Duration: Apr 24 2000Apr 28 2000

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering


Dive into the research topics of 'Pursuit-evasion using beam detection'. Together they form a unique fingerprint.

Cite this