An algorithm for searching a polygonal region with a flashlight
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 0(m(2) + 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.
visibility pursuit-evasion motion planning robotics sensing