水面无人艇（SV）即水面机器人，是一种支持无人操作的船舶，它只需要驾驶员在安全地点进行极少量的远程操作便能执行任务。

USV在海洋数据采样、海上搜索和救援、港口船舶管理、内河交通等方面发挥着重大作用。

目前，在军事领域，水面无人艇技术发展最成熟的国家是美国和以色列，美国海军研发的SpartanScout、SeadooChallenger2000和MUSCL等水面无人艇可用于执行情报收集、反潜作战、监视和侦察等任务；以色列海军的Protector、Stingary和SilverMarlin能够进行海岸物标识别、智能巡逻和电子战争等。

在民用领域，英国Plymouth大学的Springer可用于内河、水库和沿海等浅水域污染物追踪和环境测量；中国的云洲智能将无人船应用于环境监测，可进行在线水质污染和核污染监测。

美国海军空海系统概念图，来自网络

路径规划，即依据某些优化准则在工作空间中找到一条从起始到目标点的最优安全路径。路径规划问题一直都是水面无人艇领域的研究重点，在之前的研究中，已经有很多综述类文章对路径规划相关的问题进行了总结，但都是针对性地探讨某些方面，缺乏系统性的综述。

刘佳等对各种算法的特点作了系统介绍，然而作者更注重算法原理，忽略了环境建模、避碰规则以及船舶操纵特性等因素对路径规划的影响；陈华等和POLVARA等详细介绍了路径规划相关的算法，但仅仅是从原理上进行介绍，没有对其优劣势和改进方法进行评价和总结；CAMPBELL等对USV的发展进行了深入探讨，但侧重于控制相关的内容。

除此之外，上述文献均从全局路径规划和局部路径规划这2个方面来总结，没有包含近程反应式危险规避和无人船运动规划等方面的内容。

相比于其他的研究综述，本文内容更加全面，具体包括4个方面：⑴介绍了水面无人艇路径规划常用的几种环境建模方法，并将其优缺点进行对比分析；⑵跟进目前水面无人艇路径规划方面的最新研究进展，对各种算法及其改进算法进行评估，总结了学术界对各种算法改进的切入点；⑶除了全局路径规划和局部路径规划外，还总结了近程反应式危险规避和无人船运动规划的内容，包括碰撞危险度模型、船舶领域模型、避碰算法、运动规划与控制算法等；⑷综合近年来关于路径规划的文献，并为学者们提供未来的研究方向和重点。

一、图形环境建模

环境建模一般是从图形学的角度出发，将现实的物理空间抽象成算法可以处理的抽象空间，实现相互之间的映射。合适的环境模型有助于更好地理解环境变量，减少不必要的规划和计算。常用的环境建模方法有可视图空间法、Voronoi图法和栅格法等，各种方法的优缺点对比见表1。

表1 常用环境建模方法对比

可视图法采用多边形表示障碍物，每个端点都与其所有可见顶点相连（见图1），多边形的顶点连接其所有相邻点，因此无人船可以沿多边形边缘移动，通过搜索这些路线的集合，挑选出最佳路径。可视图法的优点在于可以寻找出全局最优路径，缺点是搜索时间复杂度为O(n2)，n指代问题规模，并且可能会发生碰撞，具体见图1。

图1 可视图法

Voronoi图是由一组连接两邻点连线构成的连续多边形组成，具体见图2。相比于可视图法，Voronoi图计算速度更快，时间复杂度为O(nlogn)，且可保证默认情况下生成的是最安全的路径，但必须利用到定位传感器（如LiDAR）进行准确计算举例。Voronoi图主要的缺点在于其搜索的节点存在局限性，生成的路径往往会偏长。 

图2 Voronoi图

栅格法将工作空间离散化成多个矩形区域，即网格，再通过算法搜索从初始网格到目标网格的最短路径，见图3。栅格法的搜索速度主要取决于网格的密度，可以根据地图的复杂程度进行调节，如果网格线之间的距离过大，搜索速度加快，但地图的精确度降低；如果网格线之间的距离过小，那么搜索时间将大幅度提升。栅格法的缺点在于其搜索性能有限，每次只能搜索8个或者16个方向，再加上网格的锯齿效应带来一系列的冗余点，很难得到最优路径。 

