无人水面艇避障路径规划算法综述

刘 佳 王 杰

(南京信息工程大学自动化学院 BDAT&CICAEET 江苏 南京 210044)

0 引 言

无人水面艇(Unmanned Surface Vehicle,USV)也可称为水面无人艇或水面机器人，是一种无人操作的水面舰艇，主要用于执行危险以及不适合有人船只执行的任务[1]。在无人水面艇领域，美国和以色列的相关技术比较领先，相比较而言，目前国内的无人水面艇技术还比较落后。美国空间和海战系统中心研发的“SSC San Diego”号无人水面艇，结合电子海图实现了路径规划功能，以自动雷达标绘仪的目标检测信息实现了局部危险情况下的紧急避障[2]。以色列研发的“Protector”号无人艇已经交付给以色列军方，具有模块化、反水雷战、情报监视和侦察等特点[3]。国内的云州智能公司将无人艇推向民用领域，实现了在线水质检测等多项功能[4]。

避障路径规划一直都是无人水面艇研究的重要内容，无人水面艇的自主能力之一是与外界未知环境进行交互，需要采集外界环境信息，从而保证无人水面艇能够根据外界环境信息进行路径规划，以及进行局部危险状况下的避障。避障路径规划就是根据行进要求和采集到的障碍物的状态信息，找到一条从起始点到目标点的最佳行进路径，最后安全到达目标点。

无人水面艇的避障路径规划可以分为基于完全信息的全局路径规划算法和基于传感器信息的局部路径规划算法。本文对现有的无人水面艇避障路径的众多算法的优点与不足进行了研究，对改进算法取得的最新的研究成果也进行了探讨，最后对无人水面艇的避障路径规划的发展现状进行了展望。

1 全局路径规划算法

全局路径规划一开始就要获取整个的环境信息，然后依据环境建模构造的环境地图，在规定区域进行初步的路径规划，可以归纳为两个子问题，即环境建模和路径规划算法。它依赖于全局环境信息，不能处理规划过程中出现的临时问题，若出现未知障碍物则无法使用，但一般情况下都可以找到最优解，且对实时性要求也不高[5]。

环境建模是路径规划的第一步，其将现实的物理空间抽象成算法可以处理的抽象空间，实现相互间的映射。常见的环境建模方法有可视图空间法、拓扑图法、自由空间法、栅格法、Voronoi图法和单元树法等图形学方法，它们往往是将无人水面艇所在的环境信息转换成图的问题，对整个环境空间进行描述，将实际问题转换成数学问题，虽然提供了建模的基本方法，但也存在着搜索能力不足等问题[6]。

1.1 基于图形法的路径规划算法

在上述成熟的图形学环境建模方法之上，出现很多基于图形法的全局路径规划算法，如Dijkstra算法、A*算法。

1.1.1 Dijkstra算法

Dijkstra算法是Dijkstra[7]在1959年提出的典型全局规划最短路径算法，用于计算一个节点到其他节点的最短路径。其基本思想如下：

1) 分配起点s，并且把两个集合记为S和U。集合S是用来储存已求出最短路径的顶点，集合U则是储存还没有求出最短路径的顶点。

2) 一开始，集合S只包含起点s，集合U包含剩下的顶点，集合U中顶点的路径是“起点s到该顶点的路径”，从集合U中找出路径最短的顶点加入集合S中。

3) 更新集合U中的顶点和顶点对应的路径。

4) 重复执行步骤2)-步骤3)，直到集合U中不存在顶点。

传统Dijkstra算法虽然简单明了，但占用内存大、计算效率较低，且只能按照预设路径行走，所以一般只适用于小规模情况下的避障路径规划。

庄佳园等[8]为了减少Dijkstra算法自身内存占用问题的影响，采用动态网格模型，对海面上的无人水面艇路径规划应用基于电子海图的距离寻优Dijkstra算法，距离寻优的目的是减少扩展非最短路径上的节点，从而提高计算效率，加快路径规划速度，最后优化路径，增加路径光滑度，满足无人水面艇的控制要求。Singh等[9]在动态海洋环境下应用Dijkstra算法进行全局路径规划，同时考虑到不同强度洋流对于无人水面艇最优路径规划的影响，将地图映射成二叉图，充分考虑了最佳路径曲率约束；将无人水面艇规定为圆形边界包围，为水面无人艇生成了更安全的最优路径。

1.1.2 A*算法及其改进算法

