水面无人艇（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个目标，并且在环境建模时还考虑了海流的影响。