Benchmarking Classical Coverage Path Planning Heuristics on Irregular Hexagonal Grids for Maritime Coverage Scenarios
Carlos S. Sepúlveda and Gonzalo A. Ruz · 2026
Read Benchmarking Classical Coverage Path Planning Heuristics on Irregular Hexagonal Grids for Maritime Coverage Scenarios by Carlos S. Sepúlveda and Gonzalo A. Ruz (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-15202.txt.
Introduction
Sepúlveda and Ruz benchmark classical coverage path planning on irregular hexagonal grids for sea work. Their suite holds 10000 feasible cases across compact, stretched, and uneven shapes, with 17 heuristics from seven families. A shared test scores Hamiltonian success, full coverage, revisits, CPU latency, path length, and heading changes. Heuristics with direct shortest-path reconnection solve the relaxed task well but almost never achieve zero-revisit tours.
Catalog record
| CREATOR | Carlos S. Sepúlveda and Gonzalo A. Ruz |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31160 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.15202
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Benchmarking Classical Coverage Path Planning Heuristics on Irregular Hexagonal Grids for Maritime Coverage Scenarios Carlos S. Sepúlveda and Gonzalo A. Ruz Abstract Coverage path planning on irregular hexagonal grids is relevant to maritime surveillance, search and rescue and environmental monitoring, yet classical methods are often compared on small ad hoc examples or on rectangular grids. This paper presents a reproducible benchmark of deterministic single-vehicle coverage path planning heuristics on irregular hexagonal graphs derived from synthetic but maritime-motivated areas of interest. The benchmark contains 10 000 Hamiltonian-feasible instances spanning compact, elongated, and irregular morphologies, 17 heuristics from seven families, and a common evaluation protocol covering Hamiltonian success, complete-coverage success, revisits, path length, heading changes, and CPU latency. Across the released dataset, heuristics with explicit shortest-path reconnection solve the relaxed coverage task reliably but almost never produce zero-revisit tours. Exact Depth-First Search confirms that every released instance is Hamiltonian-feasible. The strongest classical Hamiltonian baseline is a Warnsdorff variant that uses an index-based tie-break together with a terminal-inclusive residual-degree policy, reaching 79.0% Hamiltonian success. The dominant design choice is not tie-breaking alone, but how the residual degree is defined when the endpoint is reserved until the final move. This shows that underreported implementation details can materially affect performance on sparse geometric graphs with bottlenecks. The benchmark is intended as a controlled testbed for heuristic analysis rather than as a claim of operational optimality at fleet scale. I Introduction Coverage path planning (CPP) seeks trajectories that observe every point in an area of interest (AOI) while controlling travel effort, redundancy, and maneuvering complexity [ 1 , 2 , 3 , 4 ] . In ocean and coastal operations, CPP arises in persistent surveillance, search and rescue, environmental monitoring, and inspection missions performed by unmanned surface, aerial, or underwater vehicles [ 5 , 6 ] . In these settings, the AOI is rarely convex: coastlines, islands, exclusion zones, and navigational constraints generate narrow passages and bottleneck corridors that challenge simple sweep patterns. Hexagonal discretizations are attractive for maritime sensing because they provide near-isotropic local connectivity, uniform neighbor distance, and a natural approximation to circular sensing footprints [ 7 , 8 ] . However, most CPP comparisons in the literature either focus on rectangular grids, exact methods on small instances, or case-specific examples that do not support broad conclusions about robustness across irregular topologies [ 2 , 3 , 9 ] . This paper addresses a narrower but practically important question: how do classical deterministic CPP heuristics compare when they are evaluated under a common protocol on a large set of irregular hexagonal graphs that remain small enough to audit for Hamiltonian feasibility? We do not propose a new planner. Instead, we contribute a controlled benchmark that makes algorithmic strengths, failure modes, and implementation sensitivities visible. The main contributions are: 1. A dataset of 10 000 irregular hexagonal AOIs with three morphology families and verified Hamiltonian feasibility. 2. A common implementation and evaluation protocol for 17 deterministic heuristics from seven families, all operating on the same graph model and start / return conventions. 3. A comparative analysis covering Hamiltonian success, complete-coverage success, revisits, path length, heading changes, latency, morphology-specific behavior, and failure modes. 4. Evidence that residual-degree policy under endpoint reservation is a first-order design choice for Warnsdorff-style traversal on sparse hexagonal graphs, whereas tie-breaking acts as a secondary effect. 5. Public release of the benchmark generator, audited instances, and evaluation scripts to support reproducible comparison with future heuristic, exact, and learning-based methods. II Related Work Classical CPP surveys organize methods by decomposition and traversal strategy, including cellular decomposition, spanning-tree coverage, and sweep-based patterns [ 1 , 2 , 3 , 4 ] . Boustrophedon coverage [ 1 ] and spanning-tree coverage [ 10 ] remain standard baselines because they provide simple deterministic behavior and strong relaxed-coverage guarantees. Bahnemann et al. [ 11 ] recently revisited boustrophedon planning as a generalized TSP, highlighting the gap between classical sweep assumptions and practical irregular decompositions. Hexagonal decompositions have been explored in robotics and UAV coverage because their geometry reduces directional bias and supports natural neighborhood relations [ 7 , 12 , 8 ] . In maritime settings, hexagonal grids also appear in exact or mixed-integer formulations for multi-UAV search and rescue [ 5 , 6 ] . Those works are important for operational motivation, but they do not provide a large-scale benchmark of classical heuristics on irregular sparse hexagonal graphs. Warnsdorff’s rule, originally proposed for the Knight’s Tour [ 13 ] and later generalized to Hamilton paths on graphs [ 14 ] , is a natural degree-based heuristic for sparse traversal problems. In the specific context of hexagonal grid graphs, Hamiltonicity has also been studied from a graph-theoretic perspective [ 15 ] . The appeal of Warnsdorff-style traversal lies in the simplicity of the residual-degree heuristic. Its weakness is that local choices can irreversibly consume articulation-like corridor cells in irregular topologies. The present benchmark shows that Warnsdorff is not fully specified by “choose the minimum residual degree” alone when the terminal node is reserved until the final move: the operational definition of residual degree itself matters. Recent combinatorial-optimization benchmarks emphasize Euclidean routing on complete graphs [ 16 ] . CPP on sparse geometric graphs is structurally different: adjacency constraints, obstacle-induced bottlenecks, and the distinction between relaxed coverage and zero-revisit traversal are central. A dedicated benchmark is therefore justified. III Problem Formulation III-A Hexagonal AOI Graph Let \mathcal{A}\subset\mathbb{R}^{2} denote a polygonal area of interest (AOI), possibly with interior holes representing forbidden or obstructed regions. Rather than using an exact continuous-space decomposition, we adopt a fixed-resolution approximate cellular decomposition based on a regular hexagonal lattice. The lattice is aligned with the minimum rotated rectangle of \mathcal{A} and instantiated as an even- q offset grid with hexagon circumradius h . A hexagonal cell is retained if it has sufficient geometric support in the free space according to intersection and overlap tests with the AOI and its holes. The resulting binary occupancy mask is then post-processed to remove discretization artifacts: we keep the largest connected component, remove interior dead ends, preserve a single exterior boundary ring, and enforce accessibility from the exterior border. This post-processing suppresses discretization-induced topological artifacts so that benchmark failures are attributable to heuristic behavior rather than to spurious graph defects. This yields a set of visitable cells \mathcal{V} with |\mathcal{V}|\in[28,46] . An undirected graph G=(\mathcal{V}\cup\{b,b^{\prime}\},\mathcal{E}) is finally constructed by connecting face-adjacent visitable hexagons. A departure node b and a return node b^{\prime} are attached only to cells on the outer ring that admit a feasible line-of-sight connection from the launch location. We emphasize that this representation is intended to define a controlled family of sparse hexagonal graphs for reproducible benchmarking and exact Hamiltonian auditing, rather than to claim an exact geometric decomposition of the continuous AOI. The choice of a regular hexagonal discretization is deliberate. Relative to square grids, hexagonal cells provide a more isotropic local neighborhood and a natural surrogate for approximately circular sensing footprints, while still yielding graphs of manageable size for exhaustive feasibility auditing. Conversely, exact cellular decompositions are often preferable when continuous boundary fidelity is the primary concern. In this work, our objective is not to optimize the decomposition itself, but to compare CPP