A*算法是Hart等[10]发明一种启发式算法，是Dijkstra算法的一种扩展，是静态路网中寻找到最短路径的效率最高的直接搜索方法。其基本原理为：

首先设定一个代价函数：

f(n)=g(n)+h(n)

(1)

式中：f(n)是起点到某一个目标点的估价函数；g(n)是起点到当前节点n的实际代价值；h(n)是当前节点n到某一个目标节点的估计代价值，也被称为启发函数。A*算法找到最优避障路径的关键就是对启发函数h(n)的选择。

1) 当h(n)≤d(n)时(d(n)为当前节点到某一个目标点的距离)，虽然能够得到最优解，但是搜索节点数量多，效率低下。

2) 当h(n)>d(n)时，搜索节点变少，效率提高，但是可能会导致不是最优解。

A*算法简单，运行速度比Dijkstra算法快，但其依赖启发函数，计算量巨大，规划路径的时间过长。A*算法应用广泛，许多学者针对其不足提出许多改进与变种，如：D*算法[11]及其变种算法Focussed D*[12]算法和D*Lite[13]算法，ARA*算法[14]，Anytime Dynamic A*算法[15]等。

D*算法是一种动态A*算法，适用于动态路网中；Focussed D*算法将A*算法与D*算法相结合，将启发式函数更多地注重于成本代价的更新；D* Lite算法是基于LPA*算法的一种启发式算法，它更加简单易懂，便于实现，性能优于Focussed D*算法，应用更加广泛。ARA*算法适用于有时间限制的避障路径规划，即牺牲最优解的情况下进一步增强其实时性，中途被打断也可继续重启生成可行路径。Anytime Dynamic A*算法则是结合D*算法与ARA*算法，适用于动态环境下的复杂障碍物避障路径规划。上述改进算法已经在机器人和无人机领域的路径规划上得到广泛应用，但是学者在水面无人艇的路径规划更多的还是基于原始A*算法的改进。

Svec等[16]提出基于A*的启发式搜索和运动不确定性下的局部有界最优规划方法，用于规划无人水面艇的动态可行路径。该算法使用最小极大值搜索算法，允许算法考虑由于海浪导致无人艇偏离其原始路线的可能轨迹，更符合海上的复杂环境。实验证明该算法具有实用价值，同时要求无人水面艇与原本规定路径上相距距离较近，对于无人水面艇的控制要求提出了更高的要求。陈超等[17]针对A*算法依赖启发函数的问题，提出一种基于可视图的改进A*算法，加入判断空间点和障碍物特征点相对关系，在起点和终点发生变化时不需要重新构建可视图，加强了无人水面艇适应未知环境的能力。实验证明运用启发式搜索的方法可减少需要搜索节点的数目，大幅减少了规划时间。Wang等[18]为了加快A*算法的路径规划速度，提出将A*算法与动态窗口法相结合的无人水面艇混合路径规划，将无人水面艇的运动特性考虑其中，改进成具有后平滑路径的算法来减少航线点数量，同样可以生成更短的路径，在此之上借助动态窗口法选择最佳速度来避免局部未知障碍物。实验表明，该混合路径规划算法的运行速度更快，效率更高。

1.2 智能仿生学的路径规划算法

对于处理复杂环境下的路径规划问题时，科学家们学会从大自然获取灵感，智能仿生学算法就是人们通过仿生学研究而发明的算法，常用的有蚁群算法、遗传算法、粒子群优化算法等。

1.2.1 蚁群算法

蚁群算法(Ant Colony Optimization，ACO)是Dorigo等[19]提出的一种智能优化算法，仿生学家发现蚂蚁通过一种叫作信息素的物质在个体间传递信息，蚂蚁可以感知这种物质，从而指导方向。蚁群算法的基本原理如图1所示，当大量蚂蚁采取集体行动时，通过蚂蚁路径越多，留下的信息素就越多，这就是正反馈过程，新蚂蚁选择较短路径的可能性越大，最后蚁群可以找到食物来源与巢穴之间的最短路径。有些蚂蚁不会一直重复这样的路径，也会去寻找更好并且更短的路径，吸引其他蚂蚁过来，重复这个过程就会得到一条最优路径。蚁群算法就是通过迭代来模拟蚁群觅食行为来完成寻找最短路径。

图1 蚁群寻找食物示意图

