作者：马思远，黄大志，徐慧丽，付晓月（江苏海洋大学，江苏 连云港 222005）

摘要：路径规划算法是无人平台领域的重要研究方向，水面无人艇是一 种可移动的水面无人平台。本文根据水面无人艇路径规划的功能进行分 类，将路径规划算法划分为局部路径规划和全局路径规划，并分析和对 比各常用算法的优缺点，同时对优化算法的现状进行了介绍。最后对目 前无人艇路径规划算法进行了总结。

关键词：无人艇；路径规划算法；A*算法

Abstract: The unmanned surface vehicle is a kind of movable surface unmanned platform. This paper classifies the path planning algorithms into local path planning and global path planning according to the function of unmanned surface vehicle path planning, and analyzes and compares the advantages and disadvantages of each commonly used algorithm , and introduces the current status of optimization algorithms. Finally, we present the summary of the current unmanned surface vehicle path planning algorithms.

Key words: Unmanned surface vehicle; Path planning algorithm; A* algorithm

1　引言

水面无人艇，也可以称为水面机器人，是一种小 型的智能水面平台，它具有体积小、移动迅速、智能 化程度高的优点，用于执行危险或不适合人工作业的 任务[1]。最早的无人艇出现于20世纪50年代，主要用作 水面靶艇和水面排雷艇，但仅限于人工平台的工作范 围之内[2]。随着当前卫星通讯技术和自主导航技术的发 展，水面无人艇作为小型任务平台，其工作范围已经拓 展至深海区域。在军事领域，无人艇可以通过搭载不同 的模块，执行情报收集、快速打击、扫雷和海域勘测等 任务，通过港口投放和随船投放的方式拓展海上的作战 范围[3]。在民用领域，水面无人艇主要用于水文勘探， 也可作为中继站，与无人机和水下机器人通信，实现多 设备协同[4]。路径规划是无人艇自主航行的关键技术， 也是目前需要解决的重要问题[5]。

路径规划问题分为全局路径规划和局部路径规 划。全局路径规划利用电子海图等先进信息，根据任 务需求，在较大的范围内借助合适的搜索算法，寻求 一条可行的无障碍路线。局部路径规划算法在全局航 行中起辅助作用，无人艇在全局路径航行中，对未知 的障碍物进行探测并自主避让，避让完成之后继续按 照全局路径行驶。

本文针对目前无人艇的路径规划算法进行了研究， 比较不同算法的优缺点，阐述了算法优化的研究现状， 最后对无人艇路径规划的算法进行了总结。

2　全局路径规划算法

全局路径规划算法需要获取整个环境的信息， 根据获得的完全信息对环境进行建模，并对指定路 径进行初步规划[6]。在整个全局路径规划的过程中， 可以将路径规划问题拆分为环境信息获取及建模和路 径规划算法选择，当存在未知的障碍物或者航行途中 偶遇突发状况则无法解决，只适用于对实时性要求不 高、环境信息获取完全的情况。本文只阐述路径规 划算法，对如何获取环境参数以及如何建模等问题 不做阐述。

2.1　Dijkstra算法

Dijkstra算法由Dijkstra[7]在1959年首次提出，是一种计算精度较高的全局路径规划算法，用于获取最短 路径。

经典的Dijkstra算法原理简单，但是计算流程过于 复杂且占用较多的内存，获取的结果只能按照预定的路 线航行，只适用于较小规模的路径规划。

王先全[8]等使用邻接表以及二叉排序树结构，对 传统的Dijkstra算法进行优化，以此提高计算效率，加 快路径规划速度。庄佳园[9]等使用动态网格模型，将基 于距离寻优的Dijkstra算法应用于无人艇的全局路径规 划，通过删减非最短路径的节点，在降低算法自身的内 存占用的同时，加快规划速度并优化全局路径，使得规 划的路径更加平滑，适合无人艇的航行。

2.2　A*算法

A*算法是由Hart[10]等提出的一种启发式算法，它 是Dijkstra算法的拓展，同时也是静态网路中寻找最短 路径最有效的方法。

A*算法原理简单，比Dijkstra算法运算更快，但是 其对启发函数非常依赖，这就导致该算法计算量巨大。 由于A*算法的效率最高，被广泛利用，不少专家也根据 A*算法的缺陷对其加以改造。Svec等将路径规划算法 和局部有界最优算法结合，用于解决无人艇的动态路径 规划问题，通过取最小值中的极大值，将海浪等因素可 能导致的偏差考虑在内，更加适合海上环境；通过实验 证明该算法具有实用价值，但是这对无人艇运动控制的 精度要求更高。KIMH提出了一种基于改进A*算法的路 径规划算法，由于KIMH将无人艇的最大转弯半径以及 外界环境纳入考虑范围，改进后A*算法更加灵活，通过 仿真实验也证明了算法的有效性。

2.3　蚁群算法

蚁群算法（Ant Colony Optimization，ACO）是 Dorigo[11]等提出的一种智能优化算法，通过重复模拟 蚁群的觅食行为完成最优路径的寻找。

