PaperlayerView exact revision on arXiv

Source-linked AI summary

An Introduction to Pursuit-evasion Differential Games

Isaac E. Weintraub, Meir Pachter, Eloy Garcia

arXiv:2003.05013v1math.OC

TL;DR

Pursuit-evasion research needs strategies that account for intelligent adversaries rather than restricted opponent behavior. This paper introduces differential games through seminal and recent literature organized by player count, then studies representative multiplayer games. It concludes that cooperation is central to synthesizing saddle-point strategies and improving team performance.

  • Problem

    Pursuit-evasion problems require robust strategies against intelligent adversaries whose behavior is not restricted to predefined actions.

  • Method

    The paper surveys seminal and recent pursuit-evasion differential games by player count and analyzes two representative multiplayer case studies using strategy synthesis and verification tools.

  • Results

    The case studies verify a two-pursuer-one-evader solution and show that multiplayer saddle-point strategies require cooperation among agents on the same team.

  • Takeaways & Limitations

    Cooperation is both a theoretical requirement for multiplayer saddle-point equilibria and a practical means of improving team performance.

Abstract

from arXiv · show

Pursuit and evasion conflicts represent challenging problems with important applications in aerospace and robotics. In pursuit-evasion problems, synthesis of intelligent actions must consider the adversary's potential strategies. Differential game theory provides an adequate framework to analyze possible outcomes of the conflict without assuming particular behaviors by the opponent. This article presents an organized introduction of pursuit-evasion differential games with an overview of recent advances in the area. First, a summary of the seminal work is outlined, highlighting important contributions. Next, more recent results are described by employing a classification based on the number of players: one-pursuer-one-evader, N-pursuers-one-evader, one-pursuer-M-evaders, and N-pursuer-M-evader games. In each scenario, a brief summary of the literature is presented. Finally, two representative pursuit-evasion differential games are studied in detail: the two-cutters and fugitive ship differential game and the active target defense differential game. These problems provide two important applications and, more importantly, they give great insight into the realization of cooperation between friendly agents in order to form a team and defeat the adversary.

I. INTRODUCTION

Pursuit-evasion differential games formalize adversarial conflicts and seek strategies that remain effective against unrestricted intelligent opponents. This paper introduces the field, surveys seminal and recent work, and emphasizes cooperation in multiplayer games.

  • Pursuit-evasion models conflicts between pursuers and evaders, with applications including surveillance, navigation, biology, robotics, and combat.
  • Differential game theory addresses intelligent adversaries by synthesizing saddle-point strategies with guaranteed performance against opposing strategies.
  • Multiplayer differential games require cooperation for saddle-point synthesis, and the paper uses two case studies to illustrate strategy synthesis, verification, and team coordination.
  • The paper surveys seminal contributions from Isaacs, Bellman, Pontryagin, and others, covering dynamic programming, variational methods, and constrained optimal control.
  • Recent literature is organized by player count, including one-to-one, N-pursuer-one-evader, one-pursuer-M-evader, and N-pursuer-M-evader games.
  • Classical examples include the Homicidal Chauffeur and Two Cars games, which study capture, escape, and barrier regions under maneuverability and turning-radius constraints.

5) Pursuit Evasion in Aerial Engagements:

The literature extends pursuit-evasion differential games from aircraft and naval engagements to increasingly complex teams of pursuers and evaders. These studies address capture, escape, task allocation, coordination, and capture sequencing.

  • Pursuit Evasion in Aerial Engagements: Aerial and naval applications use differential games to model missile-aircraft and other tactical engagements with realistic kinematic and control objectives.
  • N Pursuers, 1 Evader: In N-pursuer-one-evader games, Voronoi diagrams allocate tasks by identifying regions where a pursuer can intercept the evader faster than others.
  • N Pursuers, 1 Evader: Prior work also developed approximate, fuzzy-logic, and task-allocation methods for coordinating multiple agents and handling fixed or free capture sequences.
  • 1 Pursuer, M Evaders: One-pursuer-M-evader games study capture ordering, with the pursuer seeking finite-time capture while evaders coordinate to prolong escape.
  • 1 Pursuer, M Evaders: For a superior pursuer, sequential capture of multiple evaders and total capture time are central objectives.
  • N Pursuers, M Evaders: N-pursuer-M-evader games support more complex engagements, including military air operations, bodyguard-versus-bandit scenarios, and Voronoi-based task allocation.

