水库库容无人船自动巡航路径规划算法与仿真实验

摘 要：该文主要探究水库库容无人船自动巡航最短路径的规划算法，并对算法应用效果进行仿真验证。使用模拟退火算法可以基于补测点寻找最短路径，但是循环次数较多、耗时较长;通过补测点聚类处理，将补测点分成若干点簇后再次寻找最短路径，耗时明显变短，但是仍然存在不同点簇之间路径差值较大的问题。使用点簇调整算法后，保证不同点簇之间的最短路径相近，达到降低能耗和提高效率的目的。仿真结果表明，在点簇调整后，3个点簇最短路径的差值从70 398.48 m变为15 356.29 m，在多艘无人船自动巡航路径规划中达到能耗均衡、精度较高的效果。

关键词：无人船;自动巡航路径规划;模拟退火算法;聚类算法;最短路径

中图分类号：U664.82 文献标志码：A 文章编号：2095-2945（2024）30-0012-04

Abstract： This paper mainly explores the shortest path planning algorithm for automatic cruising of unmanned ships in reservoir storage capacity， and carries out simulation verification to the application effect of the algorithm. Using the simulated annealing algorithm， the shortest path can be found based on the supplementary measurement points， but the number of cycles is large and the time is long. Through the supplementary measurement point clustering process， the supplementary measurement points are divided into several point clusters and then the shortest path is found again， which takes a significantly shorter time. However， there is still a problem of large path differences between different point clusters. After using the point cluster adjustment algorithm， the shortest paths between different point clusters are ensured to be similar， achieving the purposes of reducing energy consumption and improving efficiency. The simulation results show that after the adjustment of the point clusters， the difference between the shortest paths among the three point clusters changes from 70 398.48 m to 15 356.29 m， which achieves balanced energy consumption and high accuracy in the automatic cruise path planning of multiple unmanned ships.

Keywords： unmanned ship; automatic cruise path planning; simulated annealing algorithm; clustering algorithm; shortest path

水库库容的精确测算对提高水库蓄洪能力、保障水库安全有积极帮助。无人船在水库库容计算中具有自动化程度和测算精度高的优势，尤其适用于大中型水库的库容测算。无人船的自动巡航路径规划不仅决定了测算精度，而且与测算效率、测算成本也有密切关系。使用智能优化算法规划最短的巡航路径，保证无人船在续航范围内一次性完成测算任务。基于此，探究无人船自动巡航最短路径的规划算法成为影响无人船应用效果的决定因素。

1 水库库容无人船自动巡航路径规划算法

1.1 模拟退火算法

为了进一步提高无人船的巡航效率，需要获取补测点集的位置分布并计算无人船经过所有补测点时的最短路径。传统的数学求解最短路径随着补测点数量的增加，解算难度会显著提升，计算精度也会下降。随着人工智能技术的发展，基于智能优化算法的自动巡航路径规划具有精度更高、速度更快等优势，因此得到了广泛应用。常用的智能优化算法有遗传算法（GA）、蚁群算法（ACO）和模拟退火算法（SA）等[1]。其中，模拟退火算法具有鲁棒性强、通用性好、计算速度快等特点，本文选择该算法进行水库库容无人船自动巡航路径规划。该算法的路径搜索过程如图1所示。

结合图1，从补测点集Vs中随机抽取一个点（假设为B点），计算此时的路程长度。计算结束后，随机交换B点与Vs中其他某个点（假设为C点）的访问顺序，来到了C点这个局部极值点形成的“陷阱”。为了跳出该陷阱，系统会基于Metropolis准则寻找一个比当前路径更长的解，从C点跳至D点。假设系统存在i和j 2种状态，Ei和Ej分别为2种状态下的能量（能量的高低与路径的长短正相关），T为系统温度。则系统从状态i转换为状态j的概率P可通过下式求得

， （1）