图3 栅格地图

二、全局路径规划

全局路径规划是基于全局海洋信息的静态环境地图进行的路径规划。水面无人艇的全局路径规划方法主要有进化算法和启发式搜索算法，这2种算法的特点与改进方法见表2和表3。进化算法可适应复杂的环境，改进的方法也更加多样化，易陷入局部最优状态，大多数情况下只能找到次优解。而启发式算法可找到最短的路径，但随着计算范围的增加，会消耗更多的时间和内存，缺乏适应性。

表2 主要的进化算法对比分析

表3 发式搜索算法对比分析

⒈化算法

遗传算法是最常用的优化工具之一，由HOLLAND提出。遗传算法的优点是有较强的鲁棒性和适应性，但其局部搜索能力较弱，容易产生冗余点，难以得到最优路径。学术界对遗传算法的改进通常包括：⑴进化算子的改进或引入新的搜索规则；⑵其他算法进行融合。TAM等提出了一种结合COLREGS规则的遗传算法，并且考虑了船舶的速度和转向角度等动力学因素，将其应用于船舶近距离避障。CAO基于Voronoi图提出了一种基于多处理器的遗传算法，当一个处理器进行决策时，另一个处理器同时预测所有可能目标的演化过程，预先筛选出优秀的个体，从而大大降低了搜索时间。ZHANG等提出了一种遗传算法与模拟退火算法的混合方法，将插入算子和删除算子引入遗传算法中来提高算法的效率，同时利用Metropolis准则改善了算法的局部搜索性能和收敛速度。SZLAPCZYNSKI的一系列研究利用遗传算法解决了多个船舶相遇的路径规划问题，并且将其应用于能见度低的环境中。蚁群算法最初由DORIGO等提出，这种算法的优点在于强鲁棒性和适应性，且易与其他算法结合。而缺点在于，若初期缺少信息素，则会降低算法的求解速度。同时，蚁群算法对初始参数的要求较高。学术界对蚁群算法的优化主要从3个方面进行：⑴基于搜索策略的优化；⑵基于参数自适应的调整；⑶与其他优化算法相结合。WU等对蚁群算法的搜索策略进行了改进，引入了返回和死亡机制，如果蚂蚁周围没有可行的解，将返回上一个节点，如果返回之后搜索不到其他可行节点，那么蚂蚁死亡。这种方法屏蔽了无效路径的影响，提高了搜索效率。封声飞等对算法进行了自适应调整，在状态转移概率中引入了转角启发信息，提高了搜索的效率，同时在迭代次数达到阈值后会重新调节信息素挥发系数和浓度，避免算法进入局部最优。LAZAROWSKA利用试验船HoryzontII的航行数据模拟实际海洋环境，并在仿真平台上验证了蚁群算法在真实海洋条件下依然具有良好的安全性和实用性。粒子群优化算法是一种形式较为简单的智能优化算法，由EBERHART等于1995年提出。粒子群算法与其他智能算法相比，其优势在于计算简单且容易实现，但容易陷入局部最优。SHEN等将传统粒子群优化算法应用到切线图中，类似地，LIU等利用混沌序列和多人口机制对粒子群优化算法（PSO）进行改进，然后再应用于切线图中。虽然后一种算法的收敛性和搜索能力都得到了提高，但二者都是先通过Dijkstra算法生成链接图，再利用PSO对各个节点进行优化，这种方法从根本上限制了PSO的使用范围。HU等提出了一种将分级排序规则融入到多目标PSO的算法，在迭代过程中有针对性地选择更符合要求的粒子，从而优化了算法的过程。MA等提出了动态增强多目标PSO算法，可同时优化路径的长度、光滑度、经济性和安全性等4个目标，并且在环境建模时还考虑了海流的影响。

⒉启发式搜索算法

