Critic-Free Deep Reinforcement Learning for Maritime Coverage Path Planning on Irregular Hexagonal Grids

Carlos S. Sepúlveda; Gonzalo A. Ruz

cs.LGMar 30, 2026

Critic-Free Deep Reinforcement Learning for Maritime Coverage Path Planning on Irregular Hexagonal Grids

Authors: Carlos S. Sepúlveda, Gonzalo A. Ruz

Organizations: Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Av. Diagonal las Torres 2640, Santiago, Chile · Dirección de Programas, Investigación y Desarrollo, Armada de Chile, General del Canto 398, Valparaíso, Chile · Millennium Nucleus for Social Data Science (SODAS), Santiago, Chile · Millennium Nucleus in Data Science for Plant Resilience (PhytoLearning), Santiago, Chile

Abstract

Maritime surveillance missions, such as search and rescue and environmental monitoring, rely on the efficient allocation of sensing assets over vast and geometrically complex areas. Traditional Coverage Path Planning (CPP) approaches depend on decomposition techniques that struggle with irregular coastlines, islands, and exclusion zones, or require computationally expensive re-planning for every instance. We propose a Deep Reinforcement Learning (DRL) framework to solve CPP on hexagonal grid representations of irregular maritime areas. Unlike conventional methods, we formulate the problem as a neural combinatorial optimization task where a Transformer-based pointer policy autoregressively constructs coverage tours. To overcome the instability of value estimation in long-horizon routing problems, we implement a critic-free Group-Relative Policy Optimization (GRPO) scheme. This method estimates advantages through within-instance comparisons of sampled trajectories rather than relying on a value function. Experiments on 1,000 unseen synthetic maritime environments demonstrate that a trained policy achieves a 99.1% Hamiltonian success rate, more than double the best heuristic (46.0%), while producing paths 7% shorter and up to 24.1% fewer heading changes than the closest heuristic baseline. All three inference modes (greedy, stochastic sampling, and sampling with 2-opt refinement) operate under 50 ms per instance on a laptop GPU, confirming feasibility for real-time onboard deployment.

Figures & tables

Approach (family / representative works)	Hex	Irreg. AOI	Main method	Single visit	Amort. policy	Turn cost	RT infer.
Classical CPP decomposition ( Choset, 2001 ; Galceran and Carreras, 2013 ; Cabreira et al., 2019 )	$\times$	$\sim$	Cellular decomposition / sweep	$\times$	$\times$	$\sim$	$\sim$
Hex-based SAR / coverage optimization ( Cho et al., 2021b ; Cho et al., 2021a ; Kadioglu et al., 2019 )	✓	$\sim$	Hex decomposition + MILP / graph optimization	$\sim$	$\times$	$\times$	$\times$
USV coastal bathymetric survey ( Zhao et al., 2024 )	$\times$	✓	Coastline approximation + evolutionary sequencing	$\times$	$\times$	$\sim$	$\times$
USV offshore bathymetric survey ( Zhao and Bai, 2024 )	$\times$	✓	Integer programming / hierarchical planning	$\times$	$\times$	$\sim$	$\times$
Multi-USV cooperative coverage ( Shen et al., 2025 ; Ma et al., 2026 )	$\times$	✓	Task allocation / cooperative game + FSM	$\times$	$\times$	$\sim$	$\sim$
Grid-MDP maritime CPP with DRL ( Ai et al., 2021 ; Wu et al., 2024 )	$\times$	$\sim$	DRL over grid states	$\times$	$\sim$	$\sim$	$\sim$

Table 1: Positioning of representative approaches to maritime and graph-based coverage planning. ✓: explicitly addressed;

\sim

: partially addressed or addressed under different assumptions;

\times

: not a primary focus.

Panel of Figure 1 — Figure 1: Taxonomy of surveillance-related coverage, patrolling, and routing problems underpinning our CPP formulation on hexagonal grids. The three columns mirror the structure of the Related work section, while Table 9 provides a concise summary of the corresponding problem families.

