Overlapping Coalition Formation for Resource Allocation in Post-Disaster Rescue UAV Swarms

Unmanned aerial vehicle (UAV) swarms, equipped for distributed sensing and rapid response, can form coalitions to undertake complex missions such as post-disaster relief, communication support, and payload delivery. However, typical coalition formation methods assign each UAV to a single task, limiting cross-task resource sharing. To address this, we investigate overlapping coalition formation (OCF) for UAV swarms, where a single UAV is permitted to participate in multiple coalitions, enabling resource reuse and reducing idleness. We formulate OCF as a multi-objective combinatorial optimization problem that jointly balances task fulfillment ratio, coalition synchronization deviation, and operational cost, while explicitly accounting for inter-coalition resource contention and execution precedence. Specifically, we first construct a hypergraph representation of UAVs and tasks and employ a hypergraph attention network to capture their high-order interactions. Next, we propose a structure-aware hierarchical value decomposition method for policy learning, which progressively aggregates individual- and coalition-level information, models member complementarity and inter-coalition cooperative–competitive relations, and generates a global value estimate that is sensitive to changes in coalition structure. Furthermore, we integrate Monte Carlo Tree Search, utilizing the learned value as a heuristic to efficiently explore the feasible region, and close the loop with candidate-structure demonstration replay and policy distillation, enabling search to refine the learned policy. In multi-scale rescue simulations, the proposed approach improves task utility by up to 11.4% over the best-performing baseline and increases energy efficiency by more than 228% compared to a non-overlapping coalition variant.