PaperlayerView exact revision on arXiv

Source-linked AI summary

Cooperative Pursuit with Multi-Pursuer and One Faster Free-moving Evader

Xu Fang, Chen Wang, Lihua Xie, Jie Chen

arXiv:2001.04731v2eess.SYcs.SY

TL;DR

The paper addresses how multiple pursuers can capture a faster evader that moves freely, despite prior methods often constraining the evader. It proposes distributed encirclement and approach strategies, with sufficient capture conditions based on initial positions and speed ratios. Under those conditions, the analysis guarantees capture regardless of the evader’s strategy.

  • Problem

    For a faster free-moving evader, the paper asks how to form an encirclement, balance it with approach, and guarantee capture from initial spatial distributions.

    Source: §I · p. 2

  • Method

    The paper proposes distributed pursuit that assigns surrounding and hunting tasks to balance encirclement formation with approaching the evader.

    Source: §I · p. 2, §VIII · p. 9

  • Results

    Under the stated sufficient conditions, the faster free-moving evader is captured regardless of its strategy.

    Source: §V · p. 7

  • Takeaways & Limitations

    The proposed algorithms form and maintain an encirclement while balancing that objective with approaching the evader.

    Source: C. Problem Description · p. 3, §VIII · p. 9

Abstract

from arXiv · show

This paper addresses a multi-pursuer single-evader pursuit-evasion game where the free-moving evader moves faster than the pursuers. Most of the existing works impose constraints on the faster evader such as limited moving area and moving direction. When the faster evader is allowed to move freely without any constraint, the main issues are how to form an encirclement to trap the evader into the capture domain, how to balance between forming an encirclement and approaching the faster evader, and what conditions make the capture possible. In this paper, a distributed pursuit algorithm is proposed to enable pursuers to form an encirclement and approach the faster evader. An algorithm that balances between forming an encirclement and approaching the faster evader is proposed. Moreover, sufficient capture conditions are derived based on the initial spatial distribution and the speed ratios of the pursuers and the evader. Simulation and experimental results on ground robots validate the effectiveness and practicability of the proposed method.

I. INTRODUCTION

The paper tackles cooperative capture of a faster evader that can move freely, where prior approaches often constrain the evader and individual pursuit can leave group-level escape gaps. It introduces encirclement and approach strategies and defines geometric notions for assessing which evader directions pursuers can cover.

I. INTRODUCTION

  • Free movement makes capture challenging: existing faster-evader methods impose constraints, and individual success can come at the cost of an escapable group gap.The paper frames three open problems: continuous-space encirclement, balancing encirclement with approach, and conditions guaranteeing capture from random initial distributions.Source: §I · pp. 1–2
  • The contributions are a distributed encirclement algorithm, a method balancing surrounding and hunting tasks, and sufficient capture conditions based on initial positions and speed ratios.The paper builds on its earlier overlapping-angle work.Source: §I · p. 2

II. PRELIMINARIES AND PROBLEM DESCRIPTION

  • The setup uses an evader-centered coordinate system and a single-integrator model for pursuers, without assuming a kinematic model for the evader.The pursuers’ maximum speeds are compared with the faster evader’s speed; the evader’s direction and escape strategy are unavailable to them.Source: A. Occupied Angle · p. 2

A. Occupied Angle

  • A pursuer’s occupied angle is the wedge between tangents from the evader to its Apollonius circle, representing evader directions that pursuer can capture.The occupied angle depends only on the pursuer-to-evader speed ratio.Source: A. Occupied Angle · p. 3

B. Coverage Angle, Overlapping Occupied Angle and Escapable Angle

Adjacent pursuers’ angular coverage determines whether the evader has overlapping capture directions or an escapable wedge. The group occupied angle summarizes the directions collectively covered by the pursuers.

