Smarter Lions: Efficient Cooperative Pursuit in General Bounded Arenas
Zhengyuan Zhou, Jonathan Richard Shewchuk, Dušan M. Stipanović, Haomiao Huang, Claire J. Tomlin
Abstract
We study a full-knowledge pursuit-evasion problem where cooperating pursuers attempt to capture a single evader of equal (and without loss of generality, unit) speed in a closed, bounded, two-dimensional arena whose boundaries may be curved. By a famous result of Besicovitch, a point-sized lion (pursuer) can evade a single point-sized man (evader) indefinitely. If the lion is endowed with a capture radius in the form of an outstretched paw of length $r$, by a result of Alonso, Goldstein, and Reingold, the man can evade the lion for time that is superlinear in the diameter of circular arena. We propose a pursuit algorithm by which two pursuers can capture an evader in a simply connected arena in time that is linear in the diameter of the arena, even when the capture radius is zero. This algorithm is clearly asymptotically optimal, highlights the performance gap between one pursuer and two pursuers (even in a convex domain) and clearly establishes that no more than two pursuers are needed for optimal pursuit in simply-connected domains. Furthermore, we propose a pursuit algorithm by which three pursuers are guaranteed to capture an evader in a general two-dimensional arena with $h$ obstacles in time that is proportional to $hd$ (when capture radius is zero). To the best of our knowledge, this is the first algorithm that has provable capture guarantees at the generality of an arbitrary two-dimensional domain in continuous-time (the hardest case) and that, equally importantly, yields the best time-capture bounds (in comparison to the existing literature) when specialized to polygonal domains.