Panel of Figure 2 — Figure 2: Hexagonal tessellation-to-graph pipeline for an irregular AOI with an internal obstacle. Hexagon size is set by the sensor footprint. (a) AOI, obstacle, and OBB. (b) OBB-aligned hex grid. (c) Visitable cells selected by intersection tests. (d) Graph edges defined by hex-neighborhood adjacency using cell centers (including the base node). (e) Final graph used for coverage planning. (The pipeline is illustrated with an explicit polygonal obstacle for visual clarity; in the experimental dataset, obstacles are implemented as individual cell removals, see Section 5.1 .)

Component	Value	Type	Operational justification
$r_{step}$	$+2.0$	Dense	Incentive per newly visited hexagonal cell.
$r_{hex}$	$+0.5\cdot w_{v_{t}}$	Dense	Time-decayed priority bonus for early visitation of high-value zones (inactive in uniform-coverage experiments) $\dagger$ .
$c_{dist}$	$-1.0\cdot\bar{d}$	Dense	Penalty proportional to normalized inter-cell distance.
$c_{turn}$	$-0.25\cdot f(\theta)$	Dense	Kinematic penalty for sharp heading changes, promoting smooth trajectories.
$r_{complete}$	$+100.0$	Episodic	Sparse reward for full coverage and return to base.
$r_{death}$	$-40.0$	Episodic	Penalty for falling into an unrecoverable geometric dead-end.

Table 2: Dense and episodic components of the reward function.

Figure 3: Proposed Transformer-based pointer policy for coverage path planning. The Graph Encoder pre-computes static node embeddings, while the Decoder dynamically aggregates the agent’s spatial context and environmental signals to generate a query. The Pointer Network computes attention scores over valid nodes, strictly constrained by a feasibility mask to guarantee valid routing.

Parameter	Description	Value
$d$	Model dimension	128
$L$	Encoder layers	3
$n_{h}$	Attention heads	8
$K_{glimpse}$	Decoder glimpses	2
$G$	Rollouts per instance	16
$K$	Inner optimization epochs	4

Table 3: Training hyperparameters.

Family	Method	Description
Linear sweep (Boustrophedon)	sweep_boustrophedon	Classic lawnmower pattern with alternating row directions, minimizing inter-row transit.
	sweep_row_oneway	Unidirectional row sweep; all rows traversed in the same direction with flyback transit.
	sweep_segment_snake	Obstacle-aware boustrophedon that decomposes the AOI into convex segments and applies snake patterns within each.
Interleaved sweep (Skip-row)	sweep_row_interleave	Skips rows to allow wider turning arcs; rows are visited in an interleaved order (e.g., 1, 7, 2, 8, …).
Interleaved sweep (Skip-row)	sweep_segment_interleave	Combines segment decomposition with interleaved row ordering for kinematically constrained vehicles.
Contour / Spiral (Boundary rings)	boundary_spiral_inward	Traces concentric rings from the AOI perimeter inward toward the centroid.

Table 4: Baseline heuristic methods grouped by algorithmic family. All methods operate on the same hex-graph representation under identical constraints.

Figure 4: Training and validation success rate (greedy decoding) across epochs. The dashed line marks the selected checkpoint (epoch 30, val. SR = 95.5%). The shaded region indicates overfitting, where validation performance declines while training performance remains stable.

Panel of Figure 5 — Figure 5: Residual failure modes of the RL-BoK16+2opt inference mode on the nine unsolved test instances (0.9%). All failures arise from severe bottlenecked topologies in which a sampled rollout commits to a branch that leaves remaining cells unreachable under the strict no-revisit constraint. Best-of-16 sampling reduces these events, but adjacency-aware 2-opt cannot recover infeasible partial constructions because it only refines feasible tours. These cases motivate explicit connectivity lookahead or bounded revisitation in future operational variants.

Type	Method	HSR (%)	CCR (%)	Revisits $\mu\pm\sigma$
Feasibility	Exact_DFS	100.0	100.0	0.0 $\pm$	0.0
RL (ours)	RL-BoK16+2opt	99.1	99.1	0.0 $\pm$	0.0
	RL-BoK16	98.6	98.6	0.0 $\pm$	0.0
	RL-Greedy	95.7	95.7	0.0 $\pm$	0.0
