Multiplayer Reach-Avoid Differential Games with Defender-Side Information Delay

Technical Summary: Multiplayer Reach-Avoid Differential Games with Defender-Side Information Delay

Problem Formulation
This paper investigates a class of reach-avoid differential games involving multiple defenders and multiple attackers moving in a two-dimensional plane with bounded speeds. The core challenge addressed is the presence of defender-side information delay. In this setting, while attackers possess real-time state information, each defender $D_i$ observes the states of other agents (both other defenders and attackers) with a constant time delay $\tau_i$. Consequently, defenders base their control decisions on the past positions of attackers ($t-\tau_i$) rather than their current positions.

The game involves $N$ defenders and $M$ attackers. Attackers aim to reach a convex closed target region $T$, while defenders aim to capture attackers (within a radius $r_i$) before they reach $T$. If an attacker is captured, the defenders seek to maximize the distance of the capture point from $T$, while the attacker seeks to minimize this distance. The game terminates when all attackers are either captured or have entered the target region. The authors assume specific initial conditions to ensure the game is well-posed: defenders are initially stationary during the delay interval, attackers start outside the target region, defenders are faster than attackers ($\bar{v}_D > \bar{v}_A$), and initial distances are sufficient to prevent immediate capture before the delay period ends.

Methodology
The authors employ a geometric approach combined with convex analysis and game-theoretic equilibrium concepts to solve the problem.

1. One-Attacker-One-Defender Analysis:

   • Attack Region Characterization: The authors first derive an explicit analytical characterization of the "delayed attack region" ($R_{total}^A$). This region represents the set of points an attacker can guarantee reaching no later than the defender, accounting for the defender's reaction lag.
   • Convexity Proof: Using a specific curvature analysis of the boundary defined by the distance constraints and delay parameters, the paper proves that this attack region is a convex set under mild assumptions.
   • Optimal Strategies: Based on the convex attack region, the authors formulate a convex optimization problem to find the capture point (the point in the attack region closest to the target region). The optimal strategies for both players are derived as moving at maximum speed in a straight line toward this capture point.
   • Equilibrium Verification: The paper establishes that these strategies constitute a subgame-perfect Nash equilibrium (SPNE). This is proven by dividing the game into two stages (before and after the defender enters the game) and using backward induction to show optimality at every stage.

2. Extension to Multiplayer Scenarios:

   • One-Attacker-Multiple-Defenders: The attack region is defined as the intersection of the individual attack regions between the attacker and each defender. The capture point is determined by solving a convex optimization problem subject to constraints from all defenders. The authors note that, consistent with prior work, at most two defenders are sufficient to determine the capture point under optimal play.
   • Multi-Attacker-Multi-Defender: The problem is extended to a general $N$-vs-$M$ setting. The authors incorporate "delay-aware pairwise winning relations" (determining if a specific defender can guarantee capturing a specific attacker) into a maximum matching formulation. This allows for the optimal assignment of defenders to attackers to maximize the number of captures.

Key Contributions
The paper makes the following specific contributions:

1. Mathematical Formulation: It proposes a rigorous formulation of reach-avoid games where defenders operate with delayed information regarding attacker positions.
2. Analytical Characterization: For the one-on-one case, it derives an explicit analytical representation of the delayed attack region and proves its convexity, a non-trivial result given the time-delay dynamics.
3. Optimal Strategies and Equilibrium: It derives optimal strategies for both players and proves they form a subgame-perfect Nash equilibrium, addressing the sequential nature of the game induced by the delay.
4. Scalability: The framework is extended to one-attacker-multiple-defender and general multi-agent scenarios, providing strategies for capture point computation and defender-attacker assignment via maximum matching.

Results
Numerical simulations were conducted using MATLAB to validate the theoretical findings across three scenarios:

• One-vs-One: Simulations confirmed that the proposed optimal strategies outperform both pure-attack and pure-defense benchmark policies. Specifically, unilateral deviations by either player resulted in worse outcomes for the deviating player, validating the equilibrium nature of the strategies.
• One-vs-Multiple: Simulations with one attacker and two defenders demonstrated that cooperative strategies among defenders could achieve better performance (minimizing the attacker's distance to the target) compared to a single defender acting alone.
• Multi-Agent: A three-attacker-three-defender scenario illustrated the effectiveness of the maximum matching approach. The simulation showed defenders successfully assigning themselves to attackers they could guarantee capturing, while the unassigned attacker successfully reached the target region.

Significance and Claims
The paper claims to be the first to provide optimal strategies for reach-avoid games specifically under the condition of defender-side information delay. While previous works have addressed delays in attackers or standard reach-avoid games, this work fills a gap in the literature regarding how defenders can optimally mitigate performance degradation when their information is inherently delayed.

The authors emphasize that their approach moves beyond the difficulty of solving the high-dimensional Hamilton-Jacobi-Isaacs (HJI) equation directly. Instead, by leveraging the geometric structure of the delayed attack region and its convexity, they provide a tractable, verification-based analytical framework. This allows for the efficient computation of winning conditions and equilibrium strategies in scenarios that are otherwise analytically intractable. The work is positioned as a step toward more realistic modeling of adversarial systems (such as military or aerospace applications) where communication and processing latencies are unavoidable.