Optimal strategies to track and capture a predictable target

Alon Efrat, Hector H. González-Baños, Stephen G. Kobourov, Lingeshwaran Palaniappan

Research output: Contribution to journalConference articlepeer-review

16 Scopus citations


We present an O(n log1+εn)-time algorithm for computing the optimal robot motion that maintains line-of-sight visibility between a target moving inside a polygon with n vertices which may contain holes. The motion is optimal for the tracking robot (the observer) in the sense that the target either remains visible for the longest possible time, or it is captured by the observer in the minimum time when feasible. Thus, the algorithm maximizes the minimum time-to-escape. Our algorithm assumes that the target moves along a known path. Thus, it is an off-line algorithm. Our theoretical results for the algorithm's runtime assume that the target is moving along a shortest path from its source to its destination. This assumption, however is not required to prove the optimality of the computed solution, hence the algorithm remains correct for the general case.

Original languageEnglish (US)
Pages (from-to)3789-3796
Number of pages8
JournalProceedings - IEEE International Conference on Robotics and Automation
StatePublished - 2003
Event2003 IEEE International Conference on Robotics and Automation - Taipei, Taiwan, Province of China
Duration: Sep 14 2003Sep 19 2003

ASJC Scopus subject areas

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


Dive into the research topics of 'Optimal strategies to track and capture a predictable target'. Together they form a unique fingerprint.

Cite this