Coverage path planning for multi-AUV considering ocean currents and sonar performance

考虑洋流和声呐性能的多AUV覆盖路径规划

信息

• 作者: Xukai Mu, Wei Gao
• 单位: 中国海洋大学
• 期刊: Frontiers in Marine Science
• 发表日期: 2025年1月9日

---

1. 概述

1.1. 研究背景

自主水下航行器（AUV）是海洋工程中的重要工具，广泛应用于目标覆盖搜索、水下地形扫描、落水人员搜救等任务。在执行这些任务时，AUV需要利用声呐等传感器对目标区域进行完全覆盖，以确保任务成功。然而，现有的AUV覆盖路径规划（Coverage Path Planning, CPP）研究面临两大关键挑战：

1. 声呐性能受环境影响：AUV搭载的声呐，其探测性能极易受到海底地形等海洋环境因素的干扰。传统研究通常将声呐的探测范围简化为固定的圆形或扇形，忽略了在不平坦的海底，探测范围可能变为椭圆形甚至更复杂的形状，这种简化会影响路径规划的效率和覆盖的完整性。
2. 洋流对AUV动态的影响：洋流会显著改变AUV的运动状态和能耗，是路径规划中不可忽视的因素。在计算两点之间的最短时间路径时，必须考虑洋流的速度和方向。

因此，本文聚焦于解决静态目标的覆盖搜索问题，旨在提出一种新的多AUV协同路径规划方法，该方法能够同时考虑复杂海洋环境下声呐性能的动态变化以及洋流对AUV运动的影响，从而实现更高效、更均衡的任务分配与路径规划。

---

1.2. 研究贡献

本文的主要贡献可以总结为以下三点：

1. 提出更真实的声呐模型：不再假设声呐探测范围是固定不变的，而是创新性地结合了声学仿真软件（RAM）和声呐方程，根据不同位置的海底地形起伏来预测声呐的实际探测范围。这种方法能够更准确地确定任务覆盖所需的采样点，避免因模型过于简化而导致的冗余或遗漏。
2. 改进Dijkstra算法以适应洋流环境：针对洋流影响下大量采样点之间最短时间路径的计算问题，本文提出了一种改进的Dijkstra算法。该算法通过修改搜索策略和引入迭代概念，在保证结果精度的前提下，显著提升了在高密度网格地图中计算邻接矩阵的速度，其计算复杂度从传统Dijkstra算法的 $O(n^2)$ 降低到 $O(n^{3/2})$。
3. 创新的多AUV任务分配与路径规划框架：本文将粒子群优化（PSO）算法与ELKAI求解器相结合，用于解决多AUV的任务分配和单AUV的最优路径规划问题 。PSO算法负责寻找最优的任务区域划分方案，而ELKAI求解器则高效地计算每个AUV在其分配区域内的最短路径（NP-hard问题）。这种组合不仅确保了任务在多个AUV之间公平分配，还最小化了整体任务完成时间。

---

2. 问题定义

2.1. 基本假设

为了使问题可以被建模和求解，研究首先提出了一系列基本假设：

• 环境模型：
  • 地图模型：研究采用网格化方法对任务区域建模。每个网格都包含了具体的海底深度信息 $d(x,y)$ 和洋流信息 $\vec{v}(x,y)$ 。
  • 洋流模型：洋流数据从全局数据集中随机选取，并假设AUV在两个相邻网格间移动时，洋流的大小和方向是恒定的。
• AUV与传感器模型：
  • AUV性能：所有AUV的输出功率固定且性能相同。
  • 传感器模型：AUV搭载的是全向主动声呐。其探测性能只受海底地形影响。声呐在任意位置 $(x,y)$ 和任意水平方向 $\theta$ 的探测距离被表示为 $r(\theta ,x,y)$，这是一个随位置和方向动态变化的值，而非传统研究中假设的固定半径。为了简化路径规划，一个位置的最终有效探测范围被定义为该点在所有方向上最小探测距离所构成的方形区域。

2.2. 问题建模

论文将一个复杂的物理问题，通过分层定义的方式，清晰地转化为了一个包含覆盖优化和路径协同优化的多目标约束求解问题。

*图3：(a) 根据不同探测范围确定的采样点 (b) 多AUV任务分配与路径规划

• 层次1：确定采样点：如何在考虑声呐实际性能的情况下，用最少的探测区域完全覆盖整个任务区？假设任务区域为$P$，由 $k$ 个采样点的探测区域共同覆盖，这些采样点必须满足以下两个数学约束条件：
  • 约束一：完全覆盖：所有单个采样点 $P\_j$ 的探测区域的并集，必须等于整个目标任务区域 $P$：$$P_1\cup P_2\cup ...\cup P_k=P$$
  • 约束二：最小重叠：所有采样点探测区域之间的交集（即重叠部分）应该尽可能小：$$min(P_1\cap P_2\cap ...\cap P_k)$$

