Coordinated Defense Allocation in Reach-Avoid Scenarios With Efficient Online Optimization

In this paper, we study the multi-player reach-avoid games within general convex environments and present a two-layer online optimization strategy for defender robots. The defenders' common goal is to intercept as many attacker robots as possible without prior knowledge of their strategies. To balance between optimality and efficiency, our approach alternates between coordinating defender coalitions against individual attackers and allocating coalitions to attackers based on predicted single-attack coordination outcomes. We develop an online convex programming-based strategy for single-attack defense coordination, which not only allows adaptability to joint states but also identifies the maximal region of initial joint states that guarantees successful attack interception. Our defense allocation algorithm utilizes a hierarchical iterative method to approximate integer linear programs with a monotonicity constraint, reducing computational burden while ensuring enhanced defense performance over time. Extensive simulations conducted in 2D and 3D environments validate the efficacy of our approach in comparison with state-of-the-art approaches.