B. Coverage Angle, Overlapping Occupied Angle and Escapable Angle

  • For adjacent pursuers ordered by polar angle, the coverage angle is defined from their occupied angles and their angular separation.The pursuers are considered in counterclockwise ascending polar-angle order.Source: B. Coverage Angle, Overlapping… · p. 3
  • A nonpositive coverage angle is an overlapping occupied angle, while a positive one is an escapable angle that neither adjacent pursuer covers.The evader can be captured by either pursuer when moving within an overlapping occupied angle.Source: B. Coverage Angle, Overlapping… · p. 3
  • The group occupied angle describes the directions collectively dominated by the pursuers; full coverage occurs when it equals 2π.The paper defines group success rate in terms of whether all free-moving evader directions are occupied.Source: B. Coverage Angle, Overlapping… · p. 3

C. Problem Description

The problem considers heterogeneous-speed pursuers whose faster evader’s direction and escape strategy are unknown. Pursuers must trade off increasing group coverage through encirclement against closing distance to the evader.

C. Problem Description

  • The setting has a faster evader, heterogeneous pursuer speeds, unknown evader direction and strategy, and capture defined by entering a non-zero capture radius.The objective is to find cooperative velocity controls that bring at least one pursuer within that radius.Source: C. Problem Description · p. 3
  • Because the evader’s direction is unknown, pursuers must both increase group success through encirclement and decrease their distances to the evader.The paper identifies a trade-off between these aims.Source: C. Problem Description · p. 3
  • The ensuing approach presents encirclement and hunting algorithms, then balances their objectives.Encirclement increases group success rate; hunting decreases pursuer distances to the evader.Source: C. Problem Description · p. 4

III. ENCIRCLEMENT ALGORITHM

The distributed encirclement algorithm coordinates pursuers’ angular motion to surround the evader. When the group occupied angle reaches 2π and all coverage angles are nonpositive, it can trap and keep the evader within the union of their capture domains.

III. ENCIRCLEMENT ALGORITHM

  • The algorithm assumes pursuers are angularly ordered around the evader and can access its position and those of their two nearest neighbors.Nearest neighbors are identified by their polar-angle ordering.Source: §III · p. 4
  • Each pursuer adjusts its polar angle according to the difference between neighboring coverage angles, increasing the group occupied angle by filling escapable angles.The pursuers’ surrounding direction is perpendicular to the hunting direction.Source: §III · p. 4
  • When θG = 2π and every coverage angle ϵi,i+1 ≤ 0, the algorithm traps and keeps the evader within the union of the pursuers’ capture domains.Under this condition, the maximum group success rate P = 1 is achieved.Source: §III · p. 5

IV. VELOCITY CONTROL AND TRADE-OFF ALGORITHM

The velocity control combines a surrounding component with a hunting component. This lets pursuers try to trap the faster evader while also approaching it.

A. Velocity Control

  • The hunting law decreases each pursuer’s distance to the evader according to a positive hunting coefficient.Its radial-distance rule is ˙ri = −hiri.Source: A. Velocity Control · p. 5
  • The distributed velocity control combines surrounding and hunting components so pursuers try both to trap the evader and to approach it.The surrounding component is designed to increase group success rate, while hunting decreases the pursuer’s distance to the evader.Source: A. Velocity Control · p. 5
  • Because surrounding and hunting act in perpendicular directions as independent processes, choosing their coefficients requires a trade-off.The surrounding component forms an encirclement; the hunting component approaches the evader.Source: A. Velocity Control · p. 5

B. Trade-off Algorithm

The trade-off algorithm selects how much each pursuer surrounds versus hunts. Its coefficient increases with angular motion and is concave with respect to distance to the evader.

B. Trade-off Algorithm

  • The surrounding coefficient is kept positive, and the surrounding and hunting coefficients are time-varying parameters.When the angular-coverage imbalance or βi is zero, the surrounding coefficient is set to ki = 1.Source: B. Trade-off Algorithm · p. 5
  • The trade-off coefficient βi is designed to increase with |˙αi| and be concave with respect to ri.The surrounding and hunting coefficients are determined by βi.Source: B. Trade-off Algorithm · p. 5
  • A pursuer with a large angular-rate magnitude is assigned more surrounding, while one with a small magnitude focuses more on hunting.The angular rate reflects the difference between adjacent coverage angles.Source: B. Trade-off Algorithm · pp. 5–6
  • Even at the maximum surrounding factor, βi remains below π/2, so the pursuer retains a hunting component.The choice of trade-off coefficient is flexible; the paper presents one solution.Source: B. Trade-off Algorithm · p. 6

