Benchmarking Classical Coverage Path Planning Heuristics on Irregular Hexagonal Grids for Maritime Coverage Scenarios

• URL: http://arxiv.org/abs/2604.15202v1
• Date: Thu, 16 Apr 2026 16:28:03 GMT
• Title: Benchmarking Classical Coverage Path Planning Heuristics on Irregular Hexagonal Grids for Maritime Coverage Scenarios
• Abstract summary: This paper presents a reproducible benchmark of deterministic single-vehicle coverage planning on irregular hexagonal grids.<n>The benchmark contains 10,000 Hamiltonian-feasible instances spanning compact, elongated, and irregular morphologies.<n>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.
• Score: 1.2891210250935148
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Tailoring Strictly Proper Scoring Rules for Downstream Tasks: An Application to Causal Inference [48.78219918881965]
  We propose a principled framework for deriving task-specific strictly proper scoring rules by matching the local curvature of the downstream error metric.<n>We apply this to the Average Treatment Effect (ATE) estimation, deriving a closed-form loss and its corresponding canonical probability mapping.
  arXiv  Detail & Related papers  (2026-06-02T08:41:25Z)
• Fitting Unknown Number of Hyperplanes with Manifold Optimization [57.48093263119306]
  Fitting unknown number of linearplanes to data is a fundamental yet challenging problem in machine learning.<n>Existing approaches often struggle with optimum optima or lack geometric consistency.
  arXiv  Detail & Related papers  (2026-05-27T14:02:20Z)
• Reading Calibrated Uncertainty from Language Model Trajectories [46.663987199083245]
  Methods that probe the model's internal activations feed raw hidden states into opaque snapshots and leave implicit the layer-wise trajectory by which a representation is formed.<n>We extract eleven scale-invariant geometric features, tracing the cumulative path of per-layer updates, and feed them to a sparse linear probe.<n>The probe outperforms MSP under selective abstention, with baseline scaling with up to 21 AURC points.
  arXiv  Detail & Related papers  (2026-05-19T19:24:29Z)
• Sector-dominant graph-local drivers for path-window barrier Hamiltonians on the Boolean hypercube [0.0]
  We study finite-size adiabatic state preparation on Boolean hypercubes.<n>We use graph-local drivers built from sector/path coordinates related to monotone Gray-code representatives.<n>We provide code, finite certificates, CSV files, validation logs, and reproduction scripts to make the finite-size claims traceable.
  arXiv  Detail & Related papers  (2026-04-28T10:54:42Z)
• Skyline-First Traversal as a Control Mechanism for Multi-Criteria Graph Search [0.0]
  This paper shows that under constrained cost models, finite cost grids, Markovian transitions, and a nonzero progress measure, Pareto geometry alone is sufficient to drive both scheduling and termination.<n>Our analysis establishes deterministic potential descent, certified termination via dominance coverage, a uniform bound on layer width induced by cost-grid geometry, and greedy cost-space dispersion within the skyline.
  arXiv  Detail & Related papers  (2026-04-14T08:44:24Z)
• Critic-Free Deep Reinforcement Learning for Maritime Coverage Path Planning on Irregular Hexagonal Grids [1.2891210250935148]
  Maritime surveillance missions rely on the efficient allocation of sensing assets over vast and geometrically complex areas.<n>Traditional Coverage Path Planning approaches struggle with irregular coastlines, islands, and exclusion zones.<n>We propose a Deep Reinforcement Learning framework to solve CPP on hexagonal grid representations of irregular maritime areas.
  arXiv  Detail & Related papers  (2026-03-30T12:56:38Z)
• Decoupling Geometric Planning and Execution in Scalable Multi-Agent Path Finding [44.79409119345322]
  Multi-Agent Path Finding (MAPF) requires collision-free trajectories for multiple agents on a shared graph.<n>We propose a hybrid prioritized framework that separates geometric planning from execution-time conflict resolution.
  arXiv  Detail & Related papers  (2026-03-11T11:04:54Z)
• Compact Conformal Subgraphs [19.72191566715581]
  "graph-based conformal compression" is a framework for constructing compact subgraphs.<n>We design efficient approximation algorithms that achieve constant factor coverage and size trade-offs.
  arXiv  Detail & Related papers  (2026-02-07T12:55:54Z)
• Learning Shortest Paths When Data is Scarce [3.3012620893449465]
  We study a shortest-path problem in which a planner has access to abundant synthetic samples, limited real-world observations, and an edge-similarity capturing expected behavioral similarity across links.<n>We model the simulator-to-reality discrepancy as an unknown, edge-specific bias that varies smoothly over the similarity graph, and estimate it using Laplacian-regularized least squares.<n>For cold-start settings without initial real data, we develop a bias-aware active learning algorithm that adaptively selects edges to measure until a prescribed accuracy is met.
  arXiv  Detail & Related papers  (2026-01-07T06:19:04Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs [56.246783503873225]
  This paper revisits the weighted strategy for non-stationary parametric bandits.<n>We propose a simpler weight-based algorithm that is as efficient as window/restart-based algorithms.<n>Our framework can be used to improve regret bounds of other parametric bandits.
  arXiv  Detail & Related papers  (2026-01-03T04:50:21Z)
• The Coverage Principle: How Pre-Training Enables Post-Training [70.25788947586297]
  We study how pre-training shapes the success of the final model.<n>We uncover a mechanism that explains the power of coverage in predicting downstream performance.
  arXiv  Detail & Related papers  (2025-10-16T17:53:50Z)
• Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
  Learning disentangled representations from unlabelled data is a fundamental challenge in machine learning.<n>We introduce a novel approach to disentangled representation learning based on quadratic optimal transport.<n>We demonstrate the effectiveness of our approach for quantifying disentanglement across four standard benchmarks.
  arXiv  Detail & Related papers  (2024-07-10T16:51:32Z)
• Refined Edge Usage of Graph Neural Networks for Edge Prediction [51.06557652109059]
  We propose a novel edge prediction paradigm named Edge-aware Message PassIng neuRal nEtworks (EMPIRE) We first introduce an edge splitting technique to specify use of each edge where each edge is solely used as either the topology or the supervision. In order to emphasize the differences between pairs connected by supervision edges and pairs unconnected, we further weight the messages to highlight the relative ones that can reflect the differences.
  arXiv  Detail & Related papers  (2022-12-25T23:19:56Z)
• From Spectral Graph Convolutions to Large Scale Graph Convolutional Networks [0.0]
  Graph Convolutional Networks (GCNs) have been shown to be a powerful concept that has been successfully applied to a large variety of tasks. We study the theory that paved the way to the definition of GCN, including related parts of classical graph theory.
  arXiv  Detail & Related papers  (2022-07-12T16:57:08Z)
• Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [29.85468294601847]
  We revisit two classic high-dimensional online learning problems, namely linear regression and contextual bandits. We show that our algorithms succeed where conventional methods fail.
  arXiv  Detail & Related papers  (2020-10-08T17:59:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.