蚁群算法具有信息正反馈机制、较强的鲁棒性和便于并行实现等优点，但是在初期如果信息素缺少或者路径问题规模太大，则会导致路径规划速度过慢。蚁群算法设置参数不准确，同样会导致求解速度慢且所得解并不是全局最优解，陷入局部最优问题。

Wang等[20]针对蚁群算法存在的问题，首先采用网格法对于障碍物进行环境建模，在考虑无人水面艇的运动特性的同时，通过蚁群算法进行全局路径规划，仿真实验表明该算法达到了预期目标，能够有效地寻找到最优路径。尚明栋等[21]针对传统蚁群算法的早熟和停滞现象，在起点和目标点之间设定一个坐标夹角，每次移动时都选择和初始目标角度相同或相近的角度进行下一次移动，在参数设置中通过增加方向角权值来改进下一个节点的概率选择，同时信息素的更新通过动态变化来进行。仿真表明，改进算法的搜索速度和全局搜索能力都有了显著提升，最后得到的路径更短且平滑。

1.2.2 遗传算法

遗传算法(Genetic Algorithms，GA)是Holland[22]根据自然界生物进化过程而提出的随机化搜索算法，来源于进化论和遗传学理论，已经成为一个多学科、多领域的重要研究方向。基于遗传算法的避障路径规划流程如图2所示，使用适者生存原则，通过复制、交叉、突变等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解，增加适应度函数值高的解，从而获得最优路径。

图2 基于遗传算法的避障路径规划流程图

遗传算法具有较强的鲁棒性，适合求解复杂路径的优化问题，应用较为广泛。但是其收敛速度慢，局部搜索能力差，控制变量较多，寻找可行解的能力较弱，易于产生早熟现象，规划合理的避障路径花费时间过久。

Naeem等[23]基于Wiener-Hammerstein模型，使用遗传算法对无人水面艇进行路径规划，该算法已经成功应用在Springer号无人水面艇上，具有实用性。Praczyk等[24]设定无人水面艇一般情况下由人员远程操作，连接不稳定时使用遗传算法进行紧急路径规划,实验发现无论是简单区域还是复杂盆地区域都能保证无人水面艇的安全。但这种方法只作为紧急后备选择，没有进一步考虑复杂的障碍物情况。Long等[25]针对遗传算法收敛速度慢的问题，采用网格法的环境建模方法，提出一种新的初始种群方法，提高初始种群的收敛速度和初始种群质量，设计自适应交叉概率和变异概率，使得生成的路径相比于传统遗传算法更短，实验仿真证明了其安全性和可行性。曾凡明等[26]针对遗传算法无法使用系统反馈信息，造成大量无效迭代，最终导致无法求得精确解的问题，采用遗传算法来生成蚁群算法中的信息素分布，确保了信息素的快速生成，采用蚁群算法进行求解，确保解的准确性，实验证明改进算法生成的路径的鲁棒性和准确性进一步提升。

1.2.3 粒子群优化算法

粒子群优化算法(Particle Swarm Optimization，PSO)是Eberhart等[27]根据飞鸟集群觅食行为发明的一种进化计算算法。该算法是基于群体的，将鸟看成一个个粒子，这些粒子同时拥有速度和位置属性，单个粒子根据找到食物最近路径分享给群体，同时比较群体中的最近路径从而改变路径，多次迭代后整个群体就找到最优路径。粒子群算法的数学模型描述如下：

假设D维搜索空间里存在n个粒子，第i个粒子表示为Xi={xi1,xi2,…,xiD},它有最好适应值的位置表示为pbesti={pi1,pi2,…,piD}，所有粒子有最好适应值的位置表示为gbest={g1,g2,…,gD},粒子i的速度记作Vi={vi1,vi2,…,viD}。同时根据下列公式更新每个粒子的速度和位置：

Vid(t+1)=wvid(t)+c1rand()·[pid(t)-xid(t)]+

c2rand()[gd(t)-xid(t)] 1≤i≤n,1≤d≤D

(2)

x(t+1)=x(t)+v(t+1)

(3)

式中：w为惯性权重；rand()为[0,1]范围内的随机值；c1和c2为加速常数。

粒子群优化算法和遗传算法相类似，但是没有遗传算法的交叉变异等过程，它的特点是追踪单个粒子和群体信息共享去寻找最优解。粒子群优化算法具有搜索速度快、计算较为简单和具有记忆性等优点，但是会产生早熟收敛和陷入局部最优等问题。

