Visibility-based pursuit-evasion with bounded speed.

*(English)*Zbl 1194.93155
Akella, Srinivas (ed.) et al., Algorithmic foundation of robotics VII. Selected contributions of the seventh international workshop on the algorithmic foundations of robotics (WAFR 2006), New York, NJ, USA, July 16–18, 2006. Berlin: Springer (ISBN 978-3-540-68404-6/hbk; 978-3-540-68405-3/ebook). Springer Tracts in Advanced Robotics 47, 475-489 (2008).

Summary: This paper presents an algorithm for a visibility-based pursuit-evasion problem in which bounds on the speeds of the pursuer and evader are given. The pursuer tries to find the evader inside of a simply-connected polygonal environment, and the evader in turn tries actively to avoid detection. The algorithm is at least as powerful as the complete algorithm for the unbounded speed case, and with the knowledge of speed bounds, generates solutions for environments that were previously unsolvable. Furthermore, the paper develops a characterization of the set of possible evader positions as a function of time. This characterization is more complex than in the unbound-speed case, because it no longer depends only on the combinatorial changes in the visibility region of the pursuer.

For the entire collection see [Zbl 1155.93004].

For the entire collection see [Zbl 1155.93004].