式中：ΔE为Ei与Ej的差值。经过计算后，如果系统新状态j的能量要低于原状态i，则将系统状态更新为j;反之，如果新状态j的能量高于原状态i，则降低系统温度，并重新计算和对比降低温度后系统状态与原状态的能量，直到系统温度有最低值，即系统能量最小。在模拟退火算法中，能量与路径相关，当系统能量有最小值时，说明路径长度最短，从而获取了最短路径[2]。该算法流程如图2所示。

1.2 基于能耗均衡的无人船自动巡航路径规划算法

相比于数学计算，使用模拟退火算法能缩短无人船自动搜索最短路径的用时，但是当水库的库容较大时，由于补测点数量较多，仍然要花费较多的时间才能搜寻到较好的路径。基于此，本文提出了一种基于能耗均衡的多无人船自动巡航路径规划算法。其原理是：通过聚类处理，将距离较为靠近的若干个补测点划分到同一个点簇内，然后在点簇内搜索最短路径。由于点簇内的补测点数量相对较少，可以缩短获取最短巡航路径的用时。同时，将补测任务平均分配给多艘无人船，每艘无人船分别完成一个点簇的路径规划任务，通过并行处理的方式在保证能耗均衡的前提下提升了补测效率[3]。

在多艘无人船的自动巡航路径算法中，补测点的聚类处理是核心步骤。目前常用的聚类算法有层次聚类、划分聚类、密度聚类等若干种。划分聚类算法具有时空复杂度低、可识别形状多、抗噪声性能好等优势，适合本文的研究需求，因此选取划分聚类算法。如图3所示，该区域内分布有49个补测点，使用划分聚类算法将49个补测点分成3个点簇，并计算各个点簇的最短路径。点簇0的最短路径为12 967.89 m，点簇1的最短路径为12 920.51 m，点簇2的最短路径为8 147.29 m。

如图3所示，基于聚类处理的最短路径搜索虽然缩短了用时，但是不同点簇的路径存在较为明显的差异。假设将3个点簇的路径规划任务分别派发给A（点簇0）、B（点簇1）、C（点簇2）三条无人船，那么当C船完成点簇2的路径规划任务后，还需要等待A船和B船，浪费了较多时间，无法保证多艘无人船的能耗均衡。在实际应用中，会出现有些无人船提前完成任务，还有些无人船因为路径过程、巡航不足而无法完成任务的情况[4]。为了解决此类问题，本文提出了一种通过微调点簇、平衡点簇间路径长度差距的方法。

假设补测点集合为V={v1，v2，…，vn}，使用划分聚类算法对V进行聚类处理后，得到了k个点簇，点簇表示为C={c1，c2，…，cn}。L={l1，l2，…，ln}表示点簇对应的路径最短长度。任意一个点簇Ci中需要调整的点数ni可通过下式求得

式中：l0表示点簇内平均路径长度。还是以图3为例，已知该图中包含3个点簇，计算出3个点簇的路径平均长度（12 967.89+12 920.51+8 147.29）/3=11 345.23 m。根据式（2）可以求得3个点簇需要调整的点数n，n值取整。点簇0的n0=round（2.28）=2，n1=round（2.22）=2，n3=round（-4.51）=-5。由此可得，点簇2需要从点簇0和点簇1中挑选5个距离它最近的补测点，如图4中虚线椭圆所示。

点簇1去掉5个补测点后，n1值从2变为了-3，因此点簇1需要从点簇0中挑选2个补测点（图4）。经过调整后，3个点簇的路径长度变成了11 084.59 m、12 233.58 m、10 772.38 m，最大差值为1 461.2 m;相比于处理前的4 820.6 m有了明显的缩小，实现了多艘无人船的能耗均衡。

2 水库库容无人船自动巡航路径规划的仿真实验

2.1 仿真数据的获取与处理

为了验证本文设计的无人船自动巡航路径规划算法的应用效果，选择美国国家海洋和大气管理局（NOAA）提供的湖泊公开数据设计了仿真实验。选取600万个测深采样点数据，计算出该水库的库容值[5]。库容计算方法如下：假设水平面的高度为0 m，将湖泊划分成若干个条状栅格。从第i个栅格中选择A、B、C、D四个采样点，得到以栅格为底、以4个采样点水深为棱长的四棱柱，该柱的体积V可通过下式求得

