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

arXiv: https://arxiv.org/abs/2603.28385 · HTML: https://mlsanity.com/paper/2603.28385/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL for robot navigation and UAV control, one of 15 directions in Deep reinforcement learning methods.
- Builds on 17 of its 83 references that are in the map.
- First posted on arXiv 30 Mar 2026.

## Placed in

- Deep reinforcement learning methods / [RL for robot navigation and UAV control](https://mlsanity.com/deeprl/rl-for-robot-navigation-and-uav-control/)

## Builds on (most cited first, 17 of 17)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [A Closer Look at Invalid Action Masking in Policy Gradient Algorithms](https://mlsanity.com/paper/2006.14171/) (2020)
- [Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2012.10638/) (2020)
- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)
- [Heterogeneous Attentions for Solving Pickup and Delivery Problem via Deep Reinforcement Learning](https://mlsanity.com/paper/2110.02634/) (2021)
- [Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/2110.02629/) (2021)
- [Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective](https://mlsanity.com/paper/2404.06492/) (2024)
- [Space-based Global Maritime Surveillance. Part I: Satellite Technologies](https://mlsanity.com/paper/2011.11304/) (2020)
- [Revisiting Boustrophedon Coverage Path Planning as a Generalized Traveling Salesman Problem](https://mlsanity.com/paper/1907.09224/) (2019)
- [Fields2Cover: An open-source coverage path planning library for unmanned agricultural vehicles](https://mlsanity.com/paper/2210.07838/) (2022)
- [Riverine Coverage with an Autonomous Surface Vehicle over Known Environments](https://mlsanity.com/paper/1908.02827/) (2019)

## Abstract (arXiv)

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.