IV. TWO CUTTERS AND FUGITIVE SHIP DIFFERENTIAL GAME

This section introduces the two-cutters and fugitive ship differential game and frames the HJI PDE as a verification tool for state-feedback saddle-point strategies.

  • Game and verification framework: Two faster cooperative pursuers seek minimum-time capture while the evader seeks to maximize capture time.The game uses state-feedback policies and a performance functional defined over the players’ dynamics.
  • Game and verification framework: The HJI PDE provides sufficient conditions for verifying a candidate Value function and synthesizing optimal strategies from its gradient.The paper focuses on verification after obtaining the Value function.
  • Game and verification framework: The verification theorem establishes a saddle-point equilibrium for state-feedback policies when a C1 Value function satisfies the HJI PDE and terminal condition.The resulting feedback strategies are written as u*=μ*(t,x(t)) and v*=ν*(t,x(t)).
  • Game and verification framework: The section first formulates the dynamics and performance functional before applying the verification result to the two-cutters game.The formulation includes controls, state evolution, and the terminal payoff structure.

A. Problem Formulation

The problem models one evader and two faster holonomic pursuers with simple motion, point capture, and opposing objectives over capture time.

  • Players and dynamics: One evader and two pursuers move holonomically with constant speeds, with both pursuers faster than the evader.The pursuers’ normalized speeds are β1 and β2, each greater than 1.
  • Objectives and termination: The evader maximizes capture time while the cooperative pursuers minimize it.The performance functional represents the terminal capture time.
  • Objectives and termination: Cooperation can reduce capture time relative to either pursuer acting alone, although a single pursuer may fail to prevent escape from a specified domain.The formulation motivates adding a second cooperating pursuer in bounded-influence or exit scenarios.
  • Players and dynamics: The complete state consists of the Cartesian coordinates of the evader and both pursuers in R6.The controls are the instantaneous heading angles φ, ψ1, and ψ2.
  • Objectives and termination: The game terminates under point capture when either pursuer reaches the evader, including simultaneous capture by both.The terminal state is defined at time tf when any listed capture condition holds.

B. Solution

The solution derives constant optimal headings and separates outcomes into single-pursuer and simultaneous-capture cases, using Apollonius-circle intersections for the latter.

  • Derivation of optimal strategies: The Hamiltonian formulation introduces six co-states and derives optimal controls in terms of those co-state variables.The co-states correspond to the six components of the game state.
  • Derivation of optimal strategies: All co-states are constant, so optimal controls and player trajectories are constant-heading straight lines.This follows from the co-state dynamics and the simple-motion model.
  • Single-pursuer cases: Because β1 and β2 exceed 1, each pursuer has a unique heading solution for every evader heading.The converse does not hold: some pursuer headings correspond to running away from the evader.
  • Single-pursuer cases: When only one capture condition is active, the two-pursuer game reduces to the corresponding one-pursuer-one-evader solution.The evader heads directly away from the active pursuer under the stated optimal strategy.
  • Simultaneous capture: The complete solution checks the individual capture cases first and then tests simultaneous capture when neither individual condition applies.The resulting saddle-point strategies determine which pursuer captures the evader or whether both capture simultaneously.
  • Simultaneous capture: When simultaneous capture is active, the evader selects the farther intersection of two Apollonius circles, producing equal capture times for both pursuers.Each circle is determined by the initial evader-pursuer distance and the corresponding speed ratio.

C. Verification

