团队科研成果分享-52

研究背景

多USV区域覆盖路径规划（Multi-USV Coverage Path Planning, MCPP）是海洋环境监测与数据采集中一个重要问题，其路径规划策略直接影响任务的覆盖率、执行时间和能耗效率。传统的启发式算法和多智能体路径规划框架在具有复杂海洋动力学（如均匀流、涡旋流和波浪）的环境下存在一定的局限性，比如难以适应动态流场变化、缺乏全局最优性以及计算效率低下。传统算法通常依赖静态环境假设，难以在动态、多目标约束的条件下保持性能稳定。因此，需要一种能够感知并适应复杂流场特征的智能决策方法来克服这些问题。本文提出了一种基于空间图注意力网络的多智能体注意力评论家算法（SGMAAC），旨在解决多USV在复杂流场中的高效覆盖与任务负载均衡问题。该算法利用空间图注意力机制捕捉非欧几里得空间结构信息，并结合算子池实现多类型局部搜索算子的动态选择来提高规划灵活性。通过集中训练与分散执行框架，该算法有效提升了覆盖率，降低了任务完工时间，并在多变流场条件下保持较高的鲁棒性。

关键技术

本文利用空间图注意力网络（Spatial Graph Attention Network, SpGAT）与多类型算子池（Operator Pooling）技术，通过集中训练与分散执行（CTDE）框架，以提高多USV覆盖路径规划的覆盖率和任务负载均衡性。具体来说，算法首先利用 SpGAT 捕捉多USV在非欧几里得空间中的局部与全局结构信息，建模邻近USV之间的时空依赖关系，并生成高质量状态表示。这种基于注意力机制的特征提取能够自适应地聚焦于关键节点与重要连接。随后，算法引入包含多步生长算子、多步去重算子与交换算子的算子池，通过策略网络动态选择适合当前局部状态的算子以优化覆盖路径。根据多目标奖励函数与集中式评论家网络的协同作用，实现了覆盖率与任务效率的平衡，提高了在复杂流场下的鲁棒性与计算效率。

该方法的创新和贡献如下：

1）提出了SGMAAC路径规划框架，通过自适应地融合空间和任务特征，使多USV能够在海洋环境中动态地平衡路径规划和任务效率；

2）提出了基于SpGAT的状态建模方法，有效捕捉多USV在非欧几里得空间中的关键结构信息；

3）设计了多类型算子池，实现局部路径优化算子的动态选择，提高规划灵活性与全局最优性。

算法介绍

（1）问题描述

本文探讨了复杂海洋环境下的多USV覆盖路径规划问题。研究旨在提升覆盖率、降低任务完工时间问题，通过空间图注意力机制与多类型算子池实现路径优化与任务负载均衡。图1展示了多USV覆盖路径规划系统模型：包含海洋流场模型、USV运动模型、能耗模型及多智能体决策框架。图中海洋流场由Navier–Stokes方程建模，可生成均匀流与涡旋流结构；USV运动模型刻画了推进、舵面控制与流场干扰对运动轨迹的影响；能耗模型量化了克服水动力阻力所需的推进能量；多智能体决策框架采用集中训练与分散执行模式，结合空间图注意力网络与算子池，实现对复杂动态环境的感知与路径优化。

图1 多USV覆盖路径规划环境

（2）基于网格图的MCPP实例

图2 基于网格图的MCPP实例：白色方块、黑色圆圈和红色星号分别代表地形图顶点、分解图顶点以及USV的初始顶点。实线和虚线分别表示覆盖路径和生成边。

图2展示了基于网格图的多USV覆盖路径规划中，SGMAAC框架将海域离散为图，结合时空变流场和局部障碍建模，通过SpGAT提取非欧几何特征，并在actor network中融合多智能体注意力与多步算子池决策，实现覆盖效率与负载均衡的动态权衡。其中算子选择评分函数为：

用于在路径代价与完工时间（makespan）间调节优化方向，多目标奖励函数引导策略在碰撞惩罚实现碰撞规避与覆盖效率的平衡；通过CTDE训练、部署时仅使用Actor推理，SGMAAC在保持实时性的同时，显著提升了大规模水域下的覆盖率、路径效率与任务均衡性。

（3）系统模型

图3  SGMAAC框架

图3展示了基于SGMAAC算法的多USV覆盖路径规划系统框架。首先，海洋流场模型基于Navier–Stokes方程生成均匀流与涡旋流，并将流速矢量场输入至USV运动模型，用于模拟复杂动态水域对USV航行的影响，即实现环境感知与动力学耦合建模。接着，通过SpGAT对多USV状态信息进行编码，即利用多头注意力机制捕捉局部与全局的非欧几里得空间特征，实现多智能体之间的高效信息交互与状态表示。此外，图中算子池模块包含多步生长算子、多步去重算子与交换算子，用于在策略网络决策下执行局部路径优化；集中式评论家网络则结合全局信息评估动作质量，从而提升覆盖率、降低完工时间并实现任务负载均衡。

关键要素：顺序决策问题的三个关键要素：状态空间、动作空间和奖励函数。

1）状态空间：在时间步t，第i个USV的观测状态表示为：

其中，p_it表示USV_i的坐标，n_it表示当前解中的顶点数量，ω_it表示当前解的总权重。

