Smarter lions: Efficient cooperative pursuit in general bounded arenas

Zhengyuan Zhou, Jonathan R. Shewchuk, Dušan Stipanović, Haomiao Huang, Claire J. Tomlin

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)1229-1256
Number of pages28
JournalSIAM Journal on Control and Optimization
Volume58
Issue number2
DOIs
StatePublished - 2020

Keywords

  • Control theory
  • Differential games
  • Pursuit-evasion

ASJC Scopus subject areas

  • Control and Optimization
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Smarter lions: Efficient cooperative pursuit in general bounded arenas'. Together they form a unique fingerprint.

Cite this