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

DOI10.1016/J.AUTOMATICA.2022.110207zbMATH Open1486.91013arXiv1909.11881OpenAlexW3005581757MaRDI QIDQ2125490FDOQ2125490

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

Publication date: 14 April 2022

Published in: Automatica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (9)

• Real-time game-theoretic model predictive control for differential game of target defense
• Multiplayer homicidal chauffeur reach-avoid games: a pursuit enclosure function approach
• 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
• A review of multi agent perimeter defense games
• Time-optimal surveillance between two differential drive robots with a limited field of view
• Optimal strategy analysis for adversarial differential games
• Cooperative strategies for two-evader-one-pursuer reach-avoid differential games

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)