Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games

DOI10.1016/J.AUTOMATICA.2022.110207MaRDI QIDQ2125490zbMATH OpenOpenAlexFDO

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

Publication date 14 April 2022

Published in Automatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.11881

zbMATH Keywords

differential gamesmulti-agent systemscooperative strategiesconstrained matchingreach-avoid games

Mathematics Subject Classification ID

Pursuit and evasion games (49N75) Positional games (pursuit and evasion, etc.) (91A24) Multi-agent systems (93A16)

Abstract: 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.

Recommendations

• Cooperative strategies for two-evader-one-pursuer reach-avoid differential games
• Multiplayer pursuit-evasion games in three-dimensional flow fields
• Two pursuers and one evader in the plane: A stochastic pursuit-evasion differential game
• scientific article; zbMATH DE number 4083417
• Linear non-stationary differential pursuit games with several evaders

Cites work

• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 1243371 (Why is no real title available?)
• scientific article; zbMATH DE number 3245077 (Why is no real title available?)
• scientific article; zbMATH DE number 3363374 (Why is no real title available?)
• A Differential Game Approach to Multi-agent Collision Avoidance
• A Differential Game with Two Players and One Target
• A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games
• Approximation of knapsack problems with conflict and forcing graphs
• Decomposition of Reachable Sets and Tubes for a Class of Nonlinear Systems
• Design and Analysis of State-Feedback Optimal Strategies for the Differential Game of Active Defense
• Hamilton–Jacobi Formulation for Reach–Avoid Differential Games
• Markov Chains With Maximum Return Time Entropy for Robotic Surveillance
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Multiplayer Reach-Avoid Games via Pairwise Outcomes
• Multiplayer pursuit-evasion games in three-dimensional flow fields
• Nonsmooth semipermeable Barriers, Isaacs' equation, and application to a differential game with one target and two players
• On guaranteeing point capture in linear \(n\)-on-1 endgame interception engagements with bounded controls
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Paths, trees and matchings under disjunctive constraints
• Pursuit-evasion games in the presence of obstacles
• Reach-avoid problems with time-varying dynamics, targets and constraints
• Reducibility among combinatorial problems
• Role determination in an aerial dogfight
• Some Matching Problems for Bipartite Graphs
• The existence of value in differential games
• The geometry of the barrier in the ‘game of two cars’
• The minimum cost perfect matching problem with conflict pair constraints
• The minimum spanning tree problem with conflict constraints and its variations
• Two-target pursuit-evasion differential games in the plane
• Vehicle Routing Algorithms for Radially Escaping Targets

Cited in

(9)

• Cooperative strategies for two-evader-one-pursuer reach-avoid differential games
• A review of multi agent perimeter defense games
• Time-optimal surveillance between two differential drive robots with a limited field of view
• Real-time game-theoretic model predictive control for differential game of target defense
• Multiplayer homicidal chauffeur reach-avoid games: a pursuit enclosure function approach
• Optimal strategy analysis for adversarial differential games
• Multiplayer pursuit-evasion games in three-dimensional flow fields
• Reach-avoid games with two heterogeneous defenders and one attacker
• Surveillance evasion between two identical differential drive robots

This page was built for publication: Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2125490)