Coalition formation game-based distributed optimization for heterogeneous UAV swarm fire strike task allocation

Abstract

The weapon-target assignment (WTA) problem in heterogeneous unmanned aerial vehicle (UAV) swarm fire strikes faces severe bottlenecks: exponential computational complexity, single-point vulnerability in centralized architectures, and prohibitive global recomputation costs in dynamic environments. This paper proposes a distributed optimization framework based on coalition formation game theory, termed the Distributed Coalition Formation Algorithm (DCFA). The centralized WTA is transformed into a coalition partition game where UAVs act as rational decision-makers autonomously evaluating marginal contributions. We rigorously prove that the global utility function constitutes an exact potential function, guaranteeing finite-step convergence to Nash-stable structures with zero efficiency loss (Price of Stability = 1). The coalition utility embeds comprehensive fire-strike constraints, utilizing a modified sigmoid function to map synergistic kill probabilities to strike benefits. Algorithmically, a Simulated Annealing Better-Response (SABR) mechanism is designed to escape local optima, coupled with localized dynamic reallocation strategies for battlefield events. Extensive Monte Carlo simulations and rigorous statistical tests demonstrate that DCFA achieves near-linear scalability. Compared to centralized metaheuristics, DCFA secures the optimal position on the utility-time Pareto frontier, delivering over an order-of-magnitude speedup with marginal accuracy trade-offs, and enables millisecond-level dynamic recovery, providing a robust distributed solution for large-scale swarm operations.