H3CPP: Boundary-Safe Coverage Path Planning for Multi-USV Operations in Irregular Coastal Environments

As the need for persistent ocean monitoring grows, fleets of Unmanned Surface Vessels (USVs) are a promising way to survey large marine protected areas with low operational cost. Their effectiveness, however, depends on solving a challenging multi-robot Coverage Path Planning (CPP) problem over complex coastal geometries while strictly respecting safety boundaries. This paper presents H3CPP, a CPP framework that leverages the H3 hierarchical hexagonal grid to discretize arbitrarily shaped marine areas, cluster them into connected subregions, and construct boundary-aware graphs on which Traveling Salesman Problem (TSP) tours are computed. Each H3 cell is sized to match the nominal sensing footprint of a USV, and edges that intersect land or forbidden zones are exponentially penalized, encouraging safe paths that remain within the operational polygon. We evaluate H3CPP on seven benchmark polygonal maps and on a real-world coastal marina using 1–10 USVs. For a single USV in complex, non-convex environments, H3CPP achieves near-complete coverage (coverage ratio ≈ 1.0 of the target area) while avoiding boundary violations that occur with swath and spiral baselines, and reduces path length by up to 10% compared to these methods in the most irregular shapes. In the Syros marina scenario, multi-USV experiments show that H3CPP decreases the total traveled distance by 4–34% (≈ 20% on average) relative to a decomposition-plus-swaths baseline, while maintaining similar coverage and systematically reducing mission makespan as the fleet size increases from 1 to 10 USVs. The proposed framework therefore combines geodesic hexagonal indexing, connectivity-aware clustering, and penalized graph-based TSP planning into a practical CPP solution for USV swarms operating in realistic coastal environments.