The verification partitions the state space by capture outcome and proves that the proposed Value function is C1 and satisfies the HJI equation throughout the regular regions.

  • State-space partition: The capture set is partitioned into R1, R2, and Rs, representing capture only by P1, only by P2, and simultaneous capture.The regions are characterized by the individual capture conditions and their boundaries.
  • Value function: The Value function represents capture time under optimal play and takes different forms across the capture regions.In Rs, the simultaneous-capture condition is tf1(φ*) = tf2(φ*).
  • Dispersal surface: The dispersal surface D is the subset where the two Apollonius-circle intersections are equally distant from the evader, yielding two optimal strategies.Regular solutions are considered on R = R1 ∪ R2 ∪ R−s, excluding D from Rs.
  • HJI verification: Theorem 2 concludes that the Value function is continuous, continuously differentiable, and HJI-consistent over the regular state space R.The result applies to the proposed solution of the two-pursuer-one-evader differential game.
  • Value function: The Value function is C1 inside R1, R2, and Rs and remains continuous and differentiable across the region boundaries.The proof explicitly establishes boundary continuity and matching derivatives.
  • HJI verification: The candidate Value function satisfies the HJI equation in R1, R2, and Rs.The verification substitutes the optimal feedback headings into the equation in each region.

D. Dispersal Surface and Multi-Pursuer Multi-Evader Differential Game

The section examines dispersal surfaces and cooperative assignments in multi-pursuer, multi-evader games. It shows how strategy selection affects trajectories and how assignment constraints determine the minimum time to capture all evaders.

  • Dispersal Surface: Multiple optimal solutions place the example state on a dispersal surface, where teams must choose among competing strategies.The example uses E = (5, 0), P1 = (0, 0), P2 = (24, −4), with speeds vE = 1, vP1 = 1.25, and vP2 = 1.3125.
  • Dispersal Surface: Opposite initial strategy choices move the game from the dispersal surface into a regular subspace, requiring the Pursuers to recompute their solution.The Pursuers initially head south while the Evader heads north; the resulting trajectory is shown in Fig. 5.
  • Multi-Pursuer Multi-Evader Game: Cooperative two-Pursuer teams reduce capture time compared with a single Pursuer and support approximate solutions for multi-pursuer, multi-evader games.The multi-agent objective is to minimize the capture time of the last Evader while assigning each Pursuer to exactly one Evader.
  • Multi-Pursuer Multi-Evader Game: Under 2−2−1 assignments, each Pursuer can serve only one Evader, constraining feasible combinations and their capture times.For example, assigning P1 to E1 prevents assigning P1 to E2 or E3; the best capture times cited are 28.46 for E2 and 35.00 for E1 under the respective constraints.
  • Multi-Pursuer Multi-Evader Game: The best assignment is {P1E1}, {P2P3E2}, {P4P5E3}, capturing all Evaders by 28.46 time units.The corresponding capture times are 20.01, 28.46, and 19.97, and no other combination reduces the overall time.

A. Overview

Active target defense differential games model cooperation between a maneuvering Target and Defender against an Attacker. The literature uses outcome and distance-based metrics and extends the problem through geometric, multi-Defender, information-limited, and sensor-based analyses.

  • Active Target Defense: Active target defense has three players: a Target pursued by an Attacker and a Defender pursuing the Attacker.The Target and Defender cooperate when the Target can maneuver, while the Attacker opposes them.
  • Performance Metrics: Game-of-kind analyses ask whether the Target evades capture, while game-of-degree analyses measure separation when interception or capture occurs.Reported metrics include Attacker–Target range at Defender interception and Defender–Attacker distance when the Target is captured.
  • Prior Work: Prior work introduced target-defense formulations involving counter-weapons, defensive missiles, and active-target defense scenarios.These studies extend earlier two-player target-reaching and target-avoidance differential games.
  • Prior Work: Apollonius-circle geometry was used to derive Defender interception strategies and identify a critical Target/Attacker speed ratio for target survival.Later studies considered two Defenders, nonzero Defender capture radius, restricted information, proportional navigation, pure pursuit, and sensor models.

B. Problem Formulation

