In a classic pursuit-evasion game, a pursuer attempts to capture an evader within a bounded environment. While intuition suggests that the pursuer simply needs to be faster, research into geometric pursuit-evasion reveals that capture is less about raw velocity and more about the systematic restriction of the evader's reachable space. By treating the environment as a series of partitions and the pursuers as dynamic barriers, agents can guarantee capture even in complex, obstacle-filled polygons.
The Guarding Line as a Dynamic Barrier
The most fundamental mechanism for restricting an evader is the guarding line. Kyle Klein and Subhash Suri demonstrate in Complete Information Pursuit Evasion in Polygonal Environments that a single pursuer can turn a geometric path into an impassable barrier.
This works through a projection strategy: the pursuer maintains a position that mirrors the evader’s projection onto a designated boundary or chord. By staying "ahead" of this projection, the pursuer ensures they can reach any point on the line before the evader can cross it. This effectively bisects the environment, trapping the evader in a sub-region and preventing "recontamination"—the act of an evader slipping back into a previously cleared area.
Recursive Partitioning and Geodesic Convexity
In complex environments with obstacles, a single guarding line is rarely enough. Instead, pursuers must use a leapfrog strategy. As explored by Andrew Beveridge and Volkan Isler in A Leapfrog Strategy for Pursuit-Evasion in a Polygonal Environment, two pursuers can coordinate to systematically clear a polygon. One pursuer guards a "frontier" line while the other moves to clear a sub-region. Once the sub-region is safe, the pursuers swap roles, advancing the frontier.
The success of this partitioning relies on geodesic convexity. For a guarding strategy to be robust, the shortest path between any two points in a sub-region must not exit that region. If this property holds, the pursuer’s projection-based movement remains valid, and the evader cannot exploit the "shadows" of obstacles to bypass the guard.
Apollonius Circles and the Speed Advantage
When agents have different maximum speeds, the geometry of capture shifts from simple lines to Apollonius circles. An Apollonius circle defines the boundary of the "reachable set"—the region a pursuer can reach before a faster or slower evader.
Venkata Ramana Makkapati and Chen Wang show that even slower pursuers can guarantee capture by coordinating to overlap their Apollonius regions. In Cooperative Pursuit With Multi-Pursuer and One Faster Free-Moving Evader, the authors explain that a team of slower robots can form a geometric enclosure. By maintaining a formation where the union of their Apollonius sectors covers all 360 degrees of the evader's potential headings, they create a shrinking "capture domain" from which the faster evader cannot escape.
From Vertex Capture to Topological Encirclement
While traditional models focus on the pursuer occupying the exact same vertex as the evader, recent work has shifted toward containment. In Primal-Dual Cops and Robber, Minh Tuan Ha and colleagues explore a game where cops move on the faces of a planar graph while the robber moves on vertices.
Capture is redefined as encirclement: the pursuers win if they occupy all the faces surrounding the robber's current vertex. This topological approach mirrors the geometric "moving wall" strategies used in continuous space. By securing the perimeter (the faces) rather than the point (the vertex), the pursuers neutralize the evader's mobility. Harmender Gahlawat further refines this in On the Cop Number of String Graphs by using convex path guarding, proving that identifying and securing convex structures within a graph's geometric representation acts as a force multiplier, allowing fewer pursuers to isolate an opponent.
Intuition of the Shrinking Safe Zone
The unifying logic across these papers is the gradient-based reduction of the safe-reachable set. Whether using Kamal Mammadov’s centroid-based control laws to shrink Apollonius arcs or Ubaldo Ruiz’s invariants to force an evader toward a boundary, the goal is the same:
- Partition: Use guarding lines or formations to divide the environment.
- Invariants: Maintain a geometric relationship (like a projection or angular sector) that the evader cannot break.
- Monotonicity: Ensure that every movement step reduces the area of the evader's reachable set.
By focusing on the geometry of the available space rather than the distance to the target, these strategies provide mathematical guarantees for capture in environments where simple chasing would fail.