杜开君等[28]为了避免粒子群算法陷入局部最优问题，提出一种基于国际海上碰撞规则的无人水面艇的动态避障方法。采用极坐标进行建模，对于障碍物采用圆形或者有向包围盒进行简化，考虑了无人水面艇运动特性，算法将海事规则作为约束条件之一，将粒子群算法引入无人水面艇的避障规划之中，实验证明算法满足要求。Zhang等[29]针对粒子群算法存在的问题，提出基于极坐标建模的改进粒子群优化算法，在种群初始化方法中引入β分布、改进惯性因子更新方法，在粒子速度更新方面加入差分进化的思想，仿真实验验证了算法的有效性。郑佳春等[30]为了应对粒子群优化算法的粒子飞行速度问题，引入模拟退火机制来更新粒子群优化算法中粒子的速度和位置，使得PSO算法可以跳出局部极值区域，收敛到全局最优粒子群解，仿真实验证明该改进算法可以在复杂海域条件下安全快速进行路径规划。

1.3 对比分析

全局路径算法之间的比较及其改进方法如表1所示。除此之外，还有模拟退火算法、模糊逻辑算法、禁忌搜索算法、神经网络算法[31-32]等全局路径规划算法在机器人领域应用广泛，但是在无人水面艇的路径规划中应用较少。

表1 全局路径规划算法特点与改进方法

续表1

基于图形法的路径规划算法一般要与环境建模中的地图构建集成使用，但是无人水面艇处于水上环境，接收到的传感器信息有限且易受干扰，在地图网格数量较大时，很难处理动态障碍物信息，不能保证路径规划的实时性。因此图形学的路径规划算法要在地图网格数量和路径规划实时性上寻求一定平衡。

智能仿生学的路径规划算法克服了传统路径规划算法的部分缺点，具有很好的鲁棒性，路径规划速度也得到进一步提升。但对于输入激励与抑制的设定存在一定人为的不确定因素，在寻找路径的过程中易陷入局部最优的问题，如蚁群算法和粒子群优化算法；存在参数设置过于繁多的问题，比如遗传算法。

2 局部路径规划算法

局部路径规划是指在未知或部分未知的环境下通过传感器获取周围环境的信息，包括障碍物的尺寸、形状和位置等信息，并使无人水面艇自主获得一条安全可行的最优路径。局部路径规划算法主要有人工势场法、动态窗口法、速度障碍法、快速扩展随机树算法等。

2.1 人工势场法

Khatib[33]提出的人工势场理论(Artificial Potential Fields,APF)是避障规划中使用最广泛的算法之一。人工势场法的主要思想如图3所示，首先用一个抽象的人造势场进行环境搭建，该势场由引力场和斥力场构成。引力场由目标点位置产生并作用于无人水面艇，势场向量方向由无人水面艇指向目标点；斥力场由环境中障碍物产生，势场向量方向由障碍物指向无人水面艇。无人水面艇环境空间的总势场为引力场和斥力场共同叠加作用，最终通过二者的合力控制无人水面艇来完成避障操作，到达目标点。

图3 人工势场法示意图

人工势场法具有实时性高、反应迅速和计算简单等优点，但是运动过程中如果某个点的合力为零，无人水面艇则不可以绕过该点，这就存在局部最小值问题。且当目标被障碍物包围时，路径不能收敛，无人水面艇同样无法到达目标点。

Xie等[34]为减少人工势场法局部最小问题的影响，对吸引力函数和斥力函数都进行改进，增加了一个调节因子，当无人水面艇接近目标时，该调节因子控制下降的吸引力函数是线性函数，同时规定斥力是一个降低的高阶函数，实验证明改进的人工势场法能使无人水面艇到达目标点。Wang等[35]针对人工势场法局部最小问题，在排斥力场函数中增加无人水面艇与目标点之间的距离，并定时检测无人水面艇是否进入了局部最小点，通过增加这两个因素去改进人工势场法，可以让无人水面艇安全地避免局部最小点问题，仿真结果证明该改进算法可以有效帮助无人水面艇成功避免动态障碍物。Wu等[36]针对人工势场法存在的问题，提出在人工势场里面将斥力分解成两个分力，并使一个分力处于引力的反方向，称之为角度势场，进一步与全局蚁群算法相结合，在不同环境下应用此改进算法进行实验，进一步提高安全性。

2.2 向量场直方图法

