TRD-OCFG: A Multi-UAV Overlapping Coalition Formation Game Oriented to Temporal and Resource Deadlock Constraints

With the continuous expansion of the scope of unmanned aerial vehicle (UAV) swarm operations, the specificity and complexity of task requirements have become increasingly prominent. Meanwhile, growing coupling constraints between heterogeneous resources and tasks pose a significant challenge to the computational efficiency and adaptability of multi-UAV collaborative task planning systems. This study addresses the planning problem of heterogeneous UAVs with limited resources in search and rescue (SAR) scenarios, and establishes a system model incorporating temporal and resource deadlock constraints. The model characterizes an NP-hard problem of multi-layer coupled planning that integrates resource allocation and task scheduling. To solve this problem, this article proposes a temporal and resource deadlock constraints-oriented overlapping coalition formation game (TRD-OCFG) algorithm based on game theory, which combines asynchronous leaderless communication and iterative mechanisms to reduce computational complexity. The proposed algorithm swiftly finds coalition structures and task sequences satisfying Nash equilibrium by utilizing coalition construction and degeneration strategies. The directed cycle filtering strategy is used in distributed scheduling to resolve temporal deadlock conflicts. Additionally, in resource deadlock situations, coalition structure transfer is enabled by the resource deadlock reorganization strategy. Simulation results demonstrate that the proposed algorithm can maximize the increase in coalition utility and the task completion rate. Furthermore, it proves its generality in variable-scale search and rescue scenarios and offers notable improvements in stability, optimization performance, and convergence performance when compared to state-of-the-art OCFG methods.