Path Refinement for Large-Scale Heterogeneous Multi-UAV Coverage

The emergence of Unmanned Aerial Vehicles (UAVs) has transformed static Wireless Sensor Networks (WSNs) into dynamic mobile sensing networks, enabling large-scale data acquisition for applications such as surveillance and precision agriculture. In these missions, multiple heterogeneous UAVs equipped with onboard sensors (e.g., cameras, multispectral sensors or LiDAR units) must collaboratively perform area coverage. The efficiency of the planned paths, governed by the Heterogeneous Multi-robot Coverage Path Planning (HMCPP) problem, directly impacts mission success. However, existing approaches to HMCPP are often limited by either prohibitive computational complexity or suboptimal path efficiency. To address this challenge, the HMCPP problem is modeled from a graph-based perspective, and a novel framework, termed Heterogeneous Cost Balancing (HCB), is introduced to efficiently generate high-quality solutions. HCB transforms existing solutions into HMCPP solutions by integrating fine-grained planning with cost-balancing strategies. Specifically, the proposed fine-grained planning approach refines traditional spiral routes, reducing path redundancy and enhancing coverage efficiency. Experimental results demonstrate that HCB outperforms baseline methods in most instances while maintaining high computation efficiency. Notably, on a large-scale real-world map (366 × 376 with 40 UAVs), HCB achieves improvements in makespan of 33.82%, 9.79%, 6.37%, and 12.34% over four heuristic-based baselines, and an 86.66% improvement over MIP-based approach.