向量场直方图法(Vector Field Histogram，VFH)是Borenstein等[37]针对人工势场法的目标点附近有障碍物时很难到达目标点这一问题提出的一种实时的路径规划算法。它的主要思想是将无人水面艇所处环境建立局部栅格地图，同时计算每个方向USV的前行代价，这个方向的障碍物越多，相应的前行代价也就越大，根据代价值的不同建立直方图，选择最低代价的方向前进，同时引入一个平衡函数来平衡最低代价与目标方向，最终确定最优避障路径。

向量场直方图法计算高效，具有较好的鲁棒性，适用于多障碍物避障，但是没有考虑USV自身的动力学与运动学。有学者在其基础上提出VFH+和VFH*算法。Loe[38]将VFH算法应用于无人水面艇的局部路径规划中，并设定了多种障碍情景，发现VFH算法在简单的多障碍物情景下表现良好，但是在更加复杂的环境中也有可能陷入局部最优问题，故将VFH算法与A*算法相结合，即引入VFH*算法应对复杂环境的局部路径规划。同时将VFH算法与快速扩展随机树算法相结合，能够快速寻找到最优安全路径。魏新勇等[39]针对USV自身是一种椭圆形，直接使用VFH*算法会造成USV尾端碰撞的问题，提出一种结合激光雷达进行前后数据融合的USV的环境建模，使得USV能够准确避让检测到的障碍物，再通过建立直方图和代价函数选出最终的避障路径方向。仿真实验证明，该方法能够有效避免尾部相撞和陷入局部最小化等问题，完成局部避障。

2.3 动态窗口法

动态窗口法(Dynamic Window Approach,DWA)是Fox等[40]提出的一种在线避障算法，主要依靠实时探测的局部信息，以滚动的方式进行在线规划，用启发式方法生成优化子目标，随着窗口不断滚动不停地获得新的局部信息，然后在滚动中实现优化与反馈的结合，最终实现局部路径规划的规划。

唐平鹏等[41]针对动态窗口法的问题提出无人水面艇分层策略将动态窗口分解为艏向窗口和线速度窗口,使用切线法和弧线法分别从艏向窗口和线速度窗口中求出规避角速度和线速度，并引入角速度缓冲模型以提升规划过程中艇体的稳定性。湖面实验表明该改进算法有着很好的适应能力，增强了无人水面艇行驶能力的安全性。Lin等[42]提出未知环境下基于动态窗口的避障方法，由于无人水面艇不能像陆地机器人那样快速转向或改变速度，需要一定的响应时间，并且还需要满足无人水面艇的最小旋转直径的要求，所以加入控制周期(T0)以确保无人水面艇能够快速安全地避开障碍物，以满足避障要求。使用扩展障碍物的方法，就是用圆形或矩形体根据其纵横比来表示不同的障碍物，合理地简化了障碍物的形状，减少了消耗量的计算，缩短了计算时间。该改进方法考虑到复杂的多种动、静态障碍物，实验中设计三种不同的应用场景，不管是单个障碍物还是多个障碍物都可以实时完成避障要求，具有适应真实复杂环境的能力。

2.4 速度障碍法

速度障碍法(Velocity Obstacle，VO)是Fiorini等[43]提出的一种局部避障算法，在无人水面艇与障碍物之间在速度空间构建一个三角区域，只要速度向量落入到此三角区域内则判定二者会发生碰撞，若要进行避障必须从非三角区域中找一个最优的速度矢量，从而找到最优路径。

速度障碍法的基本原理[44]如图4所示，设定无人水面艇的位置向量为PA,障碍物B“膨化”之后的位置向量为PB,为了将USV简化成一个质点，将USV椭圆的长半轴分别叠加到障碍物的半长轴和半短轴上。图中VA为USV的速度向量，VB为动态障碍物的速度向量，VBA为USV相对于动态障碍物的速度向量。

VBA=VA-VB

(4)

图4 速度障碍法示意图

将障碍物看作是静止的，λL和λR分别是USV与障碍物的2条切线，当USV发出沿着VBA方向的射线λBA与障碍物相交时，则判定USV将来会与障碍物发生碰撞危险。定义USV与障碍物发生碰撞的相对速度VBA的集合是速度空间中的相对碰撞区：

RCCAB={VBA|λBA∩B≠∅}

(5)

式中：RCCAB是λL和λR之间的区域范围。定义在USV的绝对速度空间里，会让USV与障碍物发生碰撞的速度VA的集合为速度障碍VOAB：

