PaperlayerView exact revision on arXiv

Source-linked AI summary

Matching-Based Capture Strategies for 3D Heterogeneous Multiplayer Reach-Avoid Differential Games

Rui Yan, Xiaoming Duan, Zongying Shi, Yisheng Zhong, Francesco Bullo

arXiv:1909.11881v2math.OC

TL;DR

The paper addresses heterogeneous 3D reach-avoid games that are difficult to analyze directly and for which existing methods do not fully address heterogeneous capture radii. It combines a single-evader evasion-space strategy with conflict-constrained matching and receding-horizon pursuit. It establishes a three-pursuer bound for successful defense and gives a polynomial-time constant-factor approximation for the matching problem.

  • Problem

    Heterogeneous capture radii remain insufficiently addressed in multiplayer reach-avoid games, which are hard to solve directly because of their high dimension and multiple stages.

    Source: §1 · pp. 1–2

  • Method

    The paper develops a potential-function Evasion Space strategy for one evader and uses maximum bipartite matching with conflict graph in a receding-horizon capture strategy.

    Source: §1 · p. 2, §7 · p. 15

  • Results

    At most three pursuers are necessarily needed when a coalition can defend the goal against one evader, and MBMC has a polynomial-time constant-factor approximation algorithm.

    Source: §3.3 · p. 8, §7 · p. 15

  • Takeaways & Limitations

    The approach also extends to bounded convex play regions by slightly modifying the interception point.

    Source: §7 · p. 15

    The model assumes players can change their orientations instantaneously.

    Source: §2.1 · p. 3

Abstract

from arXiv · show

This paper studies a 3D multiplayer reach-avoid differential game with a goal region and a play region. Multiple pursuers defend the goal region by consecutively capturing multiple evaders in the play region. The players have heterogeneous moving speeds and the pursuers have heterogeneous capture radii. Since this game is hard to analyze directly, we decompose the whole game as many subgames which involve multiple pursuers and only one evader. Then, these subgames are used as a building block for the pursuer-evader matching. First, for multiple pursuers and one evader, we introduce an evasion space (ES) method characterized by a potential function to construct a guaranteed pursuer winning strategy. Then, based on this strategy, we develop conditions to determine whether a pursuit team can guard the goal region against one evader. It is shown that in 3D, if a pursuit team is able to defend the goal region against an evader, then at most three pursuers in the team are necessarily needed. We also compute the value function of the Hamilton-Jacobi-Isaacs (HJI) equation for a special subgame of degree. To capture the maximum number of evaders in the open-loop sense, we formulate a maximum bipartite matching problem with conflict graph (MBMC). We show that the MBMC is NP-hard and design a polynomial-time constant-factor approximation algorithm to solve it. Finally, we propose a receding horizon strategy for the pursuit team where in each horizon an MBMC is solved and the strategies of the pursuers are given. We also extend our results to the case of a bounded convex play region where the evaders escape through an exit. Two numerical examples are provided to demonstrate the obtained results.

1 Introduction

The paper addresses heterogeneous 3D reach-avoid games, where existing approaches do not fully handle differing capture radii, close cooperation, and unknown evader strategies. It develops single-evader pursuit methods and a conflict-constrained matching strategy for multiple evaders.

1 Introduction

  • The paper targets heterogeneous multiplayer games with heterogeneous capture radii and cooperative pursuers, settings existing methods cannot directly handle.The authors identify a need for analytical and efficient methods for heterogeneous capture radii.Source: §1 · p. 2
  • The formulation covers players with different speeds and pursuers with different capture radii, and extends to bounded convex play regions with planar exits.The paper presents a receding-horizon strategy to capture a good number of evaders.Source: §1 · p. 2
  • The Evasion Space method uses a potential function to construct a guaranteed pursuer winning strategy against one evader.The paper considers all possible pursuer coalitions in this case.Source: §1 · p. 3
  • In 3D, a coalition able to defend the goal region against one evader necessarily needs at most three pursuers.The paper also solves an associated special subgame of degree using a convex program for its HJI equation.Source: §1 · p. 3
  • The paper formulates open-loop assignment as maximum bipartite matching with conflict graph and proves this problem NP-hard.The reduction is from 3-dimensional matching.Source: §1 · p. 3
  • The Sequential Matching Algorithm is a polynomial-time constant-factor approximation, and its matching underpins a receding-horizon capture strategy.The algorithm is also shown to be APX-complete.Source: §1 · p. 3

2 Problem Description