A*算法由HART等在1968年提出，是一种基于启发函数的图搜索算法，用于寻找2个节点之间最短的路径。相对于其他启发式搜索算法，A*算法效率更高，能够保证以最小的成本返回最短路径。但其缺点是适应性差，需要消耗大量的时间和储存空间，同时算法生成的锯齿状路径对船舶的航行不利。SONG等对A*算法进行了改进，将算法的搜索范围扩大了1倍，利用3种路径优化方法解决了转折过多的问题，并且将其运用到了无人船“Springer”系统中。YANG等提出了“有限角度A*算法（FFA*）”，在扩大搜索范围的同时引入了安全距离和视线制导的规则，保证了路径的有效性和合理性。WANG等将改进的A*算法用在了六边形网格地图中，提升了算法的效率，并且将“引导值”加进了启发函数当中，解决了启发函数相同时的决策问题。CHEN等提出了A*BG算法，这种算法保留了A*VG可搜索全局最优路径的优点，并且证明该算法的速度要优于传统的A*，但试验中没有考虑近海基础设施和算法实时信息的数据，其实用性还有待验证。综上可知，学术界对A*算法的改进主要包括：⑴扩大邻接点的搜索数目，改进搜索规则；⑵启发函数的改进；⑶优化路径；⑶采用不同的环境建模方法。Dijkstra算法由DIJKSTRA在1959年提出，是一种经典的最短路径搜索算法。Dijkstra算法在搜索的过程当中执行了很多与最短路径无关的顶点计算，当情况较复杂的时候，算法的效率较低。目前学术界对Dijkstra算法的改进通常分为3种：⑴基于搜索策略的优化，如扩展搜索区域；⑵优化数据储存结构；⑶优化环境模型，如分层搜索。CHENG等对Dijkstra算法的搜索策略进行了改进，将多个角度纳入搜索范围之内，用栅格地图验证了本方法比传统Dijkstra和八方向搜索的Dijkstra得到的路径距离更短。SEKARAN等提出Dijkstra的改进算法，只计算距离最近的节点，减少了不必要的节点计算，节省时间的消耗，并且在V-REP试验平台上验证了该算法的实用性。GUO等在算法中引入了运行时间计算机制，当出现多条路径长度相等的情况时，通过运行时间计算出最优的路径。康文雄等提出了分层Dijkstra算法，该算法利用分层结构，可实现对搜索进度的保存与回溯等操作，该算法虽不一定能找到理论最优解，但在数据量大的时候可以快速找到次优解。

三、局部路径规划

局部路径规划依靠传感器获取周围环境信息和无人船的位置，将各种传感器信息融合后建立环境模型，再通过算法进行路径规划。主要的算法包括人工势场法、快速扩展随机树法和动态窗口法等。

⒈工势场法

人工势场法（APF）最早由KHATIB提出，是水面无人艇局部路径规划的一种常用算法。人工势场法具有模型结构简单、计算快速和实时性强等多个优点，但可能会出现局部最优、受力平衡、斥力大于吸引力等不利情况。综合近年来的研究，学者们对人工势场法的改进切入点包括3类：⑴修改引力和斥力的势场模型；⑵与其他算法相结合；⑶采用不同环境建模方法。MIELNICZUK将人工势场法运用于船舶航运路线生成中，利用4种不同的障碍物情景进行了有效性验证，结果表明，人工势场法能够快速、高效地找到一条安全的航线，但没有解决局部最优问题。LAZAROWSKA在一系列研究中提出了离散人工势场法（DAPF），将环境模型离散化为栅格地图，再根据COLREGS和计算规则确定了每个栅格的势能，分别在静态和动态障碍物环境下验证了算法的有效性，结果表明，该算法不仅能高效快速地计算出安全路径，而且也解决了局部最优和受力平衡等问题。LYU提出了“路径引导人工势场法”，该算法考虑了COLREGS规则和船舶操纵特性，同时在运行过程中可快速根据环境的变化及时反馈信息，并做出路径调整，但本文仅对船舶的转向角做出了限制。

⒉速扩展随机树

快速扩展随机树（RRT）最早由LAVALLE提出，该方法适合解决多自由度机器人在复杂环境下和动态环境中的路径规划，但生成的最终路径不是最优。对RRT算法的改进可以从3个方面切入：⑴引入启发信息，使探索过程不再随机化；⑵改变搜索策略，如扩展搜索方向、引入新规则；⑶与其他算法结合。CHIANG等提出了一种结合COLREGS的改进RRT算法，通过RRT的增长期间对其他船舶进行联合仿真来实现的，从而预测未来发生的碰撞。仿真结果表明，相比基于模型预测控制（MPC）与APF的避障算法，该算法拥有更高的成功率，但仿真没有考虑到风、浪、海流的影响。庄佳园等设计一种基于改进RRT算法的局部路径规划方法，在生长时加入了衡量节点探索失败次数的抑制因子，使探索不再随机发生，同时限制了最大转角，使规划航迹趋于实用。该算法提高了搜索效率，并且符合实际的无人船跟踪路径，缺点是没有考虑COLREGS规则和实际环境的影响。

