Constrained Delaunay Triangulation-Driven Coverage Path Planning for Multi-UAVs in Concave Polygonal Areas
Xinyuan Huang, Jie Li, Xiangke Wang, Fangge Cui · 2025
This paper proposes an innovative method for the minimum-time coverage problem in multi-Unmanned Aerial Vehicle (UAV) over concave polygonal regions. The proposed method first uses Constrained Delaunay Triangulation (CDT) to generate high-quality triangular meshes while respecting the boundary constraints of the given region. It then merges these triangles into multiple convex polygons through a merging process with area balancing. Finally, these sub-regions are assigned to the corresponding UAVs based on their comprehensive capabilities. Additionally, a mixed-integer linear programming (MILP) model incorporating UAV constraints is constructed and solved using Solving Constraint Integer Programs (SCIP) for optimal path planning. Finally, simulation experiments demonstrate that the proposed method effectively achieves multi-UAV coverage by decomposing concave areas into convex sub-regions, reducing redundant path length by$17 \%-34 \%$compared to existing methods, and improving solving efficiency by 86% through optimal task allocation.