cs.LGMar 30, 2026
SaveCritic-Free Deep Reinforcement Learning for Maritime Coverage Path Planning on Irregular Hexagonal Grids
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 ) | Cellular decomposition / sweep | ||||||
| Hex-based SAR / coverage optimization ( Cho et al., 2021b ; Cho et al., 2021a ; Kadioglu et al., 2019 ) | ✓ | Hex decomposition + MILP / graph optimization | |||||
| USV coastal bathymetric survey ( Zhao et al., 2024 ) | ✓ | Coastline approximation + evolutionary sequencing | |||||
| USV offshore bathymetric survey ( Zhao and Bai, 2024 ) | ✓ | Integer programming / hierarchical planning | |||||
| Multi-USV cooperative coverage ( Shen et al., 2025 ; Ma et al., 2026 ) | ✓ | Task allocation / cooperative game + FSM | |||||
| Grid-MDP maritime CPP with DRL ( Ai et al., 2021 ; Wu et al., 2024 ) | DRL over grid states |
Table 1: Positioning of representative approaches to maritime and graph-based coverage planning. ✓: explicitly addressed; : partially addressed or addressed under different assumptions; : not a primary focus.
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.
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 |
|---|---|---|---|
| Dense | Incentive per newly visited hexagonal cell. | ||
| Dense | Time-decayed priority bonus for early visitation of high-value zones (inactive in uniform-coverage experiments) . | ||
| Dense | Penalty proportional to normalized inter-cell distance. | ||
| Dense | Kinematic penalty for sharp heading changes, promoting smooth trajectories. | ||
| Episodic | Sparse reward for full coverage and return to base. | ||
| 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 |
| Model dimension | 128 | |
| Encoder layers | 3 | |
| Attention heads | 8 | |
| Decoder glimpses | 2 | |
| Rollouts per instance | 16 | |
| 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, …). |
| 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.
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 | |
| Feasibility | Exact_DFS | 100.0 | 100.0 | 0.0 | 0.0 |
| RL (ours) | RL-BoK16+2opt | 99.1 | 99.1 | 0.0 | 0.0 |
| RL-BoK16 | 98.6 | 98.6 | 0.0 | 0.0 | |
| RL-Greedy | 95.7 | 95.7 | 0.0 | 0.0 | |
| Heuristic | Warnsdorff | 46.0 | 46.0 | 0.0 | 0.0 |
| DFS_Backtrack | 33.8 | 100.0 | 3.2 | 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 (%) | HSR |
|---|---|---|
| Full (BFS + augmentation) | 98.1 | — |
| BFS dead-end detection | 24.8 | |
| geometric augmentation | 97.2 |
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 | Dist. | Turns | Steps | Revisits | |||
| RL | RL-BoK16+2opt | 991 | 3.100 | 0.314 | 34.1 | 5.3 | 37.8 | 0.0 |
| RL-BoK16 | 986 | 3.110 | 0.315 | 32.3 | 4.6 | 37.8 | 0.0 | |
| RL-Greedy | 957 | 3.111 | 0.314 | 32.9 | 4.9 | 37.8 | 0.0 | |
| Feasibility | Exact_DFS | 991 | 3.308 | 0.373 | 43.5 | 6.7 | 37.8 | 0.0 |
| Heuristic | Warnsdorff | 454 | 3.325 | 0.379 | 42.5 | 5.6 | 37.2 | 0.0 |
| DFS_Backtrack | 991 | 3.340 | 0.447 | 49.4 | 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). 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.
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. |
Table 9: Taxonomy of surveillance-related coverage, patrolling, and routing problems underpinning our CPP formulation on hexagonal grids.