PaperlayerView exact revision on arXiv

Source-linked AI summary

Multiple Pursuer Multiple Evader Differential Games

Eloy Garcia, David W. Casbeer, Alexander Von Moll, Meir Pachter

arXiv:1911.03806v1math.OC

TL;DR

The paper studies how cooperating pursuers and evaders can be modeled in a multiplayer border-defense differential game. It derives cooperative assignments and state-feedback strategies, obtaining a continuously differentiable Value function that satisfies the Hamilton-Jacobi-Isaacs equation.

  • Problem

    The paper addresses multiplayer border-defense conflicts in which pursuers must capture cooperating evaders.

  • Method

    It jointly designs cooperative pursuer-to-evader assignments, pursuit-evasion strategies, and continuous-time state-feedback strategies.

  • Results

    The Value function V(x) is C1 and satisfies the Hamilton-Jacobi-Isaacs partial differential equation, yielding a complete solution over state-feedback strategies.

  • Takeaways & Limitations

    The work provides a formal differential-game solution for multiplayer border-defense conflicts under optimal play and deviations from optimal play.

Abstract

from arXiv · show

In this paper an N-pursuer vs. M-evader team conflict is studied. The differential game of border defense is addressed and we focus on the game of degree in the region of the state space where the pursuers are able to win. This work extends classical differential game theory to simultaneously address weapon assignments and multi-player pursuit-evasion scenarios. Saddle-point strategies that provide guaranteed performance for each team regardless of the actual strategies implemented by the opponent are devised. The players' optimal strategies require the co-design of cooperative optimal assignments and optimal guidance laws. A representative measure of performance is proposed and the Value function of the game is obtained. It is shown that the Value function is continuous, continuously differentiable, and that it satisfies the Hamilton-Jacobi-Isaacs equation - the curse of dimensionality is overcome and the optimal strategies are obtained. The cases of N=M and N>M are considered. In the latter case, cooperative guidance strategies are also developed in order for the pursuers to exploit their numerical advantage. This work provides a foundation to formally analyze complex and high-dimensional conflicts between teams of N pursuers and M evaders by means of differential game theory.

I. INTRODUCTION

The paper formulates a cooperative yet non-cooperative multi-player Border Defense Differential Game in which N pursuers must capture M evaders before they reach a border. It provides a complete state-feedback solution combining optimal guidance and assignments while overcoming the curse of dimensionality.

  • Problem formulation: The BDDG divides players into cooperating pursuer and evader teams that optimize opposing team performance.Cooperation occurs within each team, while the opposing teams remain non-cooperative.
  • Problem formulation: Pursuers must capture evaders before they reach the border, requiring state feedback, guidance strategies, and optimal N-pursuer-to-M-evader assignments.Assignments form a discrete combinatorial decision alongside continuous guidance and maneuver decisions over space and time.
  • Objective and contribution: The team-cooperative optimal solution is implementable in real time and can exploit non-optimal adversary strategies and maneuvers.The evaders seek the border and, if captured beforehand, minimize combined terminal distance from it, while pursuers maximize that metric.
  • Solution approach: The method overcomes the curse of dimensionality, making Isaacs’ method applicable without approximating the optimal solution over the complete state space.The paper claims a closed-form solution for the operationally relevant multi-player BDDG.
  • Solution approach: The complete BDDG solution derives state-feedback optimal strategies, obtains the Value function V (x), and shows that V (x) is C1 and satisfies the HJI PDE.These results establish the paper’s claimed exact solution of the game.

II. THE GAME

