Visibility-based Pursuit-evasion with Limited Field of View
Top Cited Papers
- 1 April 2006
- journal article
- other
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 25 (4) , 299-315
- https://doi.org/10.1177/0278364906065023
Abstract
We study the visibility-based pursuit-evasion problem, in which one or more searchers must move through a given environment so as to guarantee detection of any and all evaders, which can move arbitrarily fast. Our goal is to develop techniques for coordinating teams of robots to execute this task in application domains such as clearing a building, for reasons of security or safety. To this end, we introduce a new class of searcher, the φ-searcher, which can be readily instantiated as a physical mobile robot. We present a detailed analysis of the pursuit-evasion problem using φ-searchers. We present the first complete search algorithm for a single φ-searcher, show how this algorithm can be extended to handle multiple searchers, and give examples of computed trajectories.Keywords
This publication has 25 references indexed in Scilit:
- Randomized Pursuit-Evasion in GraphsCombinatorics, Probability and Computing, 2003
- Dynamic Sensor Planning and Control for Optimally Tracking TargetsThe International Journal of Robotics Research, 2003
- Probabilistic pursuit-evasion games: theory, implementation, and experimental evaluationIEEE Transactions on Robotics and Automation, 2002
- Simple algorithms for searching a polygon with flashlightsInformation Processing Letters, 2002
- A VISIBILITY-BASED PURSUIT-EVASION PROBLEMInternational Journal of Computational Geometry & Applications, 1999
- Searching for a Mobile Intruder in a Polygonal RegionSIAM Journal on Computing, 1992
- Recent results in art galleries (geometry)Proceedings of the IEEE, 1992
- Min cut is NP-complete for edge weighted treesTheoretical Computer Science, 1988
- The complexity of searching a graphJournal of the ACM, 1988
- An efficient and simple motion planning algorithm for a ladder amidst polygonal barriersJournal of Algorithms, 1987