CLEARING A POLYGON WITH TWO 1-SEARCHERS
We present an algorithm for a pair of pursuers, each with one flashlight, searching for an unpredictable, moving target in a 2D environment (simple polygon). Given a polygon with n edges and m concave regions, the algorithm decides in time O(n(2) + nm(2) + m(4)) whether the polygon can be cleared by the two 1-searches, and if so, constructs a search schedule. The pursuers are allowed to move on the boundary and in the interior of the polygon. They are not required to maintain mutual visibility throughout the pursuit.
visibility pursuit-evasion motion planning robotics sensing