This section formulates an N-pursuer versus M-evader border-defense differential game that co-designs state-feedback guidance with discrete pursuer–evader assignments. Within the pursuers’ winning region, saddle-point strategies robustly determine capture behavior and terminal outcomes.

  • Game formulation: The game co-designs cooperative state-feedback guidance strategies and discrete assignments determining which pursuer captures each evader.Each team cooperatively selects instantaneous headings, while binary variables encode pursuer–evader assignments.
  • Game formulation: The game ends when an evader reaches the border or is captured, and the terminal time is when the last evader is captured.The analysis considers point capture in the region where capture of all evaders is guaranteed.
  • Optimal strategies: Saddle-point state-feedback strategies provide robust pursuer capture regardless of the evaders’ implemented guidance laws and remain effective against adversarial maneuvers.The strategies can be implemented online and are the paper’s main result.
  • Optimal strategies: Under optimal play, each player maintains a constant heading and follows a straight-line trajectory.This result is stated as Theorem 1 for the cooperative differential game.

III. 2 VS. 2 DIFFERENTIAL GAME

For the 2-versus-2 border-defense game, the solution jointly determines the optimal pursuer–evader assignment and state-feedback headings. The Value function is explicitly characterized, satisfies the HJI equation, and is continuous but loses continuous differentiability on the dispersal surface.

  • Theorem 2: The theorem provides the optimal assignment and state-feedback headings for all four players in the 2-versus-2 differential game.The game assumes αij = vEj/vPi < 1.
  • Value function: The Value function is V(x) = ys1(x) when ys1 > ys2 and V(x) = ys2(x) when ys2 > ys1; it satisfies the HJI equation.The construction uses the lowest point on each pursuer–evader Apollonius circle as the optimal interception point.
  • Dispersal surface: The Value function is continuous and continuously differentiable except on the dispersal surface ys1(x) = ys2(x), where both assignments are optimal but differentiability fails.At the surface, V(x) = ys1(x) = ys2(x).
  • Optimal assignment: The two candidate assignments pair P1 with E1 and P2 with E2, or P1 with E2 and P2 with E1; the optimal assignment maximizes the corresponding payoff.The assignment costs are ys1 and ys2, respectively, and the optimal choice is ι∗ = arg maxι=1,2 ysι.
  • Implications: The dispersal surface benefits pursuers: choosing a different assignment does not reduce their performance, whereas evaders can incur a potentially large cost increase from assuming the wrong assignment.Away from the surface, each agent can compute the complete saddle-point solution independently; on the surface, one communication event is needed for deconfliction.

IV. MULTI-AGENT DIFFERENTIAL GAME

This section extends the BDDG to multi-agent games with N pursuers and M evaders, treating the cases N = M and N > M. It introduces feasible-assignment enumeration and cooperative guidance between two pursuers to intercept an evader.

  • Multi-agent formulation: The BDDG is extended to conflicts involving N pursuers and M evaders.The section addresses the multi-agent formulation directly.
  • Case structure: The analysis considers both N = M and N > M cases.The N = M case is presented first, followed by the more general N > M case.
  • N > M: For N > M, cooperative guidance between two pursuers is used to intercept an evader.The larger-pursuer case develops cooperation specifically for interception.

A. Case: N = M

For N = M, the analysis enumerates assignments capable of potentially capturing all evaders and derives the game’s Value function and optimal assignment. The Value function satisfies the HJI equation and yields state-feedback strategies through the selected assignment.

  • A. Case: N = M: Feasible assignments are enumerated as matchings in which all evaders can be potentially captured.Assignments that fail this condition are excluded; in the example, four feasible assignments are listed.
  • A. Case: N = M: The Value function is continuous, continuously differentiable except on dispersal surfaces, and satisfies the HJI equation.The theorem assumes α_ij = v_Ej/v_Pi < 1 and x ∈ R^P.
  • A. Case: N = M: The game Value function is V(x) = maxι y_sι(x), with optimal assignment ι* = arg maxι Aι.The assignment index ranges over the feasible assignments.
  • A. Case: N = M: The selected assignment determines the corresponding optimal state-feedback strategies and aimpoints for each matched evader–pursuer pair.The strategies are specified for pairs E_j/P_i under the optimal assignment.

B. Case: N > M

