Point cloud partition–based three-dimensional coordinated coverage path planning for unmanned aerial vehicles

Abstract

For coordinated three-dimensional coverage tasks involving multiple unmanned aerial vehicles, a method based on three-dimensional point cloud clustering and partitioning is proposed to balance task workload among unmanned aerial vehicles and reduce redundant coverage. First, a sub-region partitioning strategy that preserves building structural integrity is designed to improve the rationality of regional decomposition, and a distributed auction mechanism is constructed to coordinate the allocation of sub-regions among unmanned aerial vehicles. Then, a sub-region coverage path generation method, GA-LKH, which combines genetic algorithm (GA) and Lin–Kernighan–Helsgaun (LKH) algorithm, is developed. The genetic algorithm guides the LKH search process by providing high-quality initial solutions, thereby reducing the path length of individual unmanned aerial vehicles. Statistical comparisons show that the proposed method significantly reduces the total path length compared with multi-robot coverage path planning (MCPP) and LKH-3 and significantly shortens the task completion time compared with LKH-3. In addition, the complete planning latency remains below 1 s in all tested scenarios, demonstrating the computational efficiency of the proposed method.