Source-linked AI summary
Multiplayer Reach-Avoid Games via Pairwise Outcomes
Mo Chen, Zhengyuan Zhou, Claire J. Tomlin
TL;DR
Multiplayer reach-avoid games are difficult to solve directly because their joint-state HJI formulation becomes computationally intractable with multiple players. The paper combines pairwise HJI or path-defense outcomes through maximum matching, yielding defender guarantees while trading computational cost against scalability. The HJI method supports real-time matching updates, whereas path defense scales linearly with the number of attackers.
Problem
Direct analysis of multiplayer reach-avoid games is computationally intractable when multiple attackers or defenders interact in a high-dimensional joint state space.
Method
The paper solves pairwise games with HJI or path defense, then merges pairwise outcomes using graph-theoretic maximum matching.
Results
The HJI approach enables real-time maximum-matching updates, while path defense scales linearly with the number of attackers and retains defender performance guarantees.
Takeaways & Limitations
Pairwise outcomes can approximate the multiplayer game while guaranteeing an upper bound on the number of attackers that reach the target.
Abstract
from arXiv · showhide
A multiplayer reach-avoid game is a differential game between an attacking team with NA attackers and a defending team with ND defenders playing on a compact domain with obstacles. The attacking team aims to send M of the NA attackers to some target location, while the defending team aims to prevent that by capturing attackers or indefinitely delaying attackers from reaching the target. Although the analysis of this game plays an important role in many applications, the optimal solution to this game is computationally intractable when NA>1 or ND>1. In this paper, we present two approaches for the NA=ND=1 case to determine pairwise outcomes, and a graph theoretic maximum matching approach to merge these pairwise outcomes for an NA,ND>1 solution that provides guarantees on the performance of the defending team. We will show that the four-dimensional Hamilton-Jacobi-Isaacs approach allows for real-time updates to the maximum matching, and that the two-dimensional "path defense" approach is considerably more scalable with the number of players while maintaining defender performance guarantees.
I. INTRODUCTION
Multiplayer reach-avoid games model adversarial teams navigating obstacle-filled domains, but their high-dimensional joint-state analysis is computationally difficult. The paper combines pairwise game solutions with maximum matching to analyze larger teams and provide defender guarantees.
- Computational challenge: 21?
- Computational challenge: Traditional dynamic programming becomes infeasible because the joint state space is intrinsically high-dimensional.
- Proposed approach: The paper analyzes pairwise attacker-defender outcomes using HJI and path-defense approaches before combining them for multiplayer games.The two-player construction is the building block for the multiplayer analysis.
- Proposed approach: Maximum matching merges pairwise outcomes while incorporating defender cooperation without significant additional computation cost.When dynamics are identical within teams, one HJI PDE characterizes all pairwise outcomes.
- Game formulation: Attackers seek to send M team members to a target, while defenders capture or indefinitely delay enough attackers to prevent this.The defending team wins by preventing the attackers from meeting the specified reach condition.
B. The Two-Player Reach-Avoid Game
The two-player game asks whether a defender can prevent one attacker from reaching the target and characterizes the defender-winning initial positions. This pairwise problem supplies the building block for the multiplayer analysis.
- Game definition: The two-player game treats one attacker and one defender, with their joint state and initial condition defining the game.
- Winning conditions: The attacker wins by reaching the target without capture, while the defender wins by capturing or indefinitely delaying the attacker.
- Analysis objectives: The analysis asks whether the defender is guaranteed to win from a given initial state and which initial positions guarantee defender victory.
III. THE HJI SOLUTION OF THE 1 VS. 1 GAME
The HJI approach solves the two-player reach-avoid game in the joint state space, accounting for target, capture, and obstacle avoidance. It produces a 4D reach-avoid set that separates attacker-winning and defender-winning initial states.
- HJI formulation: A 4D HJI PDE computes optimal closed-loop controls and determines the winner in the two-player game.
- HJI formulation: The game defines target and avoid conditions so the attacker reaches T while avoiding capture and obstacles.
- HJI outcome: The 4D reach-avoid set guarantees attacker victory inside it and defender victory outside it when both players use optimal controls.
- Path defense: The path-defense approximation uses 2D slices of the 4D reach-avoid set at attacker positions and assumes the defender is not slower than the attacker.
- Path defense: A path of defense is the shortest path between boundary anchor points, separating the domain into attacker and target sides.
B. Solving The Path Defense Game
The path defense approach conservatively approximates the 4D reach-avoid solution with 2D distance calculations and provides conditions for strong defendability. Its key results characterize attacker regions, defender arrival points, and efficient computation under speed assumptions.
- Definitions: A path of defense is strongly defendable when the defender can reach it after finite time and prevent the attacker from reaching it.Strong defendability is defined regardless of the attacker’s actions.
- Defendability conditions: When vA = vD, a path is strongly defendable if and only if the attacker starts outside the regions induced by a path point and its anchor points.The relevant regions are Ra and Rb, and the condition is expressed using the defender’s position relative to the induced region.
- Defendability conditions: If the attacker starts outside Ra ∪Rb, it cannot cross any point on the defense path without being captured.The result follows from comparing attacker and defender travel distances to points on the path.
- Defendability conditions: For vA < vD, starting outside Ra ∪Rb is sufficient for strong defendability of the path.The strict speed advantage strengthens the sufficient condition beyond the equal-speed case.
- Efficient test: Strong defendability can be tested by checking one special first-arrival point p∗ rather than every possible entry point.The defender can defend the path if and only if it can first defend it by going to p∗.
- Efficient computation: The resulting algorithm computes p∗ and induced regions using 2D Eikonal equations solved with FMM, reducing the 4D problem to 2D calculations.This provides an efficient alternative to directly computing the 4D reach-avoid set.
C. The Path Defense Solution to the Reach-Avoid Game
The path defense approximation uses strongly defendable paths enclosing the target to construct a conservative defender-winning region with greater computational efficiency. In simply connected domains, checking only paths that touch the target introduces no additional conservatism.
- Path defense: Strongly defendable paths enclosing the target let the defender win using a semi-open-loop strategy, even against optimal attacker control.The strategy combines an initial open-loop move with subsequent closed-loop tracking.
- Path selection: Checking only defense paths that touch the target reduces the number of paths examined.
- Path selection: In a simply connected domain, restricting checks to paths touching the target adds no conservatism.
- Approximation algorithm: The path-defense algorithm unions defender-winning regions from selected paths to form a conservative two-dimensional slice.
A. Maximum Matching
Maximum matching merges pairwise attacker-defender outcomes into a conservative multiplayer reach-avoid approximation. A matching of size m guarantees that defenders can prevent at least m attackers from reaching the target.
- Graph construction: The method constructs a bipartite graph whose nodes represent defenders and attackers, with edges for defender-winning pairwise outcomes.
- Matching: A maximum matching assigns defenders to attackers they can defeat in the corresponding two-player games.
- Guarantee: If the maximum matching has size m, defenders can prevent at least m attackers from reaching the target, so NA −m is an upper bound on attackers reaching it.
B. Time-Varying Defender-Attacker Pairings
The defender-attacker matching can be updated as players move by repeatedly recomputing pairwise outcomes, assigning a maximum matching, advancing matched defenders under winning controls, and updating positions.
- State update: The process repeats after updating player positions, allowing the matching to change during the game.
- Recomputation: At each update, pairwise winning outcomes are determined for every attacker-defender position pair before recomputing the matching.
- State update: Matched defenders follow winning control inputs for a short duration Δ, while other players are propagated under arbitrary control functions.
C. Application to the Two-Player HJI Solution
The HJI approach computes pairwise outcomes by solving 4D PDEs and supports real-time maximum-matching updates as player positions change. When team dynamics are identical, one 4D HJI PDE characterizes all pairwise outcomes.
- Pairwise computation: In general, computing all pairwise outcomes requires solving NA ND 4D HJI PDEs, where each PDE characterizes one attacker-defender pair.If each team has a single maximum speed, one 4D HJI PDE characterizes all pairwise outcomes.
- Real-time updates: The maximum matching can be updated in real time by checking whether each new attacker-defender joint state lies in the reach-avoid set.
D. Application to the Two-Player Path Defense Solution
The path defense approach combines pairwise defender outcomes through maximum matching to obtain a scalable multiplayer defense with performance guarantees. In the 4 vs. 4 example, it used far less computation than the HJI computation while producing a conservative result.
- Maximum matching: Maximum matching combines pairwise defender outcomes while incorporating cooperation among defenders.Each defender can use a specified strategy, including HJI or semi-open-loop path defense, and the resulting outcomes define the matching graph.
- Computational performance: The HJI reach-avoid set required approximately 30 minutes on a grid with 45 points in each dimension.Because all players had the same maximum speed, only one 4D HJI PDE was solved.
- HJI result: A maximum matching of size 4 guaranteed that no attacker could reach the target under optimal pairwise HJI strategies.The 4 vs. 4 example used a square domain with obstacles, equal player speeds, and a 0.1-unit defender capture radius.
- Path defense result: A maximum matching of size 3 guaranteed that at most 1 attacker could reach the target under the semi-open-loop strategy.The example used the path defense pairwise outcomes rather than the optimal closed-loop HJI outcomes.
- Computational performance: 937 paths required approximately 60 seconds for path computation and 30 seconds for computing the resulting 2D slice.Using 30 paths still covered more than 95% of the area obtained with 937 paths, reducing the times to 2.5 and 2.1 seconds.
C. Defender Cooperation
Maximum matching coordinates defenders using pairwise competence, and HJI-based pairwise outcomes can be updated as the game evolves. The path defense alternative is more scalable but conservative toward the defender.
- Defender cooperation: The HJI and path defense matchings can pair defenders with attackers in ways that are not intuitively obvious from individual pairings.The example shows that choosing an apparently reasonable pairing can leave another defender without a guaranteed winning assignment.
- Real-time updates: HJI pairwise outcomes support real-time maximum-matching updates as the players move through the game.In the 4 vs. 4 example, the matching was updated every Δ=0.005 seconds.
- Real-time updates: The matching size increased from 3 to 4 after t = 0.4, changing the guarantee from at most 1 attacker reaching the target to none.At t = 0 and t = 0.2, the matching size was 3.
- Scalability trade-off: The path defense approach scales linearly in the number of attackers but is conservative toward the defender.It computes on the state space of a single player rather than the joint state space.