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

这篇论文提出了一种基于**深度强化学习（DRL）的框架，用于解决不规则六边形网格上的海上覆盖路径规划（Maritime Coverage Path Planning, CPP）**问题。该研究旨在克服传统方法在处理复杂海岸线、岛屿和禁航区时的局限性，实现高效、实时的海上监视任务规划。

以下是该论文的详细技术总结：

1. 问题背景与挑战 (Problem Statement)

• 应用场景：海上监视任务（如搜救 SAR、环境监测、基础设施保护）需要在广阔且几何形状复杂的区域（AOI）内分配传感资产。
• 核心挑战：
  • 几何复杂性：真实的海上区域通常包含不规则海岸线、岛屿和禁航区，导致传统的“牛耕式”（Boustrophedon）扫描路径难以直接应用。
  • 传统方法的局限：基于几何分解的传统 CPP 方法在处理不规则区域时计算量大，且难以泛化；基于优化（如 MILP）的方法通常需要从零开始求解每个实例，缺乏实时重规划能力。
  • 路径约束：海上移动平台（如无人船 USV、无人机 UAV）受限于机动性（转向成本）和续航，需要生成平滑、短距离且无重复访问的路径。
• 目标：在包含障碍物的不规则六边形网格上，寻找一条能够覆盖所有目标单元格、起点和终点固定、且无重复访问（哈密顿路径）的最优路径。

2. 方法论 (Methodology)

2.1 问题建模

• 离散化表示：将海上区域建模为六边形网格（Hexagonal Grid）。六边形相比正方形网格具有各向同性更好、邻居距离相等的优势，能更自然地匹配传感器的圆形覆盖范围。
• 图论转化：将覆盖问题转化为图上的遍历问题。
  • 状态空间：包含当前节点、已访问节点掩码、静态图结构及动态环境信号（如覆盖率、可达性）。
  • 动作空间：选择下一个可行的未访问邻居节点。
  • 约束处理：使用**动态动作掩码（Dynamic Action Masking）**技术，在策略输出前屏蔽非法动作（如已访问节点、非邻居节点、死胡同），强制生成哈密顿路径。
• 奖励函数：设计包含密集奖励（每访问一个单元格的奖励、转向惩罚、距离惩罚）和稀疏奖励（完成任务奖励、死胡同惩罚）的复合奖励函数，以鼓励短路径和平滑转向。

2.2 核心算法架构

• 基于 Transformer 的 Pointer Policy：
  • 编码器：使用 Transformer 编码器处理图结构数据，生成节点嵌入（Node Embeddings）和全局图嵌入。
  • 解码器：自回归地生成下一个要访问的节点。利用注意力机制（Attention）结合当前状态、历史路径和环境信号来预测下一步动作。
  • 掩码机制：在 Softmax 之前应用加法掩码，确保生成的路径在拓扑上是可行的。
• 无 Critic 的组相对策略优化 (Critic-free GRPO)：
  • 痛点：传统的 Actor-Critic 方法（如 PPO）在组合优化问题中难以学习准确的价值函数（Value Function），导致训练不稳定。
  • 解决方案：采用 GRPO (Group-Relative Policy Optimization)。对于同一个问题实例，采样一组（Group）轨迹，通过比较组内轨迹的回报（Return）来计算优势函数（Advantage），而无需训练一个独立的 Critic 网络。
  • 优势：消除了价值函数估计的偏差和不稳定性，显著提高了长视距路由任务的训练稳定性。
• 早期死胡同检测 (Early Dead-end Detection)：
  • 引入广度优先搜索（BFS）进行可达性检查。如果当前动作导致剩余未访问节点或基地无法到达，立即终止该轨迹并施加惩罚。这加速了信用分配（Credit Assignment），防止智能体在注定失败的路径上浪费计算资源。

3. 主要贡献 (Key Contributions)

1. 问题形式化：首次将不规则海上区域的 CPP 问题形式化为六边形网格上的图遍历问题，并专注于最小化路径长度和转向次数，同时保证完全覆盖。
2. 算法创新：设计了一种基于 Transformer 的 Pointer Policy，结合动态掩码处理可变大小的 AOI 和任意障碍物配置。
3. 训练策略：将 GRPO 适配到 CPP 领域，证明了通过轨迹比较的无 Critic 学习能有效稳定长视距路由任务的训练。
4. 泛化能力：实证表明，单个学习到的策略能够泛化到未见过的几何形状，无需针对特定实例进行重新训练。

4. 实验结果 (Results)

实验在 1,000 个未见过的合成海上环境上进行，对比了 13 种经典启发式算法和最优解（DFS 作为可行性基准）。

• 哈密顿成功率 (HSR)：
  • RL 策略：在贪婪解码下达到 95.7%，结合 Best-of-16 采样和 2-opt 局部搜索后达到 99.0%。
  • 对比基线：表现最好的启发式算法（Warnsdorff）仅为 46.0%。其他传统扫描算法（如牛耕式）在严格无重复访问约束下成功率为 0%。
• 路径质量：
  • 路径长度：RL 生成的路径比最佳基线短 7%。
  • 转向次数：RL 生成的路径转向次数比最佳基线少 24%，显著提升了运动平滑度。
  • 重复访问：RL 策略在所有成功实例中实现了 0 次 节点重复访问，而传统启发式算法为了覆盖往往需要大量重复路径（平均 3-35 次）。
• 推理效率：
  • 在笔记本电脑 GPU (RTX 3070) 上，单次实例的推理时间（包括采样和 2-opt 优化）约为 32 毫秒。
  • 这证明了该方法满足海上自主系统实时重规划的需求（通常秒级或分钟级）。

5. 意义与未来展望 (Significance & Future Work)

• 实际意义：该研究证明了深度学习可以解决复杂的组合优化问题，特别是在具有严格几何约束的领域。其提出的无 Critic 训练方案为其他长视距路由问题提供了新的思路。
• 部署潜力：极低的推理延迟使其能够部署在边缘计算设备（如 NVIDIA Jetson）上，用于实时的海上监视任务规划。
• 局限性：
  • 目前仅针对均匀覆盖优先级，未考虑不同区域的重要性差异。
  • 实验基于合成数据，尚未在真实海图（含水深、洋流等复杂因素）上验证。
  • 目前为单智能体规划，多智能体协同尚未涉及。
• 未来方向：引入非均匀覆盖优先级、多平台协同规划、允许在特定预算下的有限重复访问，以及在真实海洋环境中的部署验证。

总结：这篇论文通过结合 Transformer 架构和创新的无 Critic GRPO 训练策略，成功解决了一个极具挑战性的海上路径规划问题，在成功率、路径质量和实时性方面均大幅超越了传统方法，为智能海上监视系统提供了强有力的技术支撑。