Abstract
We present an algorithm for a single pursuer with one flashlight searching for an unpredictable, moving target in a 2D environment. The algorithm decides whether a simple polygon with n edges and m concave regions can be cleared by the pursuer, and if so, constructs a search schedule of length O(m) in time O(m2 + m log n + n). The key ideas in this algorithm include a representation called "visibility obstruction diagram" and its "skeleton": a combinatorial decomposition based on a number of critical visibility events. An implementation is presented along with a computed example.
Original language | English (US) |
---|---|
Pages (from-to) | 87-113 |
Number of pages | 27 |
Journal | International Journal of Computational Geometry and Applications |
Volume | 12 |
Issue number | 1-2 |
DOIs | |
State | Published - 2002 |
Keywords
- Motion planning
- Pursuit-evasion
- Robotics
- Sensing
- Visibility
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Theory and Mathematics
- Computational Mathematics
- Applied Mathematics