For N > M, pursuers exploit their numerical advantage through cooperative pursuit, optimal assignments, and cooperatively designed guidance strategies. The resulting solution characterizes capture geometry and yields a continuous Value function satisfying the HJI equation.

  • Cooperative pursuit: When N > M, cooperative pursuit exploits the pursuers’ numerical advantage and can capture evaders farther from the border than non-cooperative pursuit.With two pursuers against one evader, cooperation can also prevent the evader from reaching the x-axis when a single pursuer cannot.
  • Cooperative pursuit: Cooperation restricts an evader’s dominance region to the intersection of the pursuers’ Apollonius circles, rather than either circle alone.In the two-pursuer example, the smallest-y point is the circles’ intersection, whereas single-pursuer assignment lets the evader reach the x-axis.
  • Optimal strategies: The saddle-point solution combines the best cooperative assignment with cooperative heading strategies, while evaders head toward the lowest point of their assigned dominance regions.The optimal assignment determines each evader’s dominance region and the corresponding team strategies.
  • Simultaneous capture: Intersection of two Apollonius circles is necessary but not sufficient for simultaneous capture; in the example, optimal play captures the evader only by P2.The lower intersection point has y-coordinate 7.846, above the lowest point on the EP2 circle at (8.511, 7.642).
  • Value function and theorem: Theorem 4 gives V (x) = maxι ysι(x), with optimal assignment ι∗= arg maxι Aι; the Value function is continuous, continuously differentiable, and satisfies the HJI equation.Differentiability can fail at dispersal surfaces ysι = ysι′.

V. EXAMPLES

The examples show that optimal assignment and closed-loop guidance jointly produce the game value, while deviations by either team change capture outcomes and performance. In particular, correct assignment without optimal guidance can still prevent successful interception, whereas incorrect pursuer assignment yields a lower payoff.

  • Example 1.1: Comparing ys1(x) = 10.696 with ys2(x) = 8.288 gives the optimal assignment µ11 = µ22 = 1 and V (x) = ys1(x) = 10.696.Assignment is selected once at engagement start, while guidance is computed in closed-loop form.
  • Example 1.1: Under optimal play, the optimal aimpoints are time-invariant and the resulting trajectories are straight lines.Computing the optimal aimpoints along the optimal trajectories produces the same result.
  • Example 1.3: With the correct assignment but Pure Pursuit guidance, P2 intercepts E2 near the x-axis while P1 fails to capture E1 before the border.The result demonstrates significant performance degradation from omitting optimal guidance even when assignment is correct.

VI. EXTENSIONS

The section extends the 2-versus-2 border-defense differential game to pursuers without prior assignment commitment, deriving robust state-feedback strategies and a guaranteed payoff. It also identifies future extensions involving richer combat roles and cooperation-driven assignment switching.

  • Future extensions: Future research will examine decoys, sacrificial players, and players with different levels of importance.The section also notes open questions about when switching assignments benefits pursuers, dispersal surfaces, and curved evader trajectories.
  • No commitment: The 2-versus-2 BDDG is analyzed without the restriction that pursuers commit to their initial assignment.The result applies when αij = vEj/vPi < 1 and x ∈ RP.
  • No commitment: The pursuers’ strategies are robust state-feedback strategies for the game without commitment.Their guaranteed payoff is ys, selected as ys1(x) when ys1 > ys2 and ys2(x) when ys2 > ys1.
  • No commitment: By choosing the best assignment, the pursuers guarantee the payoff ys regardless of the evaders’ implemented strategies.For a fixed assignment, evaders head toward the lowest point on the corresponding circles, while pursuers aim at the same point; ys is only a lower bound, not the game value.
  • Cooperation and switching: Relaxing initial commitment enables cooperation and switching, allowing two pursuers to intercept an evader farther from the border and later pursue different opponents.One pursuer can eventually capture the evader while the other becomes free to switch assignments.

VII. CONCLUSIONS