如图3(a)所示，蓝点代表根据上述两个约束条件确定的最终采样点。在地形平坦、声呐探测距离远的区域，采样点稀疏；反之，在地形复杂、探测距离近的区域，采样点密集。

• 层次2：多AUV任务分配与路径规划：如何将这些点合理地分配给n个AUV，并为每个AUV规划一条最优路径，从而使整个团队的作业时间最短？假设第 $i$ 个AUV的任务路径为 $L\_i$ (即它需要访问的采样点序列)，所有路径应满足以下四个数学约束条件：
  • 约束三：任务均衡：$|L\_i|$ 代表第 $i$ 个AUV的任务量（即路径总时长）。此公式要求分配给每个AUV的任务量应大致相等，确保所有AUV都能有效参与任务，避免部分AUV过早完成而空闲等待：$$|L_1|\approx |L_2|\approx ...\approx |L_n|$$
  • 约束四：最小化最大完工时间：这是整个路径规划问题的核心优化目标。团队完成所有任务的总时间取决于最后一个完成任务的AUV，因此，优化的目标是让所有AUV路径中耗时最长的那一条路径时间也尽可能短：$$min(max(|L_1|,|L_2|,...,|L_n|))$$
  • 约束五：无路径重叠：任意两个AUV的任务路径 $L\_m$ 和 $L\_k$ 之间不应有交集，确保每个采样点只被一个AUV访问，避免了重复工作，同时也降低了AUV之间发生碰撞的风险：$$L_m\cap L_k=\varnothing ,\forall m\ne k$$
  • 约束六：任务完整性：所有AUV的任务路径的并集，必须等于需要访问的全部采样点集合 $L$

如上图3(b)所示，不同颜色的路径代表分配给不同AUV的任务和路线。

---

3. 研究方法

图1：多AUV路径规划流程图

该研究提出了一套集成的算法流程，协同处理声呐性能、洋流影响和多AUV路径规划三大问题。其总体流程如图1所示，主要分为三个核心步骤。

3.1. 步骤一：基于声呐性能确定采样点

图4：确定采样点

这是路径规划的第一步，目标是根据声呐在不同环境下的实际表现来确定需要访问的最小点集。

• 声呐探测范围的计算：

  • 研究采用了主动声呐方程：$SL-2TL+TS-(NL-DI)=DT$（声源辐射声级SL、接收指向性指数DI、声源到目标的传输损耗TL、目标强度TS、时空处理器检测阈值DT、背景噪声级NL）在这个方程中，传输损耗TL是受环境（尤其是地形）影响最大的变量。
  • 利用专业的声学仿真软件RAM来计算不同地形下的传输损耗。
  • 为了得到一个稳定的传输损耗值，研究采用经验公式 $TL=a\lg r+\alpha r$ 对RAM的仿真数据进行拟合，从而估算出探测距离。(a和$\alpha$是环境相关的常系数)

• 采样点的生成过程：

  • 首先，对任务海域的海底地形进行分层，例如分为平坦和倾斜两种类型，以简化计算。
  • 针对每一种地形类型，使用上述方法计算出相应的声呐探测范围。
  • 根据不同区域的不同探测范围，生成能够完全覆盖整个任务区的采样点集。这样，在声呐探测距离远的海域（如平坦海底），采样点会更稀疏；在探测距离近的海域（如复杂地形），采样点会更密集，从而提高了效率(如图4)。

3.2. 步骤二：使用改进Dijkstra算法计算邻接矩阵

图5：改进的Dijkstra算法

在确定了所有采样点后，需要计算在洋流影响下，任意两点之间的最短通行时间，并将这些信息存储在一个邻接矩阵中，供后续任务分配使用。

• 传统Dijkstra算法的局限：在处理大量采样点时，其 $O(n^2)$ 的时间复杂度导致计算效率低下。
• 改进Dijkstra算法的核心思想（图5）：
  • 并行更新：该算法不再是每次只扩展一个距离起点最近的节点，而是在每一步中同时向外扩展一“环”，一次性更新所有新扩展环上的网格点的值。这极大地加快了搜索速度。
  • 迭代修正：为了解决并行更新可能带来的精度损失，算法引入了迭代机制。它会基于上一轮迭代的结果，重新从起点开始逐步计算，直到所有网格的值不再变化为止，从而确保了结果的准确性。
  • 效率提升：实验证明，该改进算法在计算速度上远超传统Dijkstra算法（例如，在一个案例中，用时85.19秒，而传统算法需要2042.24秒）。

3.3. 步骤三：结合PSO与ELKAI实现多AUV任务分配和路径规划

这是整个方法的核心，通过迭代优化实现任务的均衡分配和路径的最优化。

• 使用PSO进行任务分配：

  • 该研究将多AUV任务分配问题建模为一个优化问题。在PSO算法中，每一个“粒子”都代表一种任务分配方案。
  • 一个粒子包含多个维度，每个维度代表一条从中心点发出的射线，这些射线将整个任务区域分割成多个子区域，每个子区域分配给一个AUV。通过PSO算法的迭代，这些射线的角度会不断调整，以寻找最优的区域划分方式。

