Encirclement Guaranteed Finite-Time Capture against Unknown Evader Strategies
Authors: Dinesh Patra, Prajakta Surve, Ashish R. Hota, Shaunak D. Bopardikar
Organizations: Department of Electrical Engineering, IIT Kharagpur, India · Department of Electrical and Computer Engineering, Michigan State University, USA
We consider a pursuit-evasion scenario involving a group of pursuers and a single evader in a two-dimensional unbounded environment. The pursuers aim to capture the evader in finite time while ensuring the evader remains enclosed within the convex hull of their positions until capture, without knowledge of the evader's heading angle. Prior works have addressed the problem of encirclement and capture separately in different contexts. In this paper, we present a class of strategies for the pursuers that guarantee capture in finite time while maintaining encirclement, irrespective of the evader's strategy. Furthermore, we derive an upper bound on the time to capture. Numerical results highlight the effectiveness of the proposed framework against a range of evader strategies.
Figures & tables
Fig. 1 : Examples of triangulation with an evader lying inside the convex hull of 3 pursuers (left) and 8 pursuers (right).
Fig. 2 : Range of strategies for the active pursuers that guarantee encirclement of the evader, regardless of its strategy, when vi=1 for all i∈[n] and μm≤1 . In this figure, the angles φ1 and φ2 are given by φ1=sin−1(μm) and φ2=π−sin−1(μm) . Thus, φl∈[φ1,φ2] , where l∈{j,k} and the angles are measured from the direction of the respective unit vectors towards the evader for pj and pk and considered as positive in the outward direction from H .
Fig. 3 : Encirclement guaranteed capture under the greedy policy of the evader with three pursuers. The evader moves away from the nearest pursuer at each instant throughout the pursuit. The evader is always encircled and is captured at t=1.25s .
Fig. 4 : Encirclement guaranteed capture under the switching policy of the evader with three pursuers. The evader moves to the closest edge by 0.5s and switches between moving to the closest edge and moving towards the interior for every 0.15s . The evader is always encircled and is captured at 1.2s .
Fig. 5 : Encirclement guaranteed capture with three pursuers under random policies adopted by a human-like evader. The evader remains encircled and is captured at 1.19s .
Fig. 6 : Encirclement guaranteed capture under the closest link policy of the evader with three pursuers. The evader moves to the closest edge and remains on the edge until it is captured at t=1.15s .
Fig. 7 : Performance under the closest link policy of the evader with the encirclement guaranteed sector set based robust MPC approach in [ 14 ] . The evader moves to the closest edge and remains on the edge. While the pursuers are able to maintain encirclement, it takes around t=42s for capture, due to the rigid sector constraints.
Fig. 8 : Evolution of the areas of the subtriangles A12 , A23 , and A31 formed by the pursuer and evader positions during pursuit under the closest link policy of the evader. The areas remain non-negative at all times, confirming that encirclement is maintained. Furthermore, A31=0 from approximately 0.4s onward, indicating that the edge p3p1 remains active for the rest of the pursuit.
Fig. 9 : Distance between the nearest pursuer and the evader over time under the proposed strategy and the EGSS-based robust MPC approach in [ 14 ] . The proposed approach achieves capture much faster compared to the approach in [ 14 ] .
Fig. 10 : Empirical distribution, mean and standard deviation of the ratio ( τ ) of the numerical capture time ( tsim ) and theoretical upper bound ( tc ) under the closest link policy of the evader with pursuers initialized at (0,2) , (−1,0) , and (0.8,0) , while the evader’s initial position is drawn uniformly at random from the interior of the triangle formed by the pursuers. It is found that τ<1 ( tsim<tc ) in each case and the bound is more conservative for μm=0.9 compared to μm=0.2 in line with the theoretical findings.
Policy
Theoretical Bound
Numerical Capture Time
Greedy
3.10
1.25
Switching
3.10
1.2
Random
3.10
1.19
Stationary
0.93
0.5
Closest Link
3.10
1.15
TABLE I : Comparison of Theoretical Bounds and Numerical Capture Times (in seconds). The bound for the stationary policy is obtained by assuming μm=0 (which results in the tightest bound), while for all other cases, μm=0.7 .