The game models heterogeneous pursuers and evaders competing across a separating plane, with capture before goal entry as the pursuers’ objective. Its setup specifies player motion and information, while a geometric lemma addresses strict convexity.

2.1 Multiplayer Reach-Avoid Differential Games

  • Players are holonomic mass points in 3D, with the play and goal regions separated by the plane z = 0.Pursuers may start anywhere, while evaders initially lie in the play region.Source: §2.1 · p. 3, §2.2 · p. 4
  • Each player chooses an instantaneous heading on the unit sphere, and players may have different speeds while pursuers have capture radii.Capture occurs when an evader reaches the corresponding capture radius of at least one pursuer.Source: §2.1 · p. 3

2.2 Information Structure and Assumptions

  • The information structure gives each player current positions as the basis for choosing its current input.Initial deployment excludes coincident players and initially captured evaders; the paper focuses on pursuers faster than every evader.Source: §2.2 · pp. 3–4

2.3 A Useful Lemma

  • A polar-coordinate lemma gives a condition under which a twice-differentiable simple closed curve and its interior are strictly convex.The supplied passage does not state the condition itself.Source: §2.3 · p. 4

3 Multiple Pursuers Versus One Evader

This section studies multiple-pursuer, single-evader subgames as building blocks for the multiplayer game, developing evasion-space methods to determine when and how pursuers can win. It also establishes a three-pursuer bound and formulates the HJI value-function computation for a special subgame as a convex optimization problem that yields the players’ strategies.

3.1 Problem statement

  • The whole game is decomposed into multiple-pursuer, single-evader subgames that serve as building blocks for the later pursuer–evader matching.The problem statement asks how to determine the winner for a coalition and evader, and how many pursuers are needed to guarantee a win.Source: §3.1 · p. 4

3.2 Evasion Space

  • Each single-pursuer evasion-space closure is bounded and strictly convex; a coalition’s evasion-space closure is also bounded and strictly convex.The coalition evasion space is the intersection of its members’ individual evasion spaces.Source: §3.2 · pp. 5–6

3.3 Guaranteed Pursuer Winning Strategies

  • At most three pursuers suffice to locate the interception point, and a coalition winning with the goal outside its evasion space can use feedback strategies directed toward that point.The selected subcoalition has at most three members; its strategy keeps the evasion-space closure from approaching the goal for any evader control input.Source: §3.3 · pp. 7–8

3.4 The Hamilton-Jacobi-Isaacs Equation

  • For states where the value function is differentiable, the special winning subgame’s value function can be computed by convex optimization.The result applies when the coalition’s evasion-space closure does not intersect the goal.Source: §3.4 · p. 9
  • For differentiable states, the value function obtained from the convex optimization satisfies the HJI equation.Source: §3.4 · p. 9
  • At game termination, capture at a pursuer’s radius makes the evader position the unique feasible solution, so the value function meets the terminal condition.Source: §3.4 · p. 9
  • The special subgame’s HJI equation can be transformed into a convex optimization problem with reduced computational complexity, and the players’ strategies follow from the value-function gradients obtained through its solution.Source: §3.4 · p. 10

4 Maximum-Matching Capture Strategies

The paper models pursuit-coalition assignments as a conflict-constrained bipartite matching and proves the resulting problem is hard, then provides approximation and receding-horizon strategies. The receding-horizon strategy updates assignments as play evolves while preserving matching size until a capture, when pursuers use their coalition’s ES-based strategy.

4.1 Maximum Matching

  • The bipartite graph assigns evaders to pursuit coalitions of up to three pursuers, with an edge when a coalition can capture an evader and no smaller subcoalition can.Coalitions sharing a pursuer conflict because each pursuer can belong to at most one assignment.Source: §4.1 · p. 10
  • A conflict graph represents incompatible assignments: its vertices correspond to bipartite-graph edges, and its edges mark pairs that cannot coexist in a matching.The constraint ensures a pursuer is not assigned to multiple coalitions.Source: §4.1 · p. 10, Figure 5 · p. 10
  • MBMC is NP-hard, by a polynomial reduction from 3-dimensional matching.The reduction makes a complete matching equivalent to a 3-dimensional matching.Source: §4.1 · p. 11
  • The Sequential Matching Algorithm solves successive maximum-flow matchings for coalitions of size one, then at most two, then remaining coalitions of up to three pursuers.After each stage, it removes used pursuers and evaders before constructing the next subgraph.Source: §4.1 · pp. 11–12
  • The Sequential Matching Algorithm runs in polynomial time, gives a 1/3-approximation generally and a 1/2-approximation without three-pursuer coalitions, and is exact when solutions use only one-pursuer coalitions.MBMC is also APX-complete.Source: §4.1 · p. 12