Heuristic	Warnsdorff	46.0	46.0	0.0 $\pm$	0.0
	DFS_Backtrack	33.8	100.0	3.2 $\pm$	6.0

Table 5: Coverage performance on 1,000 unseen test instances. HSR: Hamiltonian Success Rate (strict single-visit). CCR: Coverage Completion Rate (revisits permitted). Methods are grouped by type and sorted by HSR within each group.

Configuration	HSR (%)	$\Delta$ HSR
Full (BFS + augmentation)	98.1	—
$-$ BFS dead-end detection	24.8	$-73.3$
$-$ geometric augmentation	97.2	$-0.9$

Table 6: Component ablation (controlled 25-epoch runs, RL-BoK16+2opt decoding on the 1,000 test instances). Each row removes a single component from the full configuration.

Type	Method	$n$	Dist. $\mu\pm\sigma$		Turns $\mu\pm\sigma$		Steps	Revisits
RL	RL-BoK16+2opt	991	3.100 $\pm$	0.314	34.1 $\pm$	5.3	37.8	0.0
	RL-BoK16	986	3.110 $\pm$	0.315	32.3 $\pm$	4.6	37.8	0.0
	RL-Greedy	957	3.111 $\pm$	0.314	32.9 $\pm$	4.9	37.8	0.0
Feasibility	Exact_DFS	991	3.308 $\pm$	0.373	43.5 $\pm$	6.7	37.8	0.0
Heuristic	Warnsdorff	454	3.325 $\pm$	0.379	42.5 $\pm$	5.6	37.2	0.0
	DFS_Backtrack	991	3.340 $\pm$	0.447	49.4 $\pm$	12.4	41.0	3.2

Table 7: Path quality on the pairwise common solved subset with RL-BoK16+2opt (991 of 1,000 test instances solved).

n

denotes the number of instances solved by both the listed method and the RL reference. Methods sorted by normalized distance within each group.

Method	One-time cost	Per-instance cost
Warnsdorff	—	0.4 ms
STC_Tree_Coverage	—	0.4 ms
STC_like	—	0.4 ms
DFS_Backtrack	—	0.6 ms
Morton_Zorder	—	0.7 ms
Sweep_Boundary_Peel	—	0.7 ms

Table 8: Computational cost of all methods, separating one-time (offline) cost from per-instance (online) planning cost. RL inference is measured on a laptop GPU; classical heuristics, the DFS feasibility audit, and the exact/metaheuristic solvers on CPU. The MILP and GA are granted a 300 s per-instance budget (mean solving time reported). Training is a one-time cost, amortized across all instances.

