Finding an unpredictable target in a workspace with obstacles

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

Abstract

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 feast. 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.
BibTeX
@inproceedings{lavalle1997finding,
  author = {Steven M. LaValle and David Lin and Leonidas J. Guibas and Jean-Claude Latombe and Rajeev Motwani},
  title = {{Finding an unpredictable target in a workspace with obstacles}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {1997},
  doi = {10.1109/robot.1997.620123},
}

Loading related content...

Figure