V. CAPTURE CONDITION

The capture condition combines a polygon-edge bound with spacing and collision-avoidance constraints to keep the faster evader inside the pursuers’ capture domains. Under the stated initial conditions, capture follows regardless of the evader’s strategy.

V. CAPTURE CONDITION

  • An edge length no greater than 2dcλmin makes the group occupied angle θG equal 2π when the evader is inside the polygon.Here λmin is the minimum pursuer-to-evader speed ratio.Source: §V · p. 6
  • Distance-maintenance and inter-collision-avoidance potentials are incorporated into the pursuers’ velocity control to preserve polygon edges while respecting safe spacing.The distance-maintenance bound is Rf; the collision-avoidance set concerns pursuers within the specified safe-distance region.Source: §V · pp. 6–7
  • With the evader initially inside the n-pursuer polygon, the velocity control law guarantees capture if the four stated initial spacing, safety, and neighbor-set conditions hold.The theorem states capture regardless of the faster free-moving evader’s strategy.Source: §V · p. 7
  • The initial conditions require polygon-neighbor distances below Rf, other neighbor distances above Ro, and Ro < Rb < Rc < Rf ≤ 2dcλmin.They also require each pursuer’s two polygon neighbors to belong to its neighbor set.Source: §V · p. 7
  • The Lyapunov argument keeps polygon-neighbor distances below Rf and other neighbor distances above Ro, yielding full group-angle occupancy and eventual capture.The proof uses the divergence of the Lyapunov function at those distance boundaries together with a nonpositive derivative.Source: §V · p. 7
  • Unlike the cited existing condition requiring equal maximum speeds and an evenly distributed initial formation, the proposed conditions require polygon distance maintenance.The comparison is with the sufficient capture conditions cited as.Source: §V · pp. 7–8

A. Pursuit-evasion Game Simulation without Distance Maintenance

The three-pursuer simulation uses a pursuer-to-evader speed ratio of 0.9. It specifies the agents’ initial positions, capture distance, and pursuer-neighbor range.

A. Pursuit-evasion Game Simulation without Distance Maintenance

1) Strategy of the Evader:

In the simulation, the evader reacts more responsively to nearer pursuers. The pursuers first form an encirclement, then hunt after group occupancy reaches 2π, and ultimately capture the evader.

1) Strategy of the Evader:

2) The effects of Speed Ratio on Pursuit-evasion Game:

The simulations examine how speed ratio affects escape and whether twelve pursuers can capture a faster evader while maintaining distance and avoiding collisions. Ground-robot experiments and the conclusion report cooperative capture and sufficient conditions based on initial spatial distribution and speed ratios.

2) The effects of Speed Ratio on Pursuit-evasion Game:

VII. EXPERIMENTS

  • Four micro-ground robots used embedded computing boards, ZigBee communication, and an external camera-positioning system for localization.The proposed velocity control law was treated as cooperative path planning for the robots.Source: §VII · p. 8

B. Pursuit-evasion Game Simulation with Distance Maintenance and Inter-collision Avoidance

  • At λ_i=0.95, twelve pursuers maintained a group occupied angle of 2π and ultimately captured the evader while maintaining inter-pursuer distances and avoiding collisions.Theorem 2 guarantees capture regardless of the evader’s strategy under the stated initial configuration and velocity control law.Source: B. Pursuit-evasion Game Simulation… · p. 8, Figure 10 · p. 9

VII. EXPERIMENTS

  • Ground-robot experiments achieved cooperative capture despite unknown evader direction and escape strategy; the evader’s slowdown while turning gave pursuers an opportunity.The evader was manually controlled to test unpredictable motion.Source: §VII · pp. 8–9

VIII. CONCLUSION

  • The proposed distributed algorithm forms and maintains an encirclement, balances encirclement with approach, and derives sufficient capture conditions from initial spatial distribution and speed ratios.The encirclement traps and keeps the faster evader within the union of the pursuers’ capture domains.Source: §VIII · p. 9
Loading 2001.04731v2…