⒊态窗口方法

动态窗口方法（DWA）是一种常用的路径规划方法，最初由FOX等于1997年提出。该算法在速度空间中采样多组速度值，并模拟机器人在各速度下生成的轨迹，在时间最短内达到目标点即为最优解。WANG等提出了一种DWA与A*算法结合的路径规划系统，同时考虑了路径的实用性和USV的动力学性能，并且无人船可通过选择最优速度来躲避未知的障碍物。MISSURA等对传统DWA算法进行了改进，引入了“动态碰撞模型”，在考虑障碍物运动的同时预测未来可能的碰撞。LIN等提出了一种可实时路径规划的DWA算法，该算法根据障碍物的比例用圆形或者矩形建模，简化障碍物形状，减少了空间和时间的浪费，同时可以考虑多个静态和动态障碍物，具有很强的适应性，但其缺点在于仿真过程没有考虑环境因素。

⒋比分析

表4总结了上述局部路径规划方法的优缺点以及学术界对算法改进的切入点。

表4 局部路径规划算法对比分析

四、近程反应式危险规避

近程反应式危险规避是指水面无人艇在按照既定路线航行的过程中，如果发现突然出现的障碍物，水面无人艇应及时进行调整和应对，从而有效避免与障碍物的碰撞。船舶的近程避碰与上文提到的路径规划有很大的区别。路径规划通常将船视为质点，忽略了其操作运动特性，而近程避碰需要考虑到船舶的形状、领域、会遇姿态以及安全距离等。

⒈碰撞危险的识别

判断船舶在未来航行中的碰撞危险可以用碰撞危险系数（CRI）进行判别，当CRI超过某设定阈值时，则会发出警报表示碰撞危险较高。计算CRI最常用的2个量化指标分别是两船相遇的最近会遇距离（DCPA）和到达最近会遇点的时间（TCPA），这2个指标可通过两船的速度和航向求得。DCPA通常用于确定碰撞危险发生的可能性，TCPA用于估计危险程度，因此学者们将DCPA与TCPA的值按照一定的函数关系得到CRI，从而对碰撞危险进行综合评估。一种普遍的CRI计算公式为：CRI＝w1×f×(DCPA)＋w2×f×(TCPA)，⑴式中：w1和w2均为权重，通常根据专家的经验以及一些数学方法来确定，如模糊理论、概率回归等。碰撞危险度模型可作为船舶采取避碰行动的依据。CRI是一个简化后的模型，但实际上碰撞会与很多抽象的因素相关，而CRI只能判断船舶之间是否存在碰撞风险，无法给出避碰方法。另一种重要的碰撞模型是船舶领域模型。船舶领域是指船舶周围的有效区域，该区域是保证任何一艘安全航行的所需水域。船舶领域的概念最初由FUJII等提出，该模型的研究使得避碰模型更加完善，可以根据船舶的位置、速度和航向来推断最小安全通过距离和船舶领域尺寸，这对碰撞危险的识别和避碰路线的选择有重要意义。

⒉主要算法

陈姚节等提出了基于速度障碍法的船舶避碰模型，考虑到了多个目标船的约束条件以及船舶的操纵要求，但未考虑复杂环境下的约束条件以及环境扰动的影响。马文耀等将人工鱼群法应用在避碰路径规划决策中，以前进距离为目标函数，计算出最优的避让转向时机、避让角度、复航时间和角度，还考虑到了COLREGS规则。王得燕等利用粒子群优化算法解决多船会遇情况下的本船最优转向角度值，有助于多船避碰决策系统的智能化设计与开发。SONG等提出了一种速度障碍法与APF结合的混合算法进行避障，其中APF起到一个全局路径规划作用，提高了避障的实时性能。同样，LU结合了APF与速度障碍法，且加入了COLREGS规则以及路径优化功能。