VOAB=RCCAB⊕VB

(6)

式中：⊕是闵可夫斯基向量和运算。VOAB相当于RCCAB沿着VB方向移动，当USV的速度向量VA落在该区域，USV与障碍物会发生碰撞。

吴博等[45]考虑外界风浪的影响和无人水面艇的运动特性，将速度障碍法应用到无人艇避障规划中，计算无人水面艇和障碍物的相对距离，分析二者的相对速度和相对位置关系，得出符合无人水面艇控制要求的可行路径，提高行驶安全性。Kuwata等[46]针对速度障碍法没有考虑动态障碍物的动态变化的问题，提出速度障碍法服从国际海上避碰规则，通过识别障碍物，判断无人水面艇应该通过障碍物的哪一侧方向，保证了在动态海洋环境下的安全避障。通过相对速度计算无人水面艇到障碍物最接近目标点的距离和时间，满足约束条件时则判定无人水面艇与障碍物发生碰撞。构建一个代价函数，为使代价函数最小，在可行速度空间找一个速度向量作为避障的速度向量，最后生成可行路径。该改进算法已实际应用于无人水面艇的目标跟踪任务中。

2.5 碰撞锥方法

碰撞锥方法(Collision Cone Approach,CCA)是Chakravarthy等[47]提出的一种用来分析两个运动物体之间的碰撞关系的理论，根据USV与障碍物之间的地理位置，实时计算出两者可能发生碰撞的危险区域并在避障路径进行规避，如果不会发生碰撞则按原来路径前进。该算法具有模型简单、实时性高、应用广泛等优点，对于静态障碍物和动态障碍物都能快速给出高安全的避障路径。

碰撞锥方法和速度障碍法都是基于碰撞锥理论，防止无人水面艇进入到与障碍物碰撞的范围内。但是速度障碍法考虑到了无人水面艇禁止使用的不同速度向量，同时也可能包括不同的方向。碰撞锥方法考虑禁止无人水面艇的航行方向，无人水面艇和障碍物都是恒定速度航行，其还可对非圆形障碍物进行避障。

Pu等[48]针对一般路径规划算法将障碍物进行圆形建模的问题，同时考虑到大多数动态船只会成为障碍物，提出一种基于椭圆碰撞锥方法的无人水面艇路径规划算法，进一步提出点与椭圆的碰撞锥计算方法，可以计算出无人水面艇与动态船只之间的碰撞角度范围，同时结合国际海上避碰规则从而获取到避障角度，完成避障后还可回归到原始路径继续前进。实验证明该算法能够精准有效地完成无人水面艇的避障要求。吉大海等[49]针对速度障碍法适用于低速航行的不足，提出一种无人水面艇在高速情况下的基于行为的危险规避路径规划算法。首先使用碰撞锥理论判断无人水面艇与障碍物的位置关系，然后将形成的碰撞约束和国际海上避碰规则约束相结合，转换成对无人水面艇避障行为的约束，最终以USV航行角度和线速度优化问题来获得避障路径。仿真实验证明，改进后的混合算法能让高速航行的USV完成动态障碍物的避障。

2.6 快速扩展随机树算法

快速扩展随机树算法(Rapidly-exploring Random Tree,RRT)由Lavalle[50]提出，采用树结构代替有向图结构，在规定控制率时，通过对状态空间的采样点进行碰撞检测，避免空间建模，应用于高维多自由度机器人在复杂环境下的路径规划问题。

快速扩展随机树算法主要思想是迅速减小一个随机选择的节点到树的距离，直到满足预期要求，最终目的就是找到一条从根节点到目标点的可行路径。基本快速扩展随机树算法构建过程如图5所示，RRT算法在高维环境下的路径规划中应用广泛，但在全局空间下均匀搜索，导致时间花费过久，造成资源浪费，实时性较差，而且随机采样点缺乏可重复性，最终可能导致生成的路径不是最优路径。

图5 基本快速扩展随机树算法构建过程

