Multi-UAV Coverage Path Planning Based on Balanced Graph Partitioning

Abstract

Coverage path planning is a critical problem in multi-UAV systems for daily inspection and patrol missions, requiring coordinated movements of UAVs along predetermined trajectories to cover the entire map. Existing methods are often inadequate in considering both workload balance and motion efficiency during task assignment, resulting in imbalanced coverage areas or unnecessary turning maneuvers. To address these limitations, this paper presents a hierarchical structure that integrates spatial decomposition, balanced task assignment through graph partitioning, and turn-aware trajectory planning. The approach follows three key steps: first, spatial decomposition partitions the map into subregions; second, the partitioned map is transformed into a weighted graph, where task assignment distribution is optimized by iteratively migrating and swapping nodes among subgraphs while preserving connectivity, ensuring a balanced workload distribution across UAVs. Finally, trajectory planning incorporates turn optimization to reduce completion time. The results show that our method ensures even task assignment among UAVs, fewer turns, faster task completion, and lower computation time compared to other popular algorithms.