Autonomous Observers
Stanford CS Robotics Lab
Visibility-Based Motion Strategies for Pursuing an Evading Target
This work concerns 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 have been
obtained. For a simply-connected free space, a logarithmic bound is
established on the minimum of robots needed. A complete algorithm for
computing the motion strategy of the robots has been developed, and is
based on searching a finite cell complex that is constructed on the
basis of critical information changes. A few computed solution
strategies have been obtained.
Related Papers
Finding an Unpredictable Target in a
Workspace with Obstacles by Steven M. LaValle, David Lin,
Leonidas J. Guibas, Jean-Claude Latombe, and Rajeev Motwani.
To appear in Proc. 1997 IEEE International Conference on Robotics and
Automation. (Postscript version)
Computed Examples
Select an example from the popup menu in the java applet and
then press the play button to see the solution.
Last modified: Fri Mar 7 17:14:02 1997