庄佳园等[51]针对RRT算法耗时长、无法满足实时性要求的问题，提出一种基于RRT的局部路径规划算法。针对无人水面艇的航行特点，对传统RRT算法进行了改进，以海上和湖上实际雷达图像进行环境建模，改进生长点选择使树朝着最有利方向生长，改进探索点的选择使得规划轨迹接近最优轨迹。最后对航线进行优化，去除多余航线点。实验表明优化后的路径更适合无人水面艇的控制要求，进一步提高了USV局部路径规划的速度。Chen等[52]针对RRT算法只可设定一个目标点问题，提出一种用于无人水面艇多点路径规划的RRT算法，对于单个目标航行点的时候可以快速产生航行路线。但是对于多个预设的目标点时，将目标点动态调整为沿路的航线点，并且在RRT树的生长过程中动态刷新树的节点信息，使得航行路线可以通过所有航行点。同时在每个路径段都加入路径平滑算法，与A*算法相比，可以较短时间完成避障路径规划。

2.7 对比分析

局部路径规划算法的优缺点与其改进方法如表2所示。此外还有Bug算法、曲率速度法、接近图法、ASL法、梯度法等经典局部路径规划算法已经在自主机器人领域得到广泛应用，但在无人水面艇领域的应用较少。

表2 局部路径规划算法特点与改进方法

续表2

人工势场法根据传感器信息获得局部障碍物信息，多用于局部静态障碍物的路径规划，在目标点附近没有障碍物时，其规划速度和规划准确度最佳。向量场直方图法针对局部最优问题提出改进，更适合多障碍物情形下的避障。动态窗口法和速度障碍法更适用于局部动态障碍物的路径规划处理，考虑无人水面艇方向空间和速度空间的危险规避，但是对于无人水面艇的控制也提出更高的要求。碰撞锥方法实时性高，适用于非圆形障碍物避障。快速扩展随机树算法大多应用于高维环境下的路径规划，更符合海洋环境下的无人水面艇避障路径规划。

上述全局路径规划算法和局部路径规划算法都符合无人水面艇的避障路径规划要求，大部分文献提出的改进算法忽略了洋流、风浪等外界环境的影响，其环境建模还需要进一步完善。由于无人水面艇处于海洋环境，和陆地机器人行动不同，这些算法也忽略了无人水面艇的运动特性即在海洋中实际转向能力。

3 结 语

随着控制技术的进一步发展，无人水面艇的应用场景越来越丰富，为了进一步发展无人水面艇，必须对现阶段的无人水面艇的不足进行改进，但是没有一种单一算法可以在任意的环境下准确有效避障，故未来还需对以下几方面展开研究：

(1) 进一步完善现有路径规划算法的实用性。对于无人水面艇的环境建模，必须通过具体测量或者使用准确的电子海图去获得比较可靠的数据，考虑水流、风浪等外界环境的影响，利用获得的数据对模型进行验证。在规划海洋环境避障路径时，无人水面艇必须考虑国际海上避碰规则，因为可能与真实船舶进行实时避障，只有共同遵循规则才能确保双方船只航行安全，完成安全避障。在无人水面艇进行避障行动的时候必须考虑无人水面艇自身的运动特性，与陆地机器人的运动不同，由于水流的特性，无人水面艇的运动路径可能存在一定的偏移和误差，必须考虑其旋转半径，根据无人水面艇的实际转向能力，适当“膨胀”无人水面艇与障碍物之间的距离，引入安全距离的概念，才能产生实际可行的避障路径。

(2) 新的路径规划算法。近年来，智能算法得到了极大的发展，出现许多新的人工智能方法和新的数理方法，这些算法在其他无人机器设备上得到很好应用，但在无人水面艇路径规划上还没有发挥应有的优势，可以研究将传统路径规划算法与智能算法相融合，寻求可以克服现有方法缺点的新的路径规划算法，以期得到未知环境下的适应性更好的动态避障组合算法。

(3) 多无人水面艇协同工作。多无人水面艇协同工作也是目前新的研究方向，多机器人协同工作在很多领域中已经十分常见，比如物流公司多个无人机器小车协同搬运快递、无人机的飞行编队和水下机器人的合作搜救与观察等，其中涉及运动控制算法、编队算法问题和多机器人之间的通信问题，将路径规划算法与运动控制算法相结合，在实践中进一步完成更多未知环境下的避障路径规划。

(4) 路径规划算法和底层控制。对于无人水面艇的导航避障问题，路径规划问题只是其中重要一环，传感器及控制器的工作也是其中重要问题之一。路径规划算法为无人水面艇提供可行航线，但是具体操作需要传感器与控制器来完成。大部分路径规划算法在模拟实验中的仿真验证表明了算法的可行性，但是理论研究最终还是要应用于实际，在真实环境中使用这些算法还需要进一步的研究与改进。