⚡ electrical engineering

Encirclement Guaranteed Finite-Time Capture against Unknown Evader Strategies

This paper proposes a novel class of pursuit strategies that guarantee finite-time capture of an unknown evader in a two-dimensional environment while ensuring the evader remains enclosed within the pursuers' convex hull throughout the engagement, regardless of the evader's tactics.

Original authors: Dinesh Patra, Prajakta Surve, Ashish R. Hota, Shaunak D. Bopardikar

Published 2026-03-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dinesh Patra, Prajakta Surve, Ashish R. Hota, Shaunak D. Bopardikar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a game of "Red Light, Green Light" played in an open field, but with a twist: you are a team of security guards (the pursuers) trying to catch a sneaky intruder (the evader).

Here is the challenge:

The Goal: You must catch the intruder.
The Rule: At every single moment before you catch them, the intruder must be trapped inside a "virtual fence" formed by your team. You can't just chase them from behind; you have to surround them so they can't slip out the side.
The Problem: You don't know what the intruder is thinking. They might run fast, run slow, zigzag, or stand still. You only know their maximum possible speed.

This paper presents a clever, mathematically proven strategy for the security team to win this game no matter how the intruder tries to escape.

The Core Idea: The "Rubber Band" Triangle

To understand the strategy, imagine the security team forms a shape around the intruder. If there are three guards, they form a triangle. If there are eight, they form an octagon. The intruder is always inside this shape.

The authors use a concept called Triangulation. They imagine drawing invisible lines from the intruder to every pair of guards standing next to each other. This creates a bunch of little triangles filling the space between the guards and the intruder.