五、运动规划与控制

运动规划阶段完全考虑了水面无人艇的运动学和动力学约束，通常会从控制层面来研究规划问题，其目标是通过自身的控制系统来逼近和实现规划的路径。按照研究对象的可控程度来划分，运动规划可分为完全驱动系统和欠驱动系统。对于完全驱动系统，其运动过程完全可控，所能呈现的运动姿态都可以通过方程进行准确表达。因此，完全驱动系统常见的运动规划方法是建立精准的运动控制模型，然后根据具体的规划任务对主要控制参数进行调整和优化。无人艇属于欠驱动系统，由于系统的控制量个数小于自由度个数，因此很难简单地通过优化控制参数来进行路径规划，其运动规划通常分为2步：⑴利用路线规划算法，从起始状态到目标状态寻找一条安全路径；⑵以研究对象的运动学和动力学模型为基础，设计相应的控制器来驱动机器人按照该路径运动，最终到达目标点。无人艇的运动规划研究起步较晚，多数规划方法都是基于传统的路线规划算法。FEDORENKO等在机器人操作系统（ROS）环境下设计了基于Voronoi图的无人船路径规划系统，利用李雅普诺夫不稳定性定理进行运动规划，这种方法的优点在于实现简单并且不需要在障碍物区域重新构建路径，保证了算法的实时性。ESCARIO等利用改良后的蚁群算法进行USV的运动规划，该算法结合无人船的数学模型，利用优化方法生成最优的运动和操纵轨迹，并且分别在开阔海域和受限制的海域验证了该算法的有效性。GU等基于改进的A*算法和轨迹单元法，设计了一种适用于受限制水域的运动规划方法，可同时满足船舶状态、操作特性和水域环境等多个约束条件，且采用真实船舶模型在受限制水域进行了验证。

六、结语与展望

学术界认为，水面无人艇路径规划和避碰的解决方案仍有很大的发展空间，未来无人船路径规划的研究应以7方面为研究重点：

⑴利用实际的海洋交通数据进行试验。本文提到的大部分文献都是用非实际的数据进行仿真，只能证明其理论上的有效性，无法评估算法在实际环境数据下的效率，故其实用性有待验证。

⑵考虑外界干扰信号如风、浪、海流的影响。现有研究的环境建模忽略了风、浪、流对无人艇的影响，环境模型不够完善，算法在实际航行中的表现会与理论存在偏差。

⑶路径优化和运动规划，考虑控制器的协同。许多算法在仿真过程中都没有将船舶的动力学特点作为约束条件，生成的路径缺乏实用性，在进一步的研究中，要将路径优化方法与路径规划方法结合生成更加光滑和简洁的路线，同时考虑船舶的操纵性能，限制船舶的转向角、速度和加速度值等参数进行运动规划，与下层的控制器协同。

⑷开发基于国际海上避碰规则的路径规划系统。目前许多加入了国际海上避碰规则的算法都只考虑到特定的几条规则，如第13～15条，且都是在单一情况下。然而很多复杂的海况可能会同时出现交叉、追遇等多种情形，特别是在多船规划时，避碰系统很难界定应该采用哪条规则进行避碰。因此，完全将COLREGS整合到路径规划中仍是一个巨大的挑战。

⑸考虑复杂动态情况下的危险规避。现有的危险规避仿真中，障碍物通常是静态或者半动态，障碍物的运动仅限于直线，不会改变运动的方向。而实际航行中远比该情况复杂，障碍物的运动轨迹是未知的，速度和航向都可能会发生变化，将其视为直线仅仅是考虑最简单的情况。

⑹完善船舶碰撞危险度评估模型。现有的碰撞危险度模型采用1～2个主要因素来评估船舶发生碰撞的危险度，而实际上航行的潜在危险将受到很多抽象和定性因素的影响，如何通过模型来建立完整的环境模型仍然需要大量研究。

⑺完善对路径的评价体系。除了安全之外，路径的长度最小通常是路径规划的重要评价指标，许多算法都会以距离作为最终的优化目标。但路径的好坏受到多方面因素的影响，如光滑度、经济性、能耗和时间等，因此路径评价体系还需完善。