式中：hA、hB、hC、hD分别表示4个采样点处的水深测量值;SABCD表示矩形ABCD的面积。将所有以条状栅格为底的四棱柱面积相加，求和结果即为该水库的库容值，经计算库容值为1 684.36 km3。在该水库中设计了60个补测点，根据补测点的位置分布情况为无人船规划一条最短巡航路径。用于仿真实验的硬件配置如下。

CPU：主频2.8 GHz的酷睿i5-6400。

内存：8 GB 2133 MHz的DDR4内存条。

硬盘：512 GB的固态硬盘。

2.2 路径规划实验

首先使用模拟退火算法对60个补测点计算最短巡航路径，经过16 500次循环后得到最短路径。第1次的巡航路径为3 071 733.84 m，最后1次的巡航路径为613 173.60 m，总耗时13 605 ms。为了进一步提高最短路径规划的效率，使用基于能耗均衡的多无人船自动巡航路径规划算法。按照上文所述流程，首先对60个补测点进行聚类处理，将其分成3个点簇，然后使用模拟退火算法再次计算每个点簇的最短巡航路径，如图5所示。

如图5所示，3个点簇的最短巡航路径依次是176 192.50、194 987.83、246 590.98 m。将3个点簇的路径相加求和，结果为617 771.31 m，与首次计算所得结果613 173.60 m相差不大。但是聚类处理后的搜索过程仅耗时2 088 ms，相比于首次计算用时的13 605 ms，效率提升了6倍。横向对比可以发现，3个点簇的最短巡航路径仍然差距较大，为了让多艘无人船的能耗趋于均衡，对3个点簇作出调整，根据点簇调整算法，点簇0需要从距离最近的点簇1中抽取1个点，点簇1需要从距离最近的点簇2中抽取2个点，如图6所示。

经过调整后，3个点簇的最短规划路径分别是204 664.82、216 269.08、220 021.11 m。最大差值从调整前的70 398.48 m变为15 356.29 m。由此可见，点簇调整算法能够有效平衡多个点簇之间的路径长度，从而保证了多艘无人船确定的最短巡航路径大体相等，节约了能耗、提高了补测效率。

3 结束语

使用无人机测算水库库容时，如果待测水库的平面面积较大，无人船的续航能力有限，无法保证一次性完成测算任务，不仅影响工作效率，而且对测算结果的精度也会产生影响。通过规划无人船的最短巡航路径，让无人船能够在续航范围内一次性完成测算任务，达到了降低能耗、提高精度的效果。使用模拟退火算法进行无人船巡航路径规划，虽然能够保证路径最短，但是路径寻找用时较长。通过聚类处理后，路径寻找用时变短，但是还存在不同点簇之间路径差异明显的问题。在此基础上使用点簇调整算法，保证不同点簇之间的最短路径趋于一致，在满足最短路径规划要求的前提下节约了能耗。

参考文献：

[1] 宋大雷，吕昆岭，曹江丽.基于深度强化学习的无人船全覆盖路径规划[J].现代电子技术，2022（22）：15-17.

[2] 吴昊，吴子昂，孟庆斌，等.水环境监测场景中的自主巡航无人船系统[J].电子制作，2023（2）：14-17.

[3] 宋大雷，干文浩，许嘤枝.无人船实时路径规划与编队控制仿真研究[J].系统仿真学报，2023（5）：957-970.

[4] 王朝飞，王慎执，宋士吉.面向海域巡逻的多无人船路径规划方法及仿真[J].中国图象图形学报，2023（8）：2536-2548.

[5] 张乃天，陈世才，蒙子昕.基于改进快速行进法的水面无人船全局路径规划[J].上海海事大学学报，2023（3）：5-11.

第一作者简介：吴健（1990-），男，硕士，工程师。研究方向为河道勘测，无人船。

*通信作者：何良（1982-），男，工程硕士，高级工程师。研究方向为河道勘测，无人机，点云。