蚁群算法相比于传统算法，具有较高的鲁棒性 和便于并行的优点，但是如果初期路径规模太大或者 前期信息素缺失，可能导致路径规划求解时间变长或 无法得到全局最优解。针对蚁群算法的这一问题， Stutzle等提出最大最小蚂蚁系统（MMAS），通过对 路径上的信息素进行上下限的限制，在一定程度上减 少了停滞现象，但是当求解过于分散时，收敛速度也 会减慢。尽管如此，MMAS算法能够有效平衡收敛速 度和避免局部最优解，因此MMAS算法可以较快地获 得最优解。游晓明[12]等提出了一种新的动态搜索诱导 算子以改进蚁群算法性能，在进化过程中利用动态衰 减模型调整阈值以加快收敛速度，测试结果说明该改 进算法不仅可以加快收敛速度，同时还可以提高优化 解的质量。

2.4　遗传算法

遗传算法由Holland[13]提出，是一种模拟生物进 化过程的随机搜索算法。遗传算法具有较高的鲁棒 性，适合复杂环境下的路径求解问题，应用非常广 泛，但是其存在收敛速度慢、控制变量多求解能力较 差的缺点。针对遗传算法存在的缺点，Long等针对遗 传算法求解过慢的问题，使用网格法对环境建模，提 出一种全新的初始种群，提高种群的收敛速度以及种 群的初始质量，通过设置自适应交叉概率以及变异概 率，生成路径的速度有较为明显的提高，实验仿真证 明了该算法的可行性。

2.5　智能水滴算法

2009年Hamed Shah-Hossini提出智能水滴算 法，智能水滴算法根据水滴与周边河道环境互相产生的 影响，如前进速度、自身携带的泥土量，通过概率实现 对路径的选择，水滴受重力作用进行启发式搜索，以此 求解最优路径。

与其他传统算法相比，智能水滴算法具有良好的 正反馈机制和自组织特性，但是其存在计算力较低、搜 索能力差和算法早熟的缺点。

徐佳敏[14]等针对智能水滴算法的算法早熟问题，提 出了通过非均匀性的编译避免算法早熟。EZUGWU[15] 等设计出了一种增强智能水滴算法，将退火算法作为局 部启发式搜索元引入智能水滴算法，加快了算法的收敛 速度。

2.6　对比分析

全局路径规划算法的优缺点对比如表1所示，除去 文中介绍的算法之外，还有模拟退火算法、神经网络算 法等其他全局规划算法，但其在无人艇的路径规划中应 用较少，故在此不做比较。

表1 全局路径规划算法比较

3　局部路径规划算法

与全局路径规划算法不同，局部路径规划算法不需 要完整的环境信息，通过传感器从周围位置环境获取信 息，包括但不限于障碍物的尺寸、形状和相对速度，并 通过算法计算得到一条安全的路径[16]。常见的局部路径 规划方法包括人工势场法、速度障碍法、向量场直方图 法等。

3.1　人工势场法

人工势场法由Khatib首次提出，目前已经成为局 部路径规划中应用最广泛的方法。人工势场法具有计算 简单、反应迅速的优点，但是如果存在某一点合力为 0，无人艇将围绕此点做圆周运动，最终无法到达目的 地，陷入局部最小值问题，除此之外，当无人艇的周围 被障碍物环绕时，利用人工势场法无法求解。

陈超[17]等通过引进新的引力场函数和斥力场函数， 对传统的人工势场法进行优化。除此之外，在应力场内 添加震荡函数，当USV陷入局部最小问题时，震荡函数 通过修改引力场方向破坏局部最小问题的平衡，通过仿 真结果得到该优化算法可以解决局部最小问题，但是求 解的路径随机且不是最优解。

3.2　速度障碍法

速度障碍法（Veloc ity Obstacle，VO）是 Fiorini[18]等提出的一种局部路径规划算法。速度障碍 法与其他智能算法相比，将障碍物的速度属性考虑进 来，能可靠地保障无人艇的避障安全，规避的准确性非 常高；但是该算法没有考虑障碍物速度的动态变化，并 在规划避障路线时，速度较慢。

Kuwata等成功地将速度障碍法应用于USV的局部 避障，通过计算无人艇与障碍物之间的最近距离以及到 达最近距离的时间，只有当最近距离和到达最近距离的 时间都满足约束条件时才会判定可能发生碰撞，同时建 立代价函数，这时候只需要从安全的速度空间内选取代 价函数值最小的速度矢量即可实现局部避障。

3.3　向量场直方图法

向量场直方图法是Borenstein[19]针对人工势场法 的特殊情况提出的一种实时路径规划算法。向量场直方 图法拥有较好的鲁棒性，适用于多种场合的局部动态避 障，但是由于缺乏对障碍物速度属性以及USV操控性的 考虑，计算得到的结果可能陷入局部最优问题。Loe[20] 针对局部最优问题，通过将向量场直方图算法与A*算法 结合，得到VFH*法，该算法在复杂的局部环境中依然 可以进行局部路径规划。Babinec[21]等提出了一种基于 VFH的优化算法，通过栅格化建模，将无人艇航行空 间划分为具有二值信息的单元，通过获取单元的信任度 值计算障碍物栅格的向量值和矢量角等信息，得到复杂 环境下的最优路径。