• 使用ELKAI求解器规划单AUV路径：

  • 当PSO给出一个任务分配方案后，需要计算每个AUV完成其任务所需的最短时间。这本质上是一个旅行商问题（TSP）。
  • 研究引入了ELKAI求解器，这是一个高效的TSP问题求解工具，能够为最多315个点的中等规模问题找到最优解，完全满足AUV单次任务的续航限制。
  • ELKAI计算出的路径时间（即任务时长）将作为评估该粒子（分配方案）优劣的“适应度值”，反馈给PSO算法。

• 迭代优化：PSO算法根据ELKAI反馈的适应度值，不断调整粒子群，寻找能使即整体任务时间最短的分配方案。这个“PSO分配-ELKAI求解”的循环不断进行，直至收敛，最终得到均衡且高效的多AUV协同路径规划方案。

---

4. 实验

为了验证所提方法的有效性，论文设计了两个部分的仿真实验。实验代码分别在MATLAB（声学模拟和改进Dijkstra）和PyCharm（PSO与ELKAI）环境中运行。

4.1. 第一部分：验证考虑声呐性能的重要性

该部分通过对比“考虑声呐性能”和“不考虑声呐性能（即假设探测半径固定）”两种情况下生成的路径，来证明前者的优越性。

• 仿真1（图6）：
  • 环境：一个包含浅海区（100-130m）和深海区（160-200m）的真实海域。
  • 结果：考虑声呐性能后，估算的探测距离在浅水区（2.25km）大于深水区（1.35km），生成的采样点更合理（图6c）。最终规划的路径时长为80.275小时，相比于固定探测距离所需的97.4小时（图6d表示的是原始固定探测范围内覆盖整个区域所需的采样点），节省了21.3%的时间。

• 仿真2（图8）：

  • 环境：一个地形变化更剧烈（深度从150m到450m）的海域。
  • 结果：路径时长从147.3小时减少到104.2小时，节省了29.3%的时间 。

• 结论：在海底地形变化越大的区域，考虑声呐性能带来的优化效果越显著。

4.2. 第二部分：验证多AUV路径规划方法的有效性

该部分将本文提出的方法（简称为PSO）与混合遗传算法（GA）和聚类算法（Clustering）进行对比。评估指标主要有两个：最大任务时间（团队完成任务的总时长）和任务时间差（衡量任务分配的均衡性）。

• 仿真3（3个AUV（图9，表1））：

  • 结果：PSO方法的任务时长最长为28.0小时，任务时间差仅为3.7%。而GA和Clustering方法的最长任务时间分别为34.3小时和34.1小时，任务时间差也远大于PSO方法。这表明PSO方法在任务时长和均衡性上均占优。

• 仿真4（3个AUV，区域更大（图10，表2））：
  • 结果：PSO方法继续保持优势，最长任务时间为219.9小时，时间差为1.2%。GA和Clustering方法的结果则显著差于PSO。

• 仿真5（4个AUV（图11，表3））：
  • 目的：测试算法在AUV数量增加时的鲁棒性。
  • 结果：PSO方法的优势更加明显。其任务时间差为2.2%，而GA和Clustering算法的任务时间差急剧增大到40.2%和58.3%，显示出这两种方法在处理更复杂协同问题时的局限性。

• 随机场景统计实验（仿真6和7（图12））：

  • 目的：在30个随机生成的场景下进一步验证算法的鲁棒性。
  • 结果：无论是在3个AUV还是4个AUV的随机测试中，PSO方法的最大任务时间和任务时间差都稳定地优于其他两种对比方法，证明了其普适性和可靠性。

• 实验总结：

  • (1) PSO与ELKAI的结合实现了更均衡的任务分配，保证了多AUV的高效利用;
  • (2) PSO与ELKAI的结合始终保证了最大任务时间小于其他方法，使得多AUV覆盖任务的完成领先于其他两种方法;
  • (3) PSO算法与ELKAI的结合在处理多AUV和大量目标点时更为明显，表明该方法具有更广泛的应用范围。

---

5. 结论、限制与未来方向

结论

1. 考虑声呐性能是必要的：将随环境变化的声呐性能纳入路径规划，能有效减少冗余的采样点，从而显著缩短任务时间。
2. 改进的Dijkstra算法：该算法在处理洋流影响下的路径计算问题时，速度远快于传统算法，且能保证结果的准确性。
3. PSO与ELKAI的结合：该组合方法在多AUV任务分配和路径规划中，能够实现更均衡的任务划分和更短的整体任务时间，尤其是在处理大规模、多智能体问题时，其鲁棒性远超传统的遗传算法和聚类方法。

限制：该方法在采样点数量较少或AUV数量特别多的极端情况下可能不适用。这可能是因为PSO在低维空间或极高维空间中优化效果不佳，或者任务过于简单/复杂，导致其优势无法体现。

未来方向
未来的研究将致力于扩展方法的适用范围，使其能够更好地应对更广泛的场景，解决当前存在的局限性。