The "Area" Trick: The team constantly calculates the area of these triangles.
The Danger Zone: If the intruder tries to escape, they will try to push one of these triangles flat until its area becomes zero (meaning the intruder has reached the line between two guards).
The Counter-Move: The moment the intruder touches the line between two guards (making that triangle's area zero), those two specific guards switch tactics. Instead of just running straight at the intruder, they angle their movement slightly outward.

Think of it like a flexible net. If the intruder pushes against one part of the net, the two people holding that part of the net don't just pull back; they step sideways to tighten the mesh, ensuring the intruder can't slip through the hole.

The Two-Phase Strategy

The paper divides the chase into two modes:

The "Chase" Mode (Interior Phase):
As long as the intruder is safely in the middle of the group, every guard simply runs directly toward the intruder. This is the most efficient way to close the distance.
The "Blockade" Mode (Edge Phase):
The moment the intruder gets close to the imaginary line between two guards, those two guards switch to a special "blocking" maneuver. They don't just run at the intruder; they run at a specific angle that guarantees the intruder cannot cross the line, even if the intruder is running at full speed.

Analogy: Imagine you are holding a rope with a friend, and a ball is rolling toward the rope. If you both just pull the rope straight back, the ball might slip past the side. But if you both step slightly outward while pulling, you create a wider, tighter barrier that the ball can't get past.

Why This is a Big Deal

Previous methods had a flaw: they were either good at surrounding the intruder but slow to catch them, or good at catching them but might accidentally let them slip out of the "fence" if they changed direction suddenly.

This paper solves both problems at once:

Guaranteed Containment: The math proves that as long as the guards follow this specific angle rule, the intruder can never escape the convex hull (the shape formed by the guards).
Guaranteed Capture: It also proves that if the guards are faster than the intruder, they will catch them in a specific amount of time. The authors even calculated a "worst-case" time limit (like a countdown timer) that tells you exactly how long the chase will take at most.

The Results: Speed vs. Old Methods

The authors tested their strategy against a computer simulation with different types of "intruders":

The Greedy intruder (always runs away from the closest guard).
The Switching intruder (jumps between running to the edge and running to the center).
The Random intruder (moves unpredictably, like a human).

In every case, the new strategy caught the intruder in about 1 to 1.25 seconds.

They compared this to an older, more complex method (called Robust MPC) that tries to predict the intruder's moves. That old method took 42 seconds to catch the same intruder!

The Takeaway

This paper gives a team of robots (or security guards) a simple, decentralized rulebook:

Surround the target.
Run straight at them when they are in the middle.
Angle outward when they touch the edge.

By following these simple geometric rules, the team creates an inescapable trap that shrinks down until the intruder is caught, all without needing to know the intruder's next move. It turns a chaotic chase into a predictable, mathematically guaranteed victory.

1. Problem Statement

The paper addresses a pursuit-evasion problem in a two-dimensional, unbounded planar environment ( $\mathbb{R}^2$ ) involving:

Agents: A team of $n$ pursuers ( $n \geq 3$ ) and a single evader.
Dynamics: Both pursuers and the evader move with constant maximum speeds ( $v_i$ for pursuers, $\mu_m$ for the evader). The pursuers control their heading angles, while the evader controls both its speed and heading.
Constraints & Assumptions:
- The evader's specific strategy (speed and heading at any instant) is unknown to the pursuers, though its maximum speed $\mu_m$ is known.
- The pursuers are initialized such that the evader is already inside their convex hull ( $e(0) \in H(0)$ ).
- Pursuers are assumed to be non-redundant (all contribute to the convex hull).
Objectives: The pursuers must achieve two simultaneous goals:
1. Encirclement: Maintain the evader strictly within the convex hull of the pursuers' positions at all times ( $e(t) \in H(t)$ ).
2. Finite-Time Capture: Guarantee that at least one pursuer reaches a distance $r_c$ (capture radius) from the evader within a finite time $t_c$ , regardless of the evader's strategy.

2. Methodology

The authors propose a decentralized control strategy based on geometric triangulation and Lyapunov stability analysis.

A. Area-Based Encirclement Condition

The core of the encirclement logic relies on triangulating the convex hull formed by the pursuers and the evader.

Triangulation: The convex hull is divided into $n$ triangles, each formed by the evader ( $e$ ) and two consecutive pursuers ( $p_j, p_k$ ).
Signed Area ( $A_{jk}$ ): The area of triangle $\triangle ep_jp_k$ $△ e p_{j} p_{k}$ is defined with a specific sign convention (counter-clockwise ordering).
- $A_{jk} > 0$ : Evader is inside the hull.
- $A_{jk} = 0$ : Evader is on the edge $p_jp_k$ (active edge).
- $A_{jk} < 0$ : Evader has escaped through the edge.
Encirclement Guarantee: To prevent escape, the time derivative of the area must be non-negative ( $\dot{A}_{jk} \geq 0$ ) whenever the evader is on an active edge ( $A_{jk}=0$ ).
Active Edge Strategy: When an edge becomes active, the two corresponding pursuers switch from standard pursuit to a specific maneuver. They move such that their velocity vectors form specific angles ( $\phi_j, \phi_k$ $ϕ_{j}, ϕ_{k}$ ) relative to the direction of the evader.
- Condition: Encirclement is guaranteed if $v_j d_{ek} \sin \phi_j + v_k d_{ej} \sin \phi_k \geq d_{jk} \mu_m$ .
- Simplified Strategy: If all pursuers have unit speed ( $v_i=1$ ) and $\mu_m \leq 1$ , the pursuers simply move outward from the edge at angles $\phi \in [\sin^{-1}(\mu_m), \pi - \sin^{-1}(\mu_m)]$ . This is a decentralized decision requiring only local position knowledge.

B. Finite-Time Capture Strategy

Once encirclement is guaranteed, the authors derive conditions to ensure the distance between the pursuers and the evader shrinks to zero in finite time.

Assumption: Pursuers are strictly faster than the evader ( $v_i = 1 > \mu_m$ ).
Lyapunov Function: The authors define $V = \sum_{i=1}^n \|p_i - e\|$ , the sum of distances from all pursuers to the evader.
Two-Phase Control Law:
1. Interior Phase: When the evader is strictly inside the hull, all pursuers use Pure Pursuit (heading directly toward the evader).
2. Edge Phase: When the evader touches an edge, the active pursuers switch to the specific "encirclement strategy" (moving outward at angle $\phi$ ), while inactive pursuers continue pure pursuit.
Convergence Proof: By analyzing $\dot{V}$ , the authors show that the Lyapunov function decreases at a constant rate bounded by $-n(1-\mu_m)$ . This ensures finite-time convergence to the capture radius $r_c$ .
Upper Bound: An explicit analytic upper bound on the capture time $t_c$ is derived:
$t_c \leq \frac{V_0 - n r_c}{n(1 - \mu_m)}$
where $V_0$ is the initial sum of distances.

3. Key Contributions

Unified Framework: The paper bridges the gap between "encirclement" (keeping the target contained) and "capture" (reducing distance to zero), providing simultaneous guarantees for both.
Unknown Strategy Robustness: Unlike game-theoretic approaches that require knowledge of the opponent's objective, this strategy works against any evader strategy (including worst-case, random, or adaptive policies) without needing to predict the evader's next move.
Decentralized Implementation: The control laws are decentralized. Active pursuers only need to know the positions of the evader and their immediate neighbor on the active edge; no global coordination or centralized server is required.
Explicit Analytic Bounds: The paper provides a rigorous, closed-form upper bound on the capture time, a feature often missing in empirical or simulation-based approaches.
Geometric Insight: The use of signed triangle areas as a Lyapunov-like metric for encirclement offers a novel geometric perspective on containment problems.

4. Numerical Results

The authors validated the strategy using MATLAB simulations with 3 pursuers and 1 evader ( $\mu_m = 0.7$ m/s, $v_i = 1$ m/s, $r_c = 0.3$ m).

Tested Evader Policies:
- Greedy: Moves away from the nearest pursuer.
- Switching: Alternates between moving to the closest edge and the interior.
- Random: Erratic, human-like unpredictable movement.
- Stationary: Does not move.
- Closest Link: Moves to and stays on the closest edge.
Performance:
- The proposed strategy successfully maintained encirclement and achieved capture in all scenarios.
- Capture Times: The actual capture times were significantly lower than the theoretical upper bounds (e.g., ~1.2s actual vs. 3.1s bound).
Comparison with State-of-the-Art:
- Compared against an Encirclement Guaranteed Sector Set (EGSS) based Robust MPC approach (from prior work [12]).
- Result: The proposed method captured the evader in ~1.15 seconds, whereas the MPC approach took ~42 seconds.
- Reason: The MPC approach suffered from rigid sector constraints that limited the pursuers' ability to move directly toward the evader during edge phases, whereas the proposed geometric strategy allows for more direct convergence while maintaining containment.

5. Significance

This work is significant for several reasons:

Theoretical Rigor: It provides the first simultaneous guarantees of encirclement and finite-time capture with an explicit time bound against unknown evader strategies.
Practical Applicability: The decentralized nature and lack of need for evader state prediction make it highly suitable for real-world applications like drone swarms, ground robot surveillance, and security perimeters where communication bandwidth is limited and the adversary is unpredictable.
Efficiency: The strategy is computationally lightweight (simple trigonometric calculations) and significantly faster than complex optimization-based methods like MPC, as demonstrated by the order-of-magnitude improvement in capture time.
Future Directions: The paper opens avenues for extending these geometric and Lyapunov-based techniques to 3D environments, multiple evaders, and scenarios with dynamic obstacles.