A Two-Level Clustered Consensus-Based Bundle Algorithm for Dynamic Heterogeneous Multi-UAV Multi-Task Allocation

In multi-UAV cooperative tasks, dynamic communication topologies and resource heterogeneity present significant challenges for distributed task allocation, leading to high communication overhead and poor task-resource matching, which in turn increases computational costs. While the Consensus-Based Bundle Algorithm (CBBA) offers a robust decentralized framework, its scalability and adaptability in heterogeneous, large-scale scenarios are limited. To overcome these issues, this paper introduces a novel Two-Level Clustered CBBA (TLC-CBBA). In the first-layer clustering, UAVs are grouped based on communication topology using graph-theoretic centrality measures to rank node importance, followed by clustering based on shortest-path distances to minimize communication costs. In the second-layer clustering, a resource-balanced and distance-aware K-medoids algorithm is applied within each subgroup obtained from the first-layer clustering, taking into account UAV resource heterogeneity and spatial proximity. This method ensures spatial compactness among UAVs within each subgroup while achieving a more balanced distribution of total resources across clusters. Finally, after completing the two-level clustering, each subgroup executes CBBA for local task bundling and consensus, while the cluster centers coordinate inter-cluster communication to guarantee globally consistent and conflict-free task allocation. Simulations across diverse mission scenarios and UAV team sizes demonstrate that TLC-CBBA substantially outperforms CBBA and its variants (DMCHBA, G-CBBA, and Clustering-CBBA) in terms of communication efficiency, total task score, runtime, and significance analysis. The proposed TLC-CBBA demonstrates strong robustness and scalability for heterogeneous multi-UAV task allocation in dynamic environments.