TY - JOUR
T1 - A computationally efficient and communication-aware hierarchical task allocation algorithm for large-scale heterogeneous UUV swarms
AU - Shen, Qingliang
AU - Li, Huiping
AU - Yang, Dawei
AU - Wang, Yu
AU - Meng, Chenjing
N1 - Publisher Copyright:
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2026.
PY - 2026/10
Y1 - 2026/10
N2 - Existing task allocation methods for multi-UUV systems often lack robustness under communication constraints, incur high computational costs, and scale poorly, hindering real-world underwater applications. Therefore, this paper addresses the challenge of large-scale task allocation for heterogeneous unmanned underwater vehicles (UUVs) operating in dynamic and uncertain environments with communication constraints. We propose a centralized distributed task allocation (CDTA) algorithm that combines the benefits of centralized and distributed approaches. The framework consists of two main phases: a centralized pre-allocation phase and a distributed allocation phase. In the centralized pre-allocation phase, an improved discrete genetic algorithm (IDGA) with adaptive crossover and mutation strategies is introduced to assign UUVs to task clusters from a global perspective. A balanced k-means (bk-means) clustering method is designed to partition tasks into balanced and non-overlapping sub-teams, ensuring an even distribution of tasks and facilitating efficient distributed allocation. In the distributed allocation phase, consensus-based bundle algorithm (CBBA) is applied within each cluster to perform fine-grained task allocation. This hierarchical decomposition achieves high task allocation success rates and competitive marginal utility even in extremely poor communication environments, while relatively reducing communication and computational complexity. To further enhance computational efficiency and reduce communication amounts, a hierarchical CDTA variant is proposed, which uses a composite fitness function incorporating communication connectivity, spatial distance proximity, and capability matching to approximate allocation quality without executing full distributed allocation. Extensive simulations demonstrate that CDTA and hierarchical CDTA achieve high task allocation success rates, excellent load balancing, competitive marginal utility, and significant reductions in communication and time consumption compared to baseline CBBA and grouped CBBA (G-CBBA) under communication-constrained and heterogeneous scenarios. Specifically, in large-scale scenarios (60 UUVs and 120 tasks), CDTA and its variant cut time consumption by over 94% and 99% under severe communication constraints, while maintaining a 100% success rate and highly competitive marginal utility.
AB - Existing task allocation methods for multi-UUV systems often lack robustness under communication constraints, incur high computational costs, and scale poorly, hindering real-world underwater applications. Therefore, this paper addresses the challenge of large-scale task allocation for heterogeneous unmanned underwater vehicles (UUVs) operating in dynamic and uncertain environments with communication constraints. We propose a centralized distributed task allocation (CDTA) algorithm that combines the benefits of centralized and distributed approaches. The framework consists of two main phases: a centralized pre-allocation phase and a distributed allocation phase. In the centralized pre-allocation phase, an improved discrete genetic algorithm (IDGA) with adaptive crossover and mutation strategies is introduced to assign UUVs to task clusters from a global perspective. A balanced k-means (bk-means) clustering method is designed to partition tasks into balanced and non-overlapping sub-teams, ensuring an even distribution of tasks and facilitating efficient distributed allocation. In the distributed allocation phase, consensus-based bundle algorithm (CBBA) is applied within each cluster to perform fine-grained task allocation. This hierarchical decomposition achieves high task allocation success rates and competitive marginal utility even in extremely poor communication environments, while relatively reducing communication and computational complexity. To further enhance computational efficiency and reduce communication amounts, a hierarchical CDTA variant is proposed, which uses a composite fitness function incorporating communication connectivity, spatial distance proximity, and capability matching to approximate allocation quality without executing full distributed allocation. Extensive simulations demonstrate that CDTA and hierarchical CDTA achieve high task allocation success rates, excellent load balancing, competitive marginal utility, and significant reductions in communication and time consumption compared to baseline CBBA and grouped CBBA (G-CBBA) under communication-constrained and heterogeneous scenarios. Specifically, in large-scale scenarios (60 UUVs and 120 tasks), CDTA and its variant cut time consumption by over 94% and 99% under severe communication constraints, while maintaining a 100% success rate and highly competitive marginal utility.
KW - CBBA
KW - Centralized distributed
KW - Clustering
KW - Intelligent algorithm
KW - Multiple UUVs
KW - Task allocation
UR - https://www.scopus.com/pages/publications/105052862073
U2 - 10.1007/s11227-026-08905-8
DO - 10.1007/s11227-026-08905-8
M3 - 文章
AN - SCOPUS:105052862073
SN - 0920-8542
VL - 82
JO - Journal of Supercomputing
JF - Journal of Supercomputing
IS - 15
M1 - 767
ER -