Full-Coverage Path Planning for Heterogeneous UUVs Using a Hybrid Detection Point Layout and a Dual-Chromosome Co-Evolutionary Genetic Algorithm

Abstract

To address the issue of unbalanced path allocation in multi-UUV cooperative operations under inhomogeneous ocean environments during full-coverage search missions, this paper proposes a heterogeneous UUV path planning method that integrates a hybrid waypoint deployment strategy with a dual-chromosome co-evolutionary genetic algorithm. First, heterogeneous UUVs are adaptively assigned to sub-regions according to the search value of the sea area, and a combination of Poisson sampling and Voronoi iterative refinement is adopted to complete the layout of detection points. Subsequently, connectivity-constrained K-means clustering is introduced to decompose the multi-traveling salesman problem (MTSP) into several independent TSP sub-problems. Finally, a dual-chromosome encoding scheme for task sequences and split points is designed, and a penalty matrix is incorporated into the fitness function to account for obstacle avoidance constraints, thereby establishing an integrated genetic-algorithm-based solution framework that incorporates both decomposition and obstacle avoidance. Simulation results demonstrate that the proposed method reduces the number of planned detection points by 12.4%, 12.8%, and 9.3% compared with baseline methods in circular, rectangular, and irregular sea areas, respectively, while the optimal path lengths are shortened by 5.8%, 4.5%, and 5.9%. Moreover, the cooperative mission time with four UUVs is reduced by 73.9%, 72.7%, and 71.2% relative to a single UUV, demonstrating an approximately linear speedup relative to the number of UUVs. Convergence analysis and extended experiments on 15 instances further confirm the algorithm’s solution stability and robustness under varying regional scales, shapes, and obstacle configurations. These results validate that the proposed approach not only reduces the number of deployment points and path cost, but also effectively balances obstacle avoidance and multi-robot load distribution.