4.2 Receding Horizon Strategy

  • The receding-horizon strategy recomputes an approximate matching as positions change and retains its size until an evader is captured, using the matched coalition’s ES-based strategy.A better matching may emerge during play; the strategy avoids changing the current matching unless more evaders can be captured.Source: §4.2 · p. 12

5 Bounded Convex Play Region with An Exit

The extension considers a bounded convex 3D play region with a planar exit, where pursuers aim to capture evaders before they escape. It defines an interception point and extends the evasion-space strategy under conditions that determine which team wins.

5 Bounded Convex Play Region with An Exit

  • In a bounded convex play region with a planar exit, pursuers aim to capture evaders before they leave the region.The play region is a closed convex subset of R3, and the exit lies on its boundary.Source: §5 · p. 12
  • When the evasion space does not intersect the exit, the interception point is unique and is chosen as the closest point in the evasion space and play region to the exit plane.If the closest point to the plane lies outside the play region, the selected point is where the relevant sets first become tangent.Source: §5 · pp. 12–13
  • If the evasion space does not intersect the exit, pursuers moving toward the interception point keep it from approaching the exit for any evader control.The result assumes every pursuer in the coalition uses the specified interception-point feedback strategy.Source: §5 · p. 13
  • The pursuers win when the evasion space misses the exit, the evaders win when it intersects the exit more than once, and a unique intersection is a tie.At most three pursuers are needed to capture one evader before escape, so the matching results also apply.Source: §5 · p. 13

6 Numerical Results

The simulations illustrate the matching strategy in unbounded and bounded convex play regions. In both examples, some evaders are captured while one reaches the goal or escapes.

6 Numerical Results

  • The numerical studies illustrate the theoretical developments for unbounded and bounded convex play regions.The simulations were performed in Matlab R2017b on a laptop with a Core i7-8550U processor and 16 GB of memory.Source: §6 · p. 13

6.1 Unbounded Play Region

  • Eight of nine evaders are captured in the unbounded play region, while one reaches the goal.The pursuit team changes its matching after a larger matching occurs during play.Source: §6.1 · p. 14, Figure 7 · p. 14

6.2 Bounded Convex Play Region

  • Six of seven evaders are captured in the bounded convex play region, while one escapes.Initially, four evaders are matched by six pursuers.Source: §6.2 · p. 14, Figure 8 · p. 14

7 Conclusion

The paper develops strategies for 3D multiplayer reach-avoid games, including a convex-program approach to interception and a matching-based capture strategy. It establishes a three-pursuer bound for defending against one evader and a polynomial-time constant-factor approximation for MBMC.

7 Conclusion

  • For a pursuit coalition and one evader, the evasion space is strictly convex and its unique interception point can be computed by a convex program.The coalition can defend the goal region by moving toward that point when the initial condition allows.Source: §7 · p. 14
  • In 3D, a coalition that can defend the goal region against an evader needs at most three pursuers.The paper also solves the HJI equation for a special subgame of degree by a convex program.Source: §7 · p. 15
  • The matching between pursuit coalitions and evaders is an instance of MBMC, for which the paper designs a polynomial-time constant-factor approximation algorithm.The paper analyzes MBMC's complexity and reports that it is NP-hard.Source: §7 · p. 15
  • The results extend to a bounded convex play region by slightly modifying the interception point.Source: §7 · p. 15

A Proof of Lemma 7

The proof establishes strict convexity of the evasion-space boundary from its curvature, then uses that boundary property to establish convexity of the set it encloses.

A Proof of Lemma 7

  • When condition (2) holds, the boundary curve has positive curvature for every ψ in [0, 2π] and is strictly convex.The proof uses the fact that positive curvature makes the curve convex and rules out line segments.Source: A Proof of Lemma 7 · p. 15
  • The curve and its interior form a convex set because the closed set has nonempty interior and a supporting hyperplane at each boundary point.Source: A Proof of Lemma 7 · p. 15
  • The enclosed set is strictly convex because its boundary curve is strictly convex.Source: A Proof of Lemma 7 · p. 15

B Proof of Theorem 4.2

The proof bounds an optimal MBMC matching using the sequential matching construction. It shows that the construction respects conflicts and runs in polynomial time.

B Proof of Theorem 4.2

Loading 1909.11881v2…