Multiplayer Reach-Avoid Games via Pairwise Outcomes

By Mo Chen, Zhengyuan Zhou, Claire Jennifer Tomlin. 2016

172 citations recorded by the source corpus.

A multiplayer reach-avoid game is a differential game between an attacking team with <inline-formula> <tex-math notation="LaTeX">$N_{A}$</tex-math></inline-formula> attackers and a defending team with <inline-formula> <tex-math notation="LaTeX">$N_{D}$</tex-math></inline-formula> defenders playing on a compact domain with obstacles. The attacking team aims to send <inline-formula> <tex-math notation="LaTeX">$M$</tex-math></inline-formula> of the <inline-formula> <tex-math notation="LaTeX">$N_{A}$</tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">$N_{A} > 1$</tex-math></inline-formula> or <inline-formula> <tex-math notation="LaTeX">$N_{D} > 1$</tex-math></inline-formula>. In this technical note, we present two approaches for the <inline-formula> <tex-math notation="LaTeX">$N_{A}=N_{D}=1$</tex-math></inline-formula> case to determine pairwise outcomes, and a graph theoretic maximum matching approach to merge these pairwise outcomes for an <inline-formula> <tex-math notation="LaTeX">$N_{A},N_{D} > 1$</tex-math></inline-formula> 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.

Subfields: Aerospace Engineering, Civil and Structural Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

Citations in the corpus

Hamilton-Jacobi reachability: A brief overview and recent advances (2017, background): “As a result, an upper bound on the number of attackers that can reach the target set can be obtained [67].”
Learning Policy Representations in Multiagent Systems (2018, background): “Graphs are a fundamental abstraction for modeling relational data, such as the interactions arising in multiagent systems (Zhou et al., 2016a;b; Chen et al., 2017; Battaglia et al., 2016; Hoshen, 2017) and concurrent work proposes to learn such graphs directly from data (Kipf et al., 2018).”