Finding an unpredictable target in a workspace with obstacles

Steven M. LaValle, David Lin, Leonidas J. Guibas, Jean Claude Latombe, Rajeev Motwani

Research output: Contribution to journalConference articlepeer-review


This paper introduces a visibility-based motion planning problem in which the task is to coordinate the motions of one or more robots that have omnidirectional vision sensors, to eventually `see' a target that is unpredictable, has unknown initial position, and is capable of moving arbitrarily fast. A visibility region is associated with each robot, and the goal is to guarantee that the target will ultimately lie in at least one visibility region. Both a formal characterization of the general problem and several interesting problem instances are presented. A complete algorithm for computing the motion strategy of the robots is also presented, and is based on searching a finite cell complex that is constructed on the basis of critical information changes. A few computed solution strategies are shown. Several bounds on the minimum number of needed robots are also discussed.

Original languageEnglish (US)
Pages (from-to)737-742
Number of pages6
JournalProceedings - IEEE International Conference on Robotics and Automation
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1997 IEEE International Conference on Robotics and Automation, ICRA. Part 3 (of 4) - Albuquerque, NM, USA
Duration: Apr 20 1997Apr 25 1997

ASJC Scopus subject areas

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


Dive into the research topics of 'Finding an unpredictable target in a workspace with obstacles'. Together they form a unique fingerprint.

Cite this