A Clustering-Based Coverage Path Planning Method for Autonomous Heterogeneous UAVs

Unmanned aerial vehicles (UAVs) have been widely applied in civilian and military applications due to their high autonomy and strong adaptability. Although UAVs can achieve effective cost reduction and flexibility enhancement in the development of large-scale systems, they result in a serious path planning and task allocation problem. Coverage path planning, which tries to seek flight paths to cover all of regions of interest, is one of the key technologies in achieving autonomous driving of UAVs and difficult to obtain optimal solutions because of its NP-Hard computational complexity. In this paper, we study the coverage path planning problem of autonomous heterogeneous UAVs on a bounded number of regions. First, with models of separated regions and heterogeneous UAVs, we propose an exact formulation based on mixed integer linear programming to fully search the solution space and produce optimal flight paths for autonomous UAVs. Then, inspired from density-based clustering methods, we design an original clustering-based algorithm to classify regions into clusters and obtain approximate optimal point-to-point paths for UAVs such that coverage tasks would be carried out correctly and efficiently. Experiments with randomly generated regions are conducted to demonstrate the efficiency and effectiveness of the proposed approach.