🤖 machine learning

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

This paper proposes a critic-free Deep Reinforcement Learning framework using Group-Relative Policy Optimization and a Transformer-based pointer policy to solve maritime coverage path planning on irregular hexagonal grids, achieving superior path efficiency and near-perfect success rates compared to traditional heuristics while enabling real-time on-board deployment.

Original authors: Carlos S. Sepúlveda, Gonzalo A. Ruz

Published 2026-03-31

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Carlos S. Sepúlveda, Gonzalo A. Ruz

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the captain of a high-tech drone boat. Your mission? To patrol a vast, messy patch of ocean. This isn't a perfect square swimming pool; it's a jagged coastline full of islands, hidden reefs, and "no-go" zones. You need to fly over every single square inch of this water to look for lost ships, pollution, or smugglers, but you have limited fuel and can't crash into the islands.

This is the problem of Maritime Coverage Path Planning.

For decades, computers tried to solve this by breaking the ocean into a grid of squares (like a checkerboard) and drawing lines back and forth, like a lawnmower. But when the coastline is jagged or there are islands in the middle, this "lawnmower" approach gets stuck. It forces the boat to make sharp, fuel-wasting 180-degree turns, or worse, it gets trapped in a narrow channel and can't get out to finish the job.

This paper introduces a new, smarter way to solve this using Deep Reinforcement Learning (DRL). Think of it as teaching a computer to "intuit" the best path, rather than just following a rigid rulebook.

Here is a simple breakdown of how they did it:

1. The Map: Switching from Squares to Honeycombs

Most maps use square grids. But squares have a problem: the corners are farther away than the sides. If you are a boat, moving diagonally across a square is harder and longer than moving straight.

The authors switched to a Hexagonal Grid (a honeycomb pattern).

The Analogy: Imagine a honeycomb. Every cell has 6 neighbors, and they are all the exact same distance away. It's the most "fair" shape for movement. It removes the bias of "diagonals are weird" and makes the math of moving around islands much smoother.

2. The Brain: A Transformer "Pointer"

Instead of calculating every possible route (which takes forever), they built an AI brain based on a Transformer (the same technology behind chatbots like me).

The Analogy: Imagine a tour guide looking at a map of the honeycomb. Instead of guessing, the guide has a "pointer" that looks at all the neighboring cells. It asks, "If I go here, can I still finish the tour later?"
The AI doesn't just pick a random spot; it learns a policy. It's like a seasoned sailor who has seen thousands of maps and knows, "If I go left now, I might get trapped in a dead-end later, so I'll go right instead."

3. The Training: Learning Without a "Critic"

Usually, when you train an AI, you have a "Teacher" (called a Critic) that watches the AI and says, "Good job!" or "Bad job!" based on a score. But in complex routing, it's very hard for a teacher to know the score until the very end of the trip. This makes learning slow and unstable.

The authors used a clever trick called Critic-Free Group-Relative Policy Optimization (GRPO).

The Analogy: Imagine a cooking competition. Instead of having one judge taste the food at the end, you ask 16 chefs to cook the same dish at the same time. You then compare them to each other.
- "Chef A's dish is better than Chef B's."
- "Chef C's dish is the worst."
The AI learns by comparing its own attempts against its peers on the same map. It doesn't need an external judge; it just needs to know, "Did I do better than my other 15 tries?" This makes learning much faster and more stable.

4. The Safety Net: The "Dead-End" Detector

On a jagged map with islands, it's easy to make a mistake that traps you in a corner where you can't reach the rest of the ocean.

The Analogy: Imagine playing a maze game. If you take a turn and realize you've entered a dead-end alley with no exit, you don't want to keep walking until you hit the wall. You want to know immediately that you made a mistake.
The AI has a built-in "BFS" (Breadth-First Search) detector. Before it even finishes a step, it simulates: "If I go here, can I still reach the exit?" If the answer is no, it stops the attempt instantly and learns, "Don't go that way!" This saves time and teaches the AI faster.

The Results: Why It Matters

The team tested this on 1,000 different, never-before-seen ocean maps. Here is what happened:

Success Rate: The old "lawnmower" methods and standard math tricks got stuck or failed to cover the whole area about 54% of the time. The new AI succeeded 99% of the time.
Efficiency: The AI's paths were 7% shorter and had 24% fewer sharp turns than the best traditional methods.
- Why this matters: Fewer turns mean less fuel burned and less wear and tear on the boat's engine.
Speed: The AI can plan a route for a complex map in 32 milliseconds. That's faster than a human can blink. It's fast enough to be installed on a real boat and used while the boat is moving.

The Bottom Line

This paper shows that we can teach computers to navigate messy, real-world oceans much better than we ever could with old math formulas. By using a honeycomb map, a smart "pointer" brain, and a "compare-yourself-to-peers" training method, we can get autonomous boats to patrol the seas efficiently, safely, and without getting lost. It's a huge step toward having a fleet of smart, self-driving ships that can protect our oceans 24/7.

1. Problem Definition

The paper addresses Maritime Coverage Path Planning (CPP) for surveillance missions (e.g., search and rescue, environmental monitoring) over vast, geometrically complex areas.

