Adaptive Team Formation for Collaborative Perimeter Defense

This work addresses the Perimeter Defense Problem with probabilistic captures, where intruders approach a protected perimeter and a team of defenders must intercept them. By treating arriving intruders as dynamic demands, we unify the Dynamic Vehicle Routing Problem and the Weapon-Target Assignment Problem into a single network-flow formulation that jointly optimizes assignment, routing, and adaptive team formation. For homogeneous defenders, we solve a Min-Cost Max-Flow instance; a 2^k factorial experiment shows collaboration explains 54% of performance variance versus only 10% for defender speed, with a coverage trade-off. For heterogeneous defenders (varying velocities), we formulate an NP-hard Unsplittable Flow Problem and develop a successive shortest‑path heuristic. Experiments demonstrate that heterogeneous teams outperform homogeneous ones with equivalent average speed. The heuristic achieves near‑optimal performance (<= 1.5% gap) while drastically reducing computation time. Results validate network flow models and efficient heuristics for dynamic, collaborative perimeter defense under probabilistic capture constraints. Illustrative video: https://youtu.be/eB6NXVCknxk.