An Optimization Method for UAV Multi-point Coverage Flight Trajectory Based on K-Means Ant Colony Algorithm

To address the problem of low computational efficiency of traditional intelligent optimization algorithms in large-scale unmanned aerial vehicle (UAV) multi-waypoint path planning, this paper proposes a K-Means ant colony based flight trajectory optimization algorithm for UAV multi-point coverage. The algorithm first employs K-Means clustering to decompose large-scale waypoint sets into multiple smaller sub-problems, then applies ant colony optimization to solve each sub-problem separately, and finally constructs the complete flight path through a sub-path connection strategy. Experimental results on four standard test datasets (gr137, Tsp225, Linhp318, and Att532) demonstrate that compared with traditional ant colony optimization (ACO), genetic algorithm (GA), and particle swarm optimization (PSO), the proposed algorithm achieves significant improvements in computational efficiency: achieving 7.0–37.7 times speedup on small and medium-scale problems, and solving large-scale problems in only 37.77–107.16 s while traditional algorithms fail to converge within 20 min. Meanwhile, the proposed algorithm exhibits excellent scalability while maintaining good solution quality, effectively handling large-scale path planning problems with up to 532 waypoints. In terms of path quality, the algorithm achieves path lengths comparable to traditional algorithms on small and medium-scale waypoint test sets (gr137 and Tsp225), and obtains superior paths through short-time computation on large-scale waypoint test sets. The research results indicate that the proposed algorithm provides an efficient and feasible solution for large-scale UAV multi-waypoint path planning with significant practical application value in engineering applications.