Coverage Path Planning for Holonomic UAVs via Uniaxial-Feasible, Gap-Severity Guided Decomposition

Abstract-- Modern coverage path planning (CPP) for holo-nomic UA Vs in emergency response must contend with diverse environments where regions of interest (ROIs) often take the form of highly irregular polygons, characterized by asymmetric shapes, dense clusters of concavities, and multiple internal holes. Modern CPP pipelines typically rely on decomposition strategies that overfragment such polygons into numerous subregions. This increases the number of sweep segments and connectors, which in turn adds inter-region travel and forces more frequent reorientation. These effects ultimately result in longer completion times and degraded trajectory quality. We address this with a decomposition strategy that applies a recursive dual-axis monotonicity criterion with cuts guided by a cumulative gap severity metric. This approach distributes clusters of concavities more evenly across subregions and produces a minimal set of partitions that remain sweepable under a parallel-track maneuver . We pair this with a global optimizer that jointly selects sweep paths and inter-partition transitions to minimize total path length, transition overhead, and turn count. We demonstrate that our proposed approach achieves the lowest mean overhead in path length and completion time across 13 notable CPP pipelines. Coverage Path Planning (CPP) generates trajectories that fully observe a Region of Interest (ROI) with minimal cost, typically measured in path length, turns, execution time, or energy use. A dominant strategy in aerial and ground robotics is parallel-track coverage, where back-and-forth sweeps (e.g., boustrophedon) tile the region. For convex ROIs, selecting an optimal sweep direction is straightforward.