The paper formulates large-scale multiplayer border-defense pursuit-evasion as a hybrid differential game that jointly solves pursuer-evader assignments and continuous-time pursuit and evasion strategies. Its complete solution covers continuous state-feedback strategies and discrete binary assignments, with simulations showing effectiveness and robustness under optimal and nonoptimal play.

  • Contributions: The study analyzes joint optimal assignment of pursuers to evaders together with optimal pursuit and evasion strategies in a two-team multiplayer border-defense game.The border-defense scenario is posed as a differential game.
  • Contributions: The hybrid differential game is solved over continuous-time state-feedback strategies and discrete binary assignment variables.This extends beyond classical differential games that seek only state-feedback strategies.
  • Results: Simulation examples demonstrate solution effectiveness and robustness under optimal play and when one or more players deviate from optimal strategies or assignments.The robustness result includes deviations in strategies, assignments, or both.
  • Extensions: The paper delineates extensions and emphasizes differential game theory for pursuit-evasion problems requiring assignment of pursuers to evaders.The extensions are presented as a basis for addressing assignment-dependent pursuit-evasion problems.

VIII. APPENDIX · A. Border defense with 3P and 1E

For border defense with three pursuers and one evader, the interception point is the lowest point of the evader’s reachable region under optimal play. The analysis identifies capture configurations, redundant assignments, and conditions ensuring saddle-point state-feedback strategies exist.

  • A. Border defense with 3P and 1E: Three pursuers maximize, while the evader minimizes, the terminal distance between the interception point and the closest point to the border.The border is the x-axis of the Cartesian frame.
  • A. Border defense with 3P and 1E: The interception point is the lowest point of the evader’s reachable region, constructed from corresponding segments associated with the three pursuers.This point is unique in general.
  • A. Border defense with 3P and 1E: Capture occurs either through one pursuer, placing the lowest point on a reachable-region arc, or simultaneously through two pursuers, placing it at two Apollonius circles’ intersection.These are the two stated capture cases.
  • A. Border defense with 3P and 1E: In the representative optimal-play case, only P1 and P2 capture the evader at I1,2, while P3 is not needed for the engagement.The interception point is denoted I1,2.
  • A. Border defense with 3P and 1E: When three circles share the lowest intersection point, one pursuer is redundant because removing it leaves the interception point unchanged.In the illustrated case, either P1 or P3 can choose not to participate.
  • A. Border defense with 3P and 1E: Assigning a third pursuer to a single evader does not improve the pursuer group’s payoff, so such assignments need not be considered.The conclusion follows from the unchanged interception point when the redundant pursuer abstains.
  • A. Border defense with 3P and 1E: Because the interception point is unique, no singular surfaces arise and saddle-point state-feedback strategies exist.This conclusion is stated for the general border-defense formulation in this subsection.

B. Assignment problem

The assignment problem is formulated as a linear program with one-to-one pursuer–evader assignments solvable by the Hungarian algorithm. Fixed initial assignments yield saddle-point feedback strategies and a game Value, whereas dynamic reassignment has only a lower bound on evader cost; the method also extends to cases with more pursuers than evaders.

  • Assignment formulation: The multi-pursuer multi-evader assignment problem is formulated as a Linear Program.For N = M, the formulation uses assignment variables indicating whether pursuer i is assigned to evader j.
  • Assignment formulation: For N = M, constraints require each evader to be engaged by exactly one pursuer and each pursuer to be assigned to exactly one evader.These are the assignment constraints represented by (44) and (45).
  • Solution method: The assignment problem can be solved using the Hungarian algorithm.The cited algorithm applies to Problem (43)–(45).
  • Game-theoretic implications: Committing pursuers to their initial assignment yields saddle-point state-feedback strategies and an existing Value of the game.Dynamic reassignment can exploit evader errors and trajectories reaching a dispersal surface, but the Value has not been found; evaders have a lower bound J for their cost.
  • More pursuers than evaders: When N > M, the assignment algorithm can assign up to two pursuers, but not more, to one evader.The distances from interception points to the border must be calculated for these assignments.
Loading 1911.03806v1…