Source-linked AI summary
Cooperative Team Strategies for Multi-player Perimeter-Defense Games
Daigo Shishika, James Paulos, Vijay Kumar
TL;DR
Finding optimal team strategies for multiplayer perimeter defense is difficult, and the paper proposes a polynomial-time cooperative defense algorithm. It outperforms existing policies and is optimal under a numerical-advantage and initial-configuration condition.
Problem
The paper asks how to find optimal team strategies for a multi-player perimeter-defense reach-avoid game.
Source: §II · p. 2Method
The paper extends a decomposition method into a polynomial-time defense algorithm that incorporates cooperative behavior.
Source: §I · p. 1, §VIII · p. 8Results
The LGR defense policy runs in polynomial time, outperforms existing assignment-based policies, and is optimal under certain conditions.
Source: §I · p. 1, §VIII · p. 8Takeaways & Limitations
Pairing defenders to pursue an intruder from both sides accounts for cooperative defense and improves performance over maximum matching.
Source: §VIII · p. 8
Abstract
from arXiv · showhide
This paper studies a variant of the multi-player reach-avoid game played between intruders and defenders with applications to perimeter defense. The intruder team tries to score by sending as many intruders as possible to the target area, while the defender team tries to minimize this score by intercepting them. Finding the optimal strategies of the game is challenging due to the high dimensionality of the joint state space, and the existing works have proposed approximation methods to reduce the design of the defense strategy into assignment problems. However they suffer from either suboptimal defender performance or computational complexity. Based on a novel decomposition method, this paper proposes a scalable (polynomial-time) assignment algorithm that accommodates cooperative behaviors and outperforms the existing defense strategies. For a certain class of initial configurations, we derive the exact score by showing that the lower bound provided by the intruder team matches the upper bound provided by the defender team, which also proves the optimality of the team strategies.
I. INTRODUCTION
The paper addresses multi-player perimeter defense, where finding optimal team strategies is difficult and prior assignment-based approaches trade performance against computational complexity. It proposes a polynomial-time cooperative defense strategy and studies when the team strategies are optimal, then formulates the game and its assumptions.
I. INTRODUCTION
- Multi-player pursuit-evasion games have high-dimensional state spaces that can make Hamilton-Jacobi-Isaacs methods intractable; this paper studies their target-guarding reach-avoid variant.Intruders seek to reach the target without interception, while defenders aim to intercept or delay intrusion indefinitely.Source: §I · p. 1
- Earlier pairwise assignments can be suboptimal because they omit cooperative captures, while a prior pincer-based policy requires solving an NP-hard maximum-independent-set problem.The assignment approach provides an upper bound on the intruder’s score; the pincer policy improves defense performance but carries the computational burden.Source: §I · p. 1
- The proposed polynomial-time defense algorithm outperforms existing policies and has optimal team strategies when defenders have a numerical advantage and the initial configuration meets a condition.The optimality analysis matches the intruder team’s lower bound with the defender team’s upper bound.Source: §I · p. 1
II. PROBLEM STATEMENT
- The target is a convex planar region with an arc-length-parameterized perimeter, and defenders are constrained to move along that perimeter.Source: §II · p. 1
- The model assumes defenders are at least as fast as intruders and, for conciseness, considers fewer intruders than defenders.Source: §II · p. 2
- An intruder scores by reaching the target without capture, and a defender is eliminated after capturing one intruder.Source: §II · p. 2
- The problem asks for optimal team strategies mapping the shared, perfectly observed game state to defender and intruder controls.Source: §II · p. 2
III. BACKGROUND
The background reviews single- and paired-defender games and assignment-based defense. In the 1v1 game, directional barriers constrain intrusion; in the 2v1 game, cooperative pincer defense makes the intruder-winning region smaller than an independent-game estimate.
III. BACKGROUND
- The background reviews single defense against one intruder, pair defense against one intruder, and assignment-based strategies for multiplayer defense.Source: §III · p. 2
A. One v.s. One Game
- In a 1v1 game, the barrier has left and right sides: moving counter-clockwise or clockwise prevents penetration of the corresponding side from the defender-winning region.From that region, the defender can keep the intruder within it, preventing perimeter entry without capture.Source: A. One v.s. One Game · p. 2
B. Two v.s. One Game
- The actual 2v1 intruder-winning region is smaller than the intersection of the two independent 1v1 winning regions because the intruder must avoid both defenders simultaneously.Within the paired-defense region, defenders using a pincer maneuver drive the intruder into a defender-winning region before it reaches the perimeter.Source: B. Two v.s. One Game · p. 2
- From the actual 2v1 intruder-winning region, the intruder can reach the midpoint between the defenders before they can.Source: B. Two v.s. One Game · p. 3
C. Existing Assignment Strategies
Existing assignment methods convert capture opportunities into assignments, but either exclude cooperative defenses or incur high computational complexity. The paper’s local-game decomposition supports a polynomial-time score bound and evaluates team-strategy optimality using both defender and intruder bounds.
C. Existing Assignment Strategies
- Maximum Matching assigns at most one intruder to each defender through guaranteed-capture edges, but ignores cooperative 2v1 defenses.Its assignment graph connects a defender and intruder when capture can be guaranteed.Source: C. Existing Assignment Strategies · p. 3
- The prior MIS strategy adds defender pairs to model cooperative 2v1 defenses and avoid conflicting assignments, but its formulation is NP-hard.Its score bound satisfies QMIS ≤ QMM.Source: C. Existing Assignment Strategies · p. 3
- The proposed polynomial-time algorithm gives QLG ≤ QMIS ≤ QMM and considers optimality by comparing defender upper and intruder lower bounds.The paper reports that the lower and upper bounds match under a derived condition.Source: C. Existing Assignment Strategies · p. 3
IV. LOCAL GAME DECOMPOSITION
- Local-game decomposition partitions the game space into subregions, using LGRs for the intruder strategy and lower bound and I-LGRs for the defender strategy.Each subregion hosts a local game between defenders and intruders.Source: §IV · p. 3, A. Local Game Region · p. 3
B. Local Intrusion Strategy
The local intrusion strategy lets intruder subteams play separate games against boundary defenders. Their disjoint partition yields a teamwide lower bound on the score.
B. Local Intrusion Strategy
- Intruders in an LGR can play a 2v1 local game against its boundary defenders, beyond which defenders cannot reach them.The local game excludes defenders outside that LGR.Source: B. Local Intrusion Strategy · pp. 3–4
- If a local game has q_k > 0, the intruder team can guarantee at least q_k points; at most n_k^D intruders are captured.The remaining intruders score under the stated assumption that each defender captures at most one.Source: B. Local Intrusion Strategy · pp. 3–4
- Partitioning intruders into disjoint subteams and playing separate local games extends the lower-bound strategy to the full team.The optimal partition is considered next.Source: B. Local Intrusion Strategy · p. 4
C. Guaranteed Total Score
The section chooses a disjoint LGR partition to maximize the intruders’ guaranteed score. It gives the associated team strategy, computational bound, and the question of whether defenders can match that score.
C. Guaranteed Total Score
- The optimal partition G* maximizes Qlow(G), giving the guaranteed total score QLG.Combining the partition with local intrusion strategies yields the score lower bound.Source: C. Guaranteed Total Score · p. 4
- Values for QLG and G* can be obtained in O(N^4 D) time, and QLG > 0 exactly when some local score q_k is positive.The computation recognizes the optimization as a maximum-weight independent-set problem on a circular-arc graph.Source: C. Guaranteed Total Score · p. 4
- The intruder strategy teams agents according to G* and approaches the midpoint between the associated LGR boundary defenders, guaranteeing at least QLG.This is the lower bound defined by the optimal partition.Source: C. Guaranteed Total Score · p. 4
- The section leaves open whether defenders can prevent scores above QLG, directing that upper-bound question to Section VI.Here QLG is established as a lower bound guaranteed by the intruders.Source: C. Guaranteed Total Score · p. 4
V. EXTENDED ENGAGEMENT TYPES
The paper introduces implicit and sequential paired-defense engagements that use dynamically changing assignments beyond those captured by MM and MIS. It then extends the local game score framework and introduces the LGR defense policy.
V. EXTENDED ENGAGEMENT TYPES
- These engagement types use dynamically changing assignments that existing MM and MIS approaches fail to capture.The strategy section presents the LGR defense policy and analyzes its performance guarantees alongside the intruder strategy.Source: §V · p. 4, §VI · p. 5
A. Implicit Assignment Structure
- The implicit assignment structure pairs two defenders against one intruder while a second intruder lies in their shared implicit assignment zone.Although no defender is explicitly assigned to the second intruder, the greedy pursuit of the first guarantees its capture as well, resolving into two 1v1 assignments before either reaches the perimeter.Source: A. Implicit Assignment Structure · p. 4
B. Sequential Paired Defense Structure
- A sequential paired defense is an n + 1 vs. n engagement formed by n interrelated 2v1 games with overlapping defenders.Overlapping assignments are non-conflicting when they require the same direction of motion; in that case all intruders are captured.Source: B. Sequential Paired Defense Structure · pp. 4–5
C. Independent Local Game Score
- The independent local game score extends the local game score concept from LGRs to I-LGRs.When q̂k = 1, boundary defenders must perform a pincer maneuver; otherwise an intruder can enter Rk C and guarantee a score.Source: C. Independent Local Game Score · p. 5
A. The LGR Defense Algorithm
The LGR defense algorithm repeatedly updates assignments that determine defenders’ directions of motion. It removes uncapturable intruders once, then assigns cooperative 2v1 and individual 1v1 defenses, including implicit assignments.
A. The LGR Defense Algorithm
- The LGR strategy continuously updates defender–intruder assignments, which determine defenders’ directions of motion and can change as the game evolves.The full loop removes uncapturable intruders, assigns 2v1 defense, then assigns 1v1 defense.Source: A. The LGR Defense Algorithm · p. 5
- Algorithm 2 removes intruders that cannot be captured and is run only once at the beginning of the game.The removal creates a virtual game with QLG = 0 so the remaining intruders can be captured.Source: A. The LGR Defense Algorithm · p. 5
- After removing uncapturable intruders, the paper restricts the algorithm to cases where q̂k ≤ 1 for every k.Algorithm 3 assigns cooperative 2v1 games in this setting.Source: A. The LGR Defense Algorithm · p. 5
- Algorithm 3 processes I-LGRs with q̂ = 1 from largest to smallest subteam, assigning a paired-defense intruder even when defenders already have other 2v1 assignments.The procedure can generate sequential paired defense; its loop terminates when all I-LGRs have q̂ ≤ 0, in fewer than NA iterations.Source: A. The LGR Defense Algorithm · p. 5
- Algorithm 4 uses maximum matching for the remaining 1v1 assignments while accounting for eligible implicit assignments.Implicit assignment is restricted to an additional intruder in the outermost defender pair’s zone; maximum matching runs in O((NA + ND)^w) time with w < 2.5.Source: A. The LGR Defense Algorithm · p. 6
B. Performance Guarantees
Under the stated initial conditions, the LGR defense guarantees zero overall score. The proof shows that assignments and score conditions evolve so every intruder receives a defense assignment before reaching the perimeter.
B. Performance Guarantees
- Under the same conditions, every intruder has a 1v1, 2v1, or implicit assignment..Source: B. Performance Guarantees · p. 6
- The maximum matching in Algorithm 4 covers all intruders left without 2v1 assignments.The proof establishes Hall’s condition for every subset of those intruders.Source: B. Performance Guarantees · p. 6
- If QLG(z) = 0 and q̂k(z) ≤ 1 for every k, Algorithm 3 generates a sequential paired-defense structure with no conflict, as defined in Definition 3.Source: B. Performance Guarantees · p. 6
- Starting from the stated initial conditions, the number of 2v1 assignments decreases over time while QLG = 0 and q̂k ≤ 1 remain preserved.Each transition reduces an intruder’s I-LGS from 1 to 0 without increasing any new I-LGR score.Source: B. Performance Guarantees · p. 6
- If initially QLG(z0) = 0 and q̂k(z0) ≤ 1 for every k, the LGR defense guarantees an overall score of zero.The theorem’s proof uses preservation of these conditions and eventual 1v1 assignment before an intruder reaches the perimeter.Source: B. Performance Guarantees · pp. 6–7
C. Saddle-point equilibrium
After removing QLG(z0) intruders, if each remaining ˆqk(z0) ≤ 1, the section establishes a saddle-point equilibrium with game value Q*(z0) = QLG(z0).
C. Saddle-point equilibrium
- When QLG(z0) > 0, a set of exactly QLG(z0) intruders can be removed to produce a new game with QLG = 0.The proof repeatedly removes an intruder whose removal reduces QLG by one.Source: C. Saddle-point equilibrium · p. 7
- Algorithm 2 tests each intruder once for whether its removal reduces QLG, terminating in fewer than NA iterations.The stated iteration count follows because the answer to each test remains the same as QLG is reduced.Source: C. Saddle-point equilibrium · p. 7
- If each remaining ˆqk(z0) ≤ 1 after removing QLG(z0) intruders, the strategies form a saddle-point equilibrium and Q*(z0) = QLG(z0).Neither team can improve the score by changing its strategy while the other keeps its equilibrium strategy.Source: C. Saddle-point equilibrium · p. 7
VII. SIMULATION RESULTS
The simulations show that LGR can improve capture guarantees through sequential cooperative defense, while its statistical advantage over MM varies with initial distance. The conclusion attributes its polynomial-time performance to decomposition into local games and identifies extensions for future work.
A. Illustrative Example
- In the six-versus-five example, LGR captures both A1 and A2 through sequential 2v1 defenses, whereas MM assigns defenses that yield QMM = 1.The sequence uses D2 first with D3 and then with D1, without explicit look-ahead planning.Source: A. Illustrative Example · p. 7
B. Statistical results
- At an initial distance of 0.1 units, QMM − QLG can reach ≈15 while QLG ≈20 ± 7 when intruders choose their formation, showing a substantial LGR advantage.Figure 8 compares score upper bounds as initial distance varies; the reported values describe the formation-sensitive gap at 0.1 units.Source: Figure 8 · p. 8, B. Statistical results · p. 8
- As initial intruder distance increases, score upper bounds decrease toward zero, while the QMM − QLG gap grows with 2v1 opportunities and later shrinks.The gap is small at short distances, increases where cooperative defenses are more useful, and falls at larger distances where MM performs near optimally.Source: B. Statistical results · p. 8
VIII. CONCLUSION
- LGR is a polynomial-time cooperative defense policy that outperforms existing assignment-based policies; its local-game decomposition lowers complexity relative to maximum-independent-set formulations.The cooperative behavior pairs defenders to pursue an intruder from both sides.Source: §VIII · p. 8
- Future work includes extending the approach to three dimensions, obstacle environments, relaxed information structures, and heterogeneous teams.The relaxed-information examples include local sensing and communication.Source: §VIII · p. 8
APPENDIX
The appendix proves that the paired-defense structure simplifies over time and that removing selected intruders can reduce QLG to zero.
A. Proof of Lemma 5
- During play, transitions preserve QLG = 0 while the number of 2v1 assignments monotonically decreases.The argument relies on non-conflicting 2v1 assignments and shows that each transition reduces the number of such assignments.Source: A. Proof of Lemma 5 · p. 9
B. Proof of Lemma 6
- When QLG > 0, a contradiction argument establishes that some intruder's removal lowers QLG by one; repeating removals reaches zero regardless of order.The proof compares disjoint optimal sets and uses their optimality to derive a contradiction if no such intruder exists.Source: B. Proof of Lemma 6 · p. 9
C. Computation Time
The computation-time results support LGR's scalability: its assignment growth is empirically sub-quadratic, while MIS search is super-polynomial and sometimes fails to complete at larger sizes. The policy divides its work between one-time removal and assignments run throughout the game.
C. Computation Time
- The computation-time comparison varies NA and tests 100 configurations at each value, with ND = NA + 1.The initial intruder distance is set to half the defender spacing.Source: C. Computation Time · p. 9
- LGR assignment computation grows empirically sub-quadratically, while MIS search is super-polynomial and some cases with NA ≥ 30 could not be completed.The results support the authors' claim that LGR outperforms MM and MIS while maintaining polynomial-time scalability.Source: Figure 9 · p. 9, C. Computation Time · p. 10
- LGR separates one-time uncapturable-intruder removal from continuously run assignments; the removal computation follows the ∼N_A^5 empirical trend.The plotted removal results are reported to validate the theoretical bound.Source: C. Computation Time · pp. 9–10