Visibility-based pursuit-evasion: the case of curved environments
- 20 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 3 (10504729) , 1677-1682
- https://doi.org/10.1109/robot.1999.770350
Abstract
We consider the problem of visually searching for an unpredictable target that can move arbitrarily fast in a simply-connected, curved, two-dimensional environment. A complete algorithm is presented that is guaranteed to find the elusive target if it is possible for a single pursuer. The key to the algorithm is a cell decomposition based on critical visibility events that occur because of inflections and bitangents of the environment boundary. We have implemented the cell decomposition algorithm, and show several computed examples. The technique is an extension and simplification of a previous technique for searching a polygonal environment. Our solution can also be considered as a step towards a unified approach to pursuit-evasion strategies that have little dependency on the representation of the environment.Keywords
This publication has 16 references indexed in Scilit:
- Minimizing width in linear layoutsPublished by Springer Nature ,2005
- Finding an unpredictable target in a workspace with obstaclesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- SEARCHING FOR A MOBILE INTRUDER IN A CORRIDOR —THE OPEN EDGE VARIANT OF THE POLYGON SEARCH PROBLEMInternational Journal of Computational Geometry & Applications, 1995
- On information invariants in roboticsArtificial Intelligence, 1995
- Recontamination does not help to search a graphJournal of the ACM, 1993
- Computing exact aspect graphs of curved objects: Algebraic surfacesInternational Journal of Computer Vision, 1992
- Monotonicity in graph searchingJournal of Algorithms, 1991
- Min cut is NP-complete for edge weighted treesTheoretical Computer Science, 1988
- Optimum watchman routesInformation Processing Letters, 1988
- The complexity of searching a graphJournal of the ACM, 1988