A complete pursuit-evasion algorithm for two pursuers using beam detection

Abstract

We present an algorithm for a pair of pursuers, each with one rotating beam (flashlight, laser or a camera), searching for an unpredictable, moving target in a 2D environment (simple polygon). Given a polygon with n edges, the algorithm decides in time O(n/sup 4/) whether it can be cleared by the pursuers, 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.