Core Challenge: Traditional CPP methods rely on geometric decomposition (e.g., boustrophedon sweeps) which struggle with irregular coastlines, islands, and exclusion zones. These methods often require computationally expensive re-planning for every new mission instance and produce inefficient paths with excessive turns and redundant motion.
Formulation: The authors model the Area of Interest (AOI) as a planar polygon with holes (obstacles). They discretize this area using a hexagonal grid where the cell size matches the sensor's footprint radius.
Objective: The goal is to find a Hamiltonian path (a path visiting every cell exactly once) that minimizes total path length and heading changes (turns) while ensuring complete coverage. This is framed as a constrained graph traversal problem on an irregular graph with obstacles.
Constraints:
- Strict Single-Visit: The agent cannot revisit nodes (unlike classical heuristics that backtrack).
- Kinematic Costs: The reward function penalizes sharp turns to reflect the inertia and maneuvering costs of maritime vessels.
- Dead-Ends: Irregular topologies can create geometric dead-ends where the agent gets trapped, making the problem significantly harder than standard Traveling Salesman Problems (TSP).

2. Methodology

The proposed solution is a Deep Reinforcement Learning (DRL) framework combining Neural Combinatorial Optimization (NCO) with a novel training scheme.

A. Graph Representation

Hexagonal Tessellation: The AOI is converted into a graph $G=(V, E)$ where nodes are cell centroids and edges represent valid transitions between adjacent cells.
State Space: The state includes the current node, a binary mask of visited nodes, and static instance data (graph structure, node priorities).
Action Space: The agent selects the next unvisited neighbor. Feasibility masking is strictly applied to prevent invalid moves (non-neighbors or already visited nodes) and to prevent early return to the base before full coverage.

B. Neural Architecture

Transformer-Based Pointer Policy:
- Encoder: A multi-layer Transformer processes the graph using k-hop neighborhood attention (restricted to the 6 neighbors of a hex cell) to generate contextual node embeddings.
- Decoder: An autoregressive decoder constructs the tour step-by-step. It uses a pointer mechanism (additive attention) to select the next node.
- Context Signals: The decoder incorporates dynamic signals such as heading direction, coverage progress, and reachability status to guide decision-making.

C. Training Scheme: Critic-Free GRPO

A key innovation is the use of Group-Relative Policy Optimization (GRPO) without a value function (critic).

Motivation: Learning a value function for combinatorial problems with sparse rewards (only at the end of the mission) is unstable and prone to bias.
Mechanism: For each training instance, the policy samples a group of $G$ trajectories. Advantages are estimated by comparing the returns of these trajectories within the same instance (standardizing returns across the group).
Benefit: This eliminates the need for a separate critic network, stabilizing training for long-horizon routing tasks.
Dead-End Detection: A Breadth-First Search (BFS) lookahead is integrated into the environment. If a move leads to a state where remaining nodes or the base become unreachable, the episode terminates immediately with a penalty. This provides sharper credit assignment, preventing the agent from learning from "doomed" trajectories.

3. Key Contributions

Problem Formulation: Defined maritime CPP on irregular hexagonal grids as a strict Hamiltonian path problem, addressing the specific challenges of sparse feasibility and kinematic costs.
Critic-Free Training: Adapted GRPO to the CPP domain, demonstrating that trajectory comparison within an instance effectively stabilizes training without a value function.
Transformer Pointer Policy: Designed a graph-aware Transformer policy with dynamic action masking that handles variable-sized AOIs and arbitrary obstacle configurations.
Generalization: Demonstrated that a single policy trained on synthetic data generalizes to unseen geometries without instance-specific retraining.

4. Experimental Results

The method was evaluated on 1,000 unseen synthetic maritime environments against 13 classical heuristics (including Boustrophedon, Spanning Tree Coverage, and Warnsdorff's rule).

Success Rate (Hamiltonian Success Rate - HSR):
- Proposed RL (RL-BoK16+2opt): 99.0% success rate.
- Best Heuristic (Warnsdorff): 46.0% success rate.
- Other Heuristics: Most classical sweep methods achieved 0% HSR because they rely on revisiting nodes or backtracking, which violates the strict Hamiltonian constraint.
Path Quality (on common solved instances):
- Path Length: The RL policy produced paths 7% shorter than the best comparable baseline.
- Heading Changes: The RL policy reduced turns by 24% compared to the closest baseline, resulting in smoother, more kinematically feasible trajectories for ships.
- Revisits: The RL policy achieved 0 revisits by design, whereas successful classical heuristics required significant redundant motion (3 to 35 revisits on average).
Inference Latency:
- All three inference modes (Greedy, Best-of-16 sampling, and Best-of-16 + 2-opt refinement) operate in < 50 ms per instance on a laptop GPU.
- This confirms feasibility for real-time, on-board deployment on autonomous maritime vehicles.

5. Significance and Impact

Paradigm Shift: The paper moves maritime CPP from geometric decomposition (which fails on complex shapes) to learning-based combinatorial optimization, enabling robust planning in highly irregular environments.
Operational Efficiency: By eliminating redundant revisits and reducing sharp turns, the method significantly saves fuel and extends mission endurance for Unmanned Surface Vehicles (USVs) and UAVs.
Real-Time Viability: The sub-50ms inference time proves that complex, non-linear path planning can be executed on edge devices, a critical requirement for autonomous maritime operations.
Scalability: The approach scales to complex topologies (bottlenecks, peninsulas) where traditional exact solvers (MILP) or heuristics fail to find feasible solutions.

In conclusion, this work presents a state-of-the-art solution for maritime surveillance that outperforms classical methods in both feasibility and efficiency, offering a practical, real-time tool for next-generation autonomous maritime systems.