Panel of Figure 6 — Figure 6: Comparative path visualizations across three representative maritime topologies. The leftmost column displays the Exact DFS, denoted by H for Hamiltonian, serving as a topological feasibility reference. Row 1 shows a small open-water configuration where all methods succeed, although STC introduces dense overlaps. Row 2 presents an H-shaped coastal corridor; here, the RL policy achieves a smooth trajectory, whereas greedy local heuristics such as Warnsdorff fail to escape the resulting geometric dead-end. Row 3 illustrates a generic irregular shape, where the RL policy identifies a valid single-visit sequence that avoids the costly kinematic reversals typical of Boustrophedon sweeps.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Family	Typical objective and common formulation	Relation to this work and representative references
Region coverage (CPP)	Achieve complete coverage of a known area of interest (AOI) while minimising path length, time, or energy. Classical CPP uses cellular decompositions (boustrophedon, trapezoidal, convex) and sweep patterns (e.g., lawnmower), extended to multi-robot and UAV settings.	Our hexagonal AOI discretisation is a discrete CPP formulation in which each hex cell represents a region of the maritime AOI. We follow CPP surveys in robotics and UAVs ( Choset, 2001 ; Galceran and Carreras, 2013 ; Cabreira et al., 2019 ; Fevgas et al., 2022 ) and connect to hex-based CPP and SAR planning in maritime contexts ( Azpúrua et al., 2018 ; Cho et al., 2021b ; Kadioglu et al., 2019 ) , and to recent USV-based coastal and offshore survey coverage and cooperative multi-vehicle formulations ( Zhao et al., 2024 ; Zhao and Bai, 2024 ; Shen et al., 2025 ; Ma et al., 2026 ) .
Sweep and barrier coverage	Ensure that every point of a region or a virtual barrier is periodically visited by mobile sensors, subject to revisit intervals or detection constraints. Models often rely on TSP/graph tours, Eulerian paths, or approximation algorithms for large-scale sweep coverage and barrier placement.	When maritime AOIs degenerate into corridors (routes, shorelines, chokepoints), our hex-grid CPP reduces to sweep or barrier-type problems over 1D/2D structures. Sweep-coverage and barrier-coverage results in WSNs ( Li et al., 2011 ; Gorain and Mandal, 2014 ; Benahmed and Benahmed, 2019 ; Nguyen and So-In, 2018 ; Li et al., 2019 ; Kong et al., 2016 ) motivate modeling “barriers” or critical routes via specialized boundary constraints and periodic revisit scheduling.
Patrolling and persistent surveillance	Maintain high-quality surveillance over long horizons by minimizing maximal idle time, maximizing information gain, or enforcing revisit-frequency constraints under vehicle range and kinematic limitations. Formulations often use infinite-horizon control or MILP-based routing with information metrics.	Weighted coverage objective can be interpreted as a single-visit proxy for persistent-surveillance value on hex-grids. Patrolling and persistent-surveillance works with UAVs and surface vehicles ( Nigam et al., 2009 ; Zuo et al., 2020 ; Bandarupalli et al., 2021 ; Savkin and Huang, 2019 ; Luis et al., 2020 ; Luis et al., 2021 ) motivate the use of information-based metrics that could inform future extensions with non-uniform priorities.
Routing for surveillance and mission planning	Plan routes for one or multiple platforms that visit regions or tasks while minimizing mission cost (time, fuel) and respecting range, time windows, and motion constraints. Typical formulations are TSP/VRP variants, orienteering, and Dubins-type routing, often solved via MILP or heuristics.	Our approach inherits the routing structure of maritime surveillance mission-planning models: hex cells act as “customers” to be visited, and tours must satisfy sensor and endurance constraints. Classical radar/SAR routing and UAV mission-planning work ( Panton and Elbers, 1999 ; John et al., 2001 ; Grob, 2006 ; Karasakal, 2016 ; Coutinho et al., 2018 ; Otto et al., 2018 ; Cho et al., 2021b ; Cho et al., 2021a ) serve as baselines to benchmark our learned policies.
Spatial crowdsourcing and task assignment	Assign spatial sensing or monitoring tasks to agents (humans, vehicles, sensors) to maximise utility or coverage subject to capacity, location, and temporal constraints. Models are often matching or assignment problems with uncertainty in agent availability and task locations.	In multi-platform maritime surveillance, our hex-based CPP can be extended with task-assignment layers that allocate subsets of hex cells or sub-tours to heterogeneous assets. Spatial crowdsourcing and mobile-sensing literature ( Wu et al., 2019 ; Bhatti et al., 2021 ; Tong et al., 2020 ; Zhou et al., 2019 ; Chen et al., 2020 ) informs potential extensions where different vehicles or sensor types share the same hex-grid representation.
Learning-based combinatorial optimisation (NCO / RL4CO)	Learn parametric policies that output near-optimal solutions for routing, scheduling, or CPP problems, enabling reuse across instances without re-solving from scratch. Approaches include pointer networks and attention-based models trained with RL or supervised signals on graph-structured inputs.	Our transformer-like pointer policy over hex-graphs belongs to this family. We adapt ideas from attention-based routing and RL4CO ( Vinyals et al., 2015 ; Bello et al., 2016 ; Nazari et al., 2018 ; Kool et al., 2018 ; Xin et al., 2021 ; Li et al., 2021a ; Berto et al., 2025 ; Darvariu et al., 2024 ) and combine them with advanced training strategies for long-horizon coverage on hex-grids, bridging maritime CPP with neural combinatorial optimisation.

Appendix

