  This paper studies a variant of the multi-player reach-avoid game played
between intruders and defenders with applications to perimeter defense. The
intruder team tries to score by sending as many intruders as possible to the
target area, while the defender team tries to minimize this score by
intercepting them. Finding the optimal strategies of the game is challenging
due to the high dimensionality of the joint state space, and the existing works
have proposed approximation methods to reduce the design of the defense
strategy into assignment problems. However they suffer from either suboptimal
defender performance or computational complexity. Based on a novel
decomposition method, this paper proposes a scalable (polynomial-time)
assignment algorithm that accommodates cooperative behaviors and outperforms
the existing defense strategies. For a certain class of initial configurations,
we derive the exact score by showing that the lower bound provided by the
intruder team matches the upper bound provided by the defender team, which also
proves the optimality of the team strategies.