3.4　对比分析

以上局部路径规划算法的优缺点如表2所示。除此 之外还有梯度法、ASL法等经典局部路径规划算法，但 是并不适用于无人艇领域。

表2 局部路径规划算法比较

4　结论

相较于局部路径规划算法，全局路径规划算法 的研究已经比较成熟，路径规划的解决方案得到了实 践并验证了可行性。但是局部路径规划算法的研究目 前只适用于实验室模型验证，只是简单的工程解决方 案，还无法应用于海面的复杂状况。

2021年江苏海洋大学研究生科研创新计划项目 （KYCX2021-087）

作者简介：

马思远（1998-），男，江苏连云港人，硕士，现就读 于江苏海洋大学，研究方向为船舶与海洋工程。

黄大志（1977-），男，河南新野人，副教授，博士， 现任教于江苏海洋大学，研究方向为海洋智能装备 。 为本文通讯作者。

徐慧丽（1997-），女，江苏盐城人，硕士，现就读于 江苏海洋大学，研究方向为船舶与海洋工程。

付晓月（1998-），女，河南安阳人，硕士，现就读于 江苏海洋大学，研究方向为船舶与海洋工程。

参考文献：

[1] 曲毅, 潘民子. 无人艇路径自主规划方法及策略研究综述[J]. 信息通信, 2019, (08) : 278 - 280.

[2] 段宝生. 无人水面自主工程勘察船技术[J]. 中国科技信息, 2014, (15) : 106 - 107.

[3] 薛春祥, 黄孝鹏, 朱咸军, 蒋莹莹. 外军无人系统现状与发展趋势[J]. 雷达与对抗, 2016, 36 (01) : 1 – 5, 10.

[4] 李家良. 水面无人艇发展与应用[J]. 火力与指挥控制, 2012, 37 (06) : 203 - 207.

[5] 孙晓界. 无人水面艇实时路径规划系统研究[D]. 大连: 大连海事大学, 2016.

[6] 刘琨. 基于人工势场和蚁群算法的无人船路径规划研究[D]. 海南: 海南大学, 2016.

[7] E. W. Dijkstra. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1 (1).

[8] 王先全, 周锡祥, 余浩源, 李浩, 王向雨. 基于改进Dijkstra的应急指挥车及时救援的最短路径算法的研究[J]. 电脑知识与技术, 2021, 17 (14) : 1 – 3, 10.

[9] 庄佳园, 万磊, 廖煜雷, 孙寒冰. 基于电子海图的水面无人艇全局路径规划研究[J]. 计算机科学, 2011, 38 (09) : 211 – 214, 219.

[10] Peter E. Hart, Nils J. Nilsson, Bertram Raphael. Correction to "A Formal Basis for the Heuristic Determination of Minimum Cost Paths"[J]. ACM SIGART Bulletin, 1972, (37).

[11] Marco Dorigo, Gianni Di Caro, Luca M. Gambardella. Ant Algorithms for Discrete Optimization[J]. Artificial Life, 1999, 5 (2).

[12] 陈佳, 游晓明, 刘升, 李娟. 动态分级的改良蚂蚁算法及其应用研究[J]. 计算机应用研究, 2019, 36 (02) : 380 - 384.

[13] Holland John H.. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence[M]. The MIT Press: 2018-08-31.

[14] 徐佳敏, 叶春明. 基于改进智能水滴算法的应急物流路径研究[J]. 物流科技, 2015, 38 (08) : 28 - 31.

[15] Ezugwu Absalom E, Akutsah Francis, Olusanya Micheal O, Adewumi Aderemi O. Enhanced intelligent water drops algorithm for multi-depot vehicle routing problem.[J]. PloS one, 2018, 13 (3).

[16] 刘建. 水面无人艇路径规划技术的研究[D]. 镇江: 江苏科技大学, 2014.

[17] 陈超, 耿沛文, 张新慈. 基于改进人工势场法的水面无人艇路径规划研究[J]. 船舶工程, 2015, 37 (09) : 72 - 75.

[18] Paolo Fiorini. Motion Planning in Dynamic Environments Using Velocity Obstacles[J]. The International Journal of Robotics Research, 1998, 17 (7).

[19] Johann Borenstein, Yoram Koren. The vector field histogram-fast obstacle avoidance for mobile robots.[J]. IEEE Trans. Robotics and Automation, 1991, 7 (3).

[20] Loe Ø. Collision avoidance concepts for marine surface craft[J]. Rapp. tecn. Norvegian University of Science e Technology, 2007.

[21] Babinec A, Duchoň F, Dekan M, et al. VFH* TDT (VFH* with Time Dependent Tree): A new laser rangefinder based obstacle avoidance method designed for environment with non-static obstacles[J]. Robotics and autonomous syste ms, 2014, 62 (8) : 1098 - 1115.

摘自《自动化博览》2021年11月刊