Table 9: Taxonomy of surveillance-related coverage, patrolling, and routing problems underpinning our CPP formulation on hexagonal grids.

Pointer Networks

See all 10 papers

Apr 16, 2026

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

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.

Carlos S. Sepúlveda, Gonzalo A. Ruz

Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Santiago, Chile · Millennium Nucleus for Social Data Science (SODAS) · Millennium Nucleus in Data Science for Plant Resilience (PhytoLearning)

Robotics Graph-Based Planning Motion Planning Coverage Path Planning Robot Motion Planning

Ask PDF

Aug 19, 2026

Multi-Agent Off-Policy Deep Reinforcement Learning for Smart Campus Coverage

Deep reinforcement learning (DRL) has recently gained a great attention due to its real-time adaptation and effectiveness in complex optimization problems. This paper investigates the optimal deployment of millimeter-wave (mmWave) base stations (BSs) in a realistic, non-convex campus topology. The optimization problem is NP-hard, due to the non-convex, non-smooth nature of the max-min fairness objective. To overcome these constraints, we formulate the BS placement as a Markov Decision Process (MDP) and systematically benchmark four DRL schemes: a discrete single-agent Deep Q-Network (DQN), a spatially partitioned Multi-Agent DQN, a continuous single-agent Deep Deterministic Policy Gradient (DDPG), and a geographically partitioned multi-agent DDPG framework. Numerical evaluations reveal that the multi-agent DDPG approach substantially outperforms single-agent in dense scenarios. Additionally full coverage is achieved, and a fairness Jain's index of 0.94 is obtained. Finally, the multi-agent demonstrates highly efficient computational convergence of dense scenarios with

400

users.

Omar Rady, Mohamed Ayman, Ali Arafa +1

Faculty of Information Engineering and Technology The German University in Cairo Cairo, Egypt

Millimeter-Wave Communications Wireless Communications Multi-Agent Reinforcement Learning Deep Deterministic Policy Gradient

Ask PDF

Jun 7, 2026

Towards End to End Motion Planning and Execution for Autonomous Underwater Vehicles Using Reinforcement Learning

Autonomous Underwater Vehicles (AUVs) traditionally rely on complex, heavily engineered pipelines for perception, path planning, and motion control. This paper explores the feasibility of an end-to-end Deep Reinforcement Learning (DRL) approach that maps raw sensor data directly to thruster commands, reducing manual engineering. We propose a hierarchical reinforcement learning (HRL) architecture splitting the problem into two Markov Decision Processes. A High-Level (HL) policy operating at 2Hz processes raw

84 \times 84

pixel monocular camera frames, stacked

100 \times 100

pixel forward-looking imaging sonar, and proprioceptive data to generate spatial subgoals. Simultaneously, a Low-Level (LL) policy operating at 10Hz converts these subgoals into thruster commands. The HL policy is trained using Reinforcement Learning from Prior Demonstrations (RLPD) within a modified Sample-Efficient Robotic Reinforcement Learning (SERL) framework, while the LL policy utilizes Soft Actor-Critic (SAC) combined with Hindsight Experience Replay (HER). Evaluated in the high-fidelity HoloOcean simulator, our method demonstrates successful obstacle avoidance, achieving trajectory lengths closely approximating (within 4% to 6% of) an

\text{RRT}^*

planning baseline. Furthermore, the learned policy exhibits strong robustness to simulated sensor noise and decreased visibility. While the system navigates familiar geometries effectively, experiments reveal generalization limitations when encountering unvisited areas with novel obstacle shapes. Ultimately, this work demonstrates the promise of sample-efficient, end-to-end DRL for underwater navigation using minimal computational hardware.

Elisei Shafer, Oren Gal

Department of Marine Technologies, University of Haifa, Israel

Hierarchical RL Visuomotor Policy Learning Underwater Robotics Autonomous Underwater Navigation Robust RL

Ask PDF

Abstract

Pointer Networks

Explore similar work

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

Multi-Agent Off-Policy Deep Reinforcement Learning for Smart Campus Coverage

Towards End to End Motion Planning and Execution for Autonomous Underwater Vehicles Using Reinforcement Learning