2）动作空间：SGMAAC采用离散动作空间，由算子池A_t构成：

其中，op_g、op_de和op_ex分别表示多步增长运算符、多步去重运算符和交换运算符。交换运算符是通过在子图之间动态交换拓扑元素，利用图论特性，通过结构优化来提高路径规划效率，通过自适应资源分配来平衡路径间的负载分布，并通过冲突检测机制来消除冗余。

    图3 多步生长算子及其执     图4 多步去重算子及其执

行后的覆盖路径示例图。     行后的覆盖路径示例图

3）奖励设计：为实现覆盖率最大化、任务完成时间最小化及负载均衡的多目标优化，奖励函数设计为：

其中，R_cw、R_C和R_E分别表示覆盖权重奖励、碰撞惩罚和能耗。

R_cw的目标是接近完整的覆盖路径规划，而累积奖励由以下公式给出：

其中w_i表示在时间t时USV_i已覆盖区域的总权重。

RC的目标是避免发生碰撞。一旦发生碰撞，将被扣10分。累计罚分的计算方式如下：

其中N_C_{i,t}表示USV_i在时间t是否发生碰撞。

R_E目标是降低USV的能耗。通常，较低的能耗会减少负奖励，从而激励USV选择更节能的运行轨迹。累积能耗由以下公式给出：

其中，E_{total, i }表示USV_i克服阻力所消耗的能量。

实验结果

（1）仿真参数设置

图5展示了区域覆盖Mcpp实例图；表1展示了Mcpp实例的设置；表2展示了环境参数；表3展示了SGMAAC框架的超参数。

图5 Mcpp实例展示图

表1 Mcpp实例

表2 环境参数

表3 超参数设置

对比算法：1）MSTC*, 2）MFC, 3）MIP , 4）ESTC, 5）MAPPO, 6）MASAC, 7）MAAC, 8）MADDPG。

性能评价指标：

1）Makespan（完工时间）：所有USV完成覆盖任务所需的总时间，取各智能体任务完成时间的最大值，反映任务调度与路径规划的效率。

2）Path Cost（路径代价）：所有USV执行路径的总路径代价，直接反映路径规划的经济性与节能性。

3）Task Load Balancing（任务负载均衡性）：衡量不同USV之间任务分配的均衡程度，通常使用标准差或方差来刻画，反映多智能体协作效率。

4）Convergence Reward（收敛奖励）：在训练阶段的收敛性能指标，综合体现策略网络在多目标奖励下达到稳定高性能策略的速度与效果。

（2）仿真结果与分析

图6 强化学习对比试验

如图6所示的训练结果表明，SGMAAC在最快收敛点和最大奖励值指标上均展现出更优的性能表现。具体而言，SGMAAC在episodes=1100时收敛至741.51，相较于其他多智能体强化学习框架显著提前了收敛时间。其他框架分别在episodes=1324、1383、837和1482时收敛至659.73、620.66、629.14和570.04。此外，SGMAAC依旧呈现出稳定的上升趋势，显示出优异的稳定性及持续优化能力。这一性能表现的主要原因在于，SGMAAC通过采用SpGAT技术有效捕捉非欧几里得空间特征，并结合算子池化技术。这种组合显著提升了决策精度，同时优化了路径规划性能。

表4–表8展示了SGMAAC框架在不同环境规模、动态流场条件及算子参数设置下均表现出较高的覆盖率、更短的完工时间、更低的路径代价及更优的任务负载均衡性，且在训练过程中保持了较快的收敛速度和稳定性。主要原因在于：（1）基于 SpGAT 的特征提取能够有效捕捉非欧几何空间结构信息；（2）多智能体注意力机制提升了全局信息融合与协同决策能力；（3）多步算子池为路径优化提供了灵活的局部搜索策略；（4）多目标奖励函数在覆盖率、效率与安全性之间实现了平衡。此外，固定碰撞惩罚有助于在规避碰撞的同时避免过度保守的路径规划；在 CTDE（集中训练、分散执行）框架下，SGMAAC 部署阶段仅需执行 Actor 网络，显著降低了推理计算负担；多场景实验结果进一步验证了该框架在大规模复杂海洋环境下的泛化能力与鲁棒性。

表4 USV完成覆盖任务所需的总时间

表5 不同算法的计算耗时

表6 USV执行路径的总路径代价

表7 USV之间任务分配的均衡程度

表8 不同环境规模下算法的可扩展性

总结

本研究探讨了多USV区域覆盖路径规划问题，目标是最大化覆盖范围、最小化时间跨度和提高决策效率。为此，我们提出了基于SpGAT和新型算子池的SGMAAC框架。SGMAAC框架通过基于SpGAT的非欧几里得特征提取和多步算子（包括增长、去重和交换算子）的动态选择，实现了复杂环境中的智能决策。实验结果证实，在不同的水生场景中，该算法具有显著优势。

尽管结合了动态洋流，但目前的评估依赖于基于网格的基准，限制了环境的真实性。未来的工作将把SGMAAC扩展到珊瑚礁和浅滩等更多不同的海洋条件中，以增强鲁棒性。此外，提高计算可扩展性和开发高能效路径规划策略将是优先事项，以满足实时和可持续多USV运行的需求。