The active target defense problem is formulated as a three-player simple-motion game in the plane. The Target and Defender share a control input against the Attacker, with terminal conditions determined by which player captures the other.

  • Problem Formulation: The game contains a Target, Attacker, and Defender moving in the Euclidean plane with constant speeds and heading controls.The states are Cartesian coordinates, while φ, χ, and ψ denote the Target, Attacker, and Defender headings.
  • Problem Formulation: The Target–Defender team controls uT,D = {φ, ψ}, while the Attacker controls uA = {χ}.The reduced-state formulation uses the combined Target–Defender control against the Attacker’s heading control.
  • Problem Formulation: The dynamics are ordinary differential equations specifying each player’s Cartesian velocity from its heading and speed.The Attacker and Defender have unit-speed components, while the Target moves with speed ratio α.
  • Terminal Conditions: The game terminates when the Attacker captures the Target or the Defender intercepts the Attacker.Target–Attacker coincidence gives the Attacker victory; Attacker–Defender coincidence gives the Target–Defender team victory.
  • Terminal Conditions: For the game of degree, the cost functional is evaluated subject to the specified terminal condition.The formulation focuses on the case in which the game-of-degree condition applies.

C. Game of Kind

The game of kind determines which team wins from the initial state and parameters. In the reduced state space, a boundary separates states where the Target is guaranteed to escape from states where optimal Attacker play prevents escape.

  • Game of Kind: A game of kind determines which team wins under given initial conditions and problem parameters.Its solution answers whether the Target–Defender team or the Attacker wins.
  • Winning Regions: In the reduced state space, xT < 0 guarantees Target escape, while xT > 0 is partitioned into escape and capture regions.The escape region Re contains states where optimal Target–Defender strategies guarantee evasion; Rc contains states where the Target cannot escape under optimal Attacker play.
  • Winning Regions: For 0 < α < 1, an equation defines the boundary separating the two outcome regions in (xA, xT, yT).This boundary is the solution to the game of kind in the active target defense game of degree.
  • Winning Regions: The boundary manifold B is the boundary of the region Re in which the Target is guaranteed to escape.For fixed xA > 0, its cross-section is described as the right branch of a hyperbola when xT > 0.

D. Game of Degree

The game-of-degree analysis derives optimal strategies for the active target defense differential game using Pontryagin’s Maximum Principle and reduced-state optimization. In the escape region, optimal headings and the aimpoint are characterized through straight-line trajectories and a quartic equation.

  • Optimality conditions: The two-sided PMP synthesizes strategies in which the Target and Defender cooperate to maximize terminal range while the Attacker minimizes it.The formulation treats the game as zero-sum with cooperative objectives for T and D.
  • Problem formulation: The active target defense game uses a reduced state space with speed ratio 0 ≤ α < 1 to derive state-feedback optimal headings in the escape region.The reduced state is (x_A, x_T, y_T), with x_A > 0 and y_T ≥ 0.
  • Optimal trajectories: Constant co-states yield constant optimal controls, so the regular optimal trajectories of the Attacker, Defender, and Target are straight lines.This follows from the co-state dynamics and the resulting constant controls.
  • Geometric solution: The optimal target heading is φ* = ξ, where ξ is determined by the collinear geometry of T, Tf, and the aimpoint y.The terminal time and geometry are obtained from the straight-line construction in Fig. 7.
  • Aimpoint characterization: The optimal aimpoint y* on the orthogonal bisector of AD is a real solution of a quartic equation.The quartic has two real solutions y1 and y2, with y1 ≤ yT ≤ y2; the selected root depends on the sign of xT.
  • Verification status: Verification of the saddle-point strategies is available for the escape region, whereas verification in the capture region remains a topic of current research.The capture-region treatment has only preliminary results and a candidate solution.

VI. CONCLUDING REMARKS

The paper surveys pursuit-evasion differential games across player configurations and emphasizes cooperation within teams. Its concluding examples show how differential game theory supports analysis of multi-player conflicts and cooperative strategies.

  • Scope and cooperation: The survey covers games with one or multiple pursuers and evaders, emphasizing cooperation among members of the same team.It discusses N-pursuers-1-evader, 1-pursuer-M-evaders, and N-pursuer-M-evaders configurations.
  • Scope and cooperation: Cooperative behavior improves team performance and is necessary for synthesizing saddle-point equilibrium strategies in multi-player games.The conclusion links cooperation directly to the construction of equilibrium strategies.
  • Applications: The paper formulates two multi-player pursuit-evasion problems as differential games to illustrate cooperative solution methods.These examples highlight both the cooperative aspect and the methods available through differential game theory.
Loading 2003.05013v1…