基于时空密度聚类的异构无人机集群覆盖路径规划方法

Coverage path planning is one of the key technologies for unmanned aerial vehicle(UAV) swarms in performing the exploration missions such as search and rescue. However, the current research often focuses on the design and optimization of flight paths in a single region, without taking into account quantitatively the effect of UAV capability on region division and start and end point selection in multi-region environment. Meanwhile, most of the existing methods use homogeneous UAV swarms to perform the coverage path planning task, ignoring the ability differences among the UAVs, resulting in a low utilization ratio of swarm resources and much difficulty in adapting to the uncertain changes of tasks and environments. This paper focuses on the coverage path planning problem of heterogeneous UAVs on multiple regions. First, by modeling the heterogeneous UAVs and analyzing the road and energy constraints of the path planning problem, we propose an exact formulation based on mixed integer linear programming to completely search the solution space and to find the best flight roads for UAVs. Then we present an efficient path planning algorithm based on temporal-spatial density clustering to improve the solving efficiency of the coverage path planning problem. The proposed algorithm groups regions according to their densities in time and space, allocates a reasonable group to each UAV, and optimizes the visiting orders of regions and the scan paths in regions, ensuring that the coverage task would be finished effectively. Experimental results show that the proposed method will provide reasonable flight paths for UAVs, and the total flight length and the task completion time can be reduced by 10.55% and 5.47%, respectively.