Advanced Search

Journal Navigation

Journal Home

Subscriptions

Archive

Contact Us

Table of Contents

Sign In to gain access to subscriptions and/or personal tools.
The International Journal of Robotics Research
This Article
Right arrow Full Text (PDF)
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to Saved Citations
Right arrow Download to citation manager
Right arrowRequest Permissions
Right arrow Request Reprints
Right arrow Add to My Marked Citations
Citing Articles
Right arrow Citing Articles via HighWire
Right arrow Citing Articles via Google Scholar
Right arrow Citing Articles via Scopus
Google Scholar
Right arrow Articles by Sachs, S.
Right arrow Articles by Rajko, S.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Complore   Add to Connotea   Add to Del.icio.us   Add to Digg   Add to Reddit   Add to Technorati   Add to Twitter  
What's this?

Visibility-Based Pursuit-Evasion in an Unknown Planar Environment

Shai Sachs

Dept. of Computer Science University of Illinois Urbana, IL 61801, USAssachs{at}uiuc.edu

Steven M. LaValle

Dept. of Computer Science University of Illinois Urbana, IL 61801, USAlavalle{at}uiuc.edu

Stjepan Rajko

Dept. of Computer Science Iowa State University Ames, IA 50011, USA stipe{at}iastate.edu

We address an on-line version of the visibility-based pursuit-evasion problem. We take a minimalist approach in modeling the capabilities of a pursuer robot. A point pursuer moves in an unknown, simplyconnected, piecewise-smooth planar environment, and is given the task of locating any unpredictable, moving evaders that have unbounded speed. The evaders are assumed to be points that move continuously. To solve the problem, the pursuer must for each target have an unobstructed view of it at some time during execution. The pursuer is equipped with a range sensor that measures the direction of depth discontinuities, but cannot provide precise depth measurements. All pursuer control is specified either in terms of this sensor or wall-following movements. The pursuer does not have localization capability or perfect control. We present a complete algorithm that enables the limited pursuer to clear the same environments that a pursuer with a complete map, perfect localization, and perfect control can clear (under certain general position assumptions). Theoretical guarantees that the evaders will be found are provided. The resulting algorithm to compute this strategy has been implemented in simulation. Results are shown for several examples. The approach is efficient and simple enough to be useful towards the development of real robot systems that perform visual searching.

Key Words: sensor-based planning • visibility • pursuitevasion • on-line algorithms • surveillance • bug algorithms • sensing uncertainty

The International Journal of Robotics Research, Vol. 23, No. 1, 3-26 (2004)
DOI: 10.1177/0278364904039610
Add to CiteULike CiteULike   Add to Complore Complore   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us   Add to Digg Digg   Add to Reddit Reddit   Add to Technorati Technorati   Add to Twitter Twitter    What's this?


This article has been cited by other articles:


Home page
 The International Journal of Robotics ResearchHome page
B. Tovar and S. M. LaValle
Visibility-based Pursuit--Evasion with Bounded Speed
The International Journal of Robotics Research, November 1, 2008; 27(11-12): 1350 - 1360.
[Abstract] [PDF]

Home page
 The International Journal of Robotics ResearchHome page
S. Suri, E. Vicari, and P. Widmayer
Simple Robots with Minimal Sensing: From Local Visibility to Global Geometry
The International Journal of Robotics Research, September 1, 2008; 27(9): 1055 - 1067.
[Abstract] [PDF]

Home page
 The International Journal of Robotics ResearchHome page
A. Kolling and S. Carpin
Cooperative Observation of Multiple Moving Targets: an algorithm and its formalization
The International Journal of Robotics Research, September 1, 2007; 26(9): 935 - 953.
[Abstract] [PDF]