Coverage Path Planning for Holonomic UAVs via Uniaxial-Feasible, Gap-Severity Guided Decomposition
Pedro Antonio Alarcon Granadeno, Jane Cleland-Huang
AI summary
Problem
Modern coverage path planning pipelines overfragment highly irregular, asymmetric regions of interest into numerous small subregions, forcing excessive inter-region travel and frequent reorientation that degrade trajectory quality and increase completion time.
Approach
The method recursively partitions complex polygons only when they fail a relaxed uniaxial monotonicity test, using a cumulative gap severity metric to guide cuts and distribute concavities evenly. A global optimizer then jointly selects optimal sweep directions and visitation orders to minimize total path length and transition overhead.
Key results
- Achieves lowest mean path-length and completion-time overhead among 15 competing CPP pipelines
- Generates a minimal set of larger, sweepable partitions by evenly distributing concavity clusters
- Eliminates premature fragmentation through relaxed monotonicity testing and iterative partition merging
- Jointly optimizes sweep paths and inter-partition transitions to reduce translational acceleration overhead
Why it matters
Enables faster, more reliable UAV search and rescue operations in complex, real-world environments where traditional decomposition methods fail.
Abstract
Modern coverage path planning (CPP) for holo- nomic UAVs 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 path-length and completion-time overhead among 15 other CPP pipelines.