0 引　言

随着海洋资源开发与智能航运的快速发展，无人船（Unmanned Surface Vehicle, USV）在环境监测、海上救援、军事侦察等领域展现出重要应用价值^[1]，因此要求无人船具备强大的自主航行能力，而路径规划是实现无人船自主航行的重要基础^[2]。

路径规划旨在通过某种算法，规划出从起点到目标区域满足自身约束条件的无碰撞路径^[3]。目前，常见用于无人船路径规划的算法有A*算法^[4]、粒子群（Particle Swarm Optimization, PSO）算法^[5]、快速扩展随机树（Rapidly-Exploring Random Tree, RRT）算法^[6]等。其中，RRT算法因具备搜索能力强、适用范围广等优点被广泛应用于无人船路径规划^[7]。但由于RRT算法的随机采样方式和固定步长特性，用于路径规划时易导致路径冗余较大、质量不佳等问题^[8]。对于RRT算法的缺陷，不少学者对其进行了改进。Hu等^[9]针对传统RRT算法存在的搜索速度慢、拐点多等问题，将动态因子α融入算法中，提出一种启发式搜素RRT算法，最后利用三阶贝塞尔曲线对路径平滑处理，结果表明改进后算法有效提升了搜索效率和路径平滑性；Gu等^[10]针对RRT算法应用于船舶路径规划时存在的收敛慢、拐点多、路径不平滑等问题，通过偏置采样提出基于指导区域的采样策略，增强算法目标采样导向性，同时利用改进DP算法对路径平滑处理，实验表明改进算法能够平衡算法效率和准确性，得到平滑的路径；Chen等^[11]为解决RRT算法结合无人船路径规划时存在的随机性强、路径易曲折的问题，在传统算法中引入扇区采样策略来约束转向角度，利用动态步长策略加速搜索，仿真实验表明改进后算法能够平衡搜索效率、路径长度和平滑度，更适合船舶航行规律；李军涛等^[12]针对RRT算法在无人艇航迹规划时存在的效率低、计算量大等问题提出一种改进RRT算法，该算法通过引入概率值来增加目标采样的导向性，然后融合APF算法加快算法搜索，改进后算法效果提升明显；李光宇等^[13]通过在RRT算法中引入目标引力思想，提出一种应用于水下机器人路径规划的改进RRT算法，实验表明改进算法在节点数以及路径长度方面有明显优势；曲胜等^[14]利用RRT算法探索能力强的特点，将APF算法改进的势场函数融入到RRT算法中，提出APR-RRT算法，实验表明改进后算法效率更高，具备使无人船向目标点前进且远离障碍物的能力。

综上所述，现有研究中对于传统RRT算法的改进主要集中在采样方式和扩展步长2个方面，在一定程度上提高了算法效率和路径质量，但在路径平滑方面研究较少。因此本文以现有研究为基础，提出一种改进RRT算法。该算法将贝叶斯优化算法引入目标点采样过程，增强目标点采样的导向性；通过动态步长和路径剪枝提升搜索效率和路径质量。此外，文中考虑到当前多数无人船采用欠驱动设计，对路径平滑度要求较高，因此提出一种动态权重的3次B样条函数用于提高路径平滑度。最后为更加真实地反映无人船在海域环境下的路径规划表现，利用Matlab在3种障碍物环境下，对3种算法进行仿真实验。实验结果表明了改进RRT算法的可行性和优越性。

1 相关算法介绍 1.1 RRT算法基本原理

RRT算法最初由LaValle在1998年提出，主要用于解决机器人运动规划问题^[15]。研究表明，RRT算法适用于低维和高维空间，同时能够在复杂障碍物环境中高效地找到可行路径，因此在无人车、无人船等自动控制载具上具有广泛应用^{[16 − 17]}。

RRT的核心思想是通过随机采样和树形扩展来探索机器人的配置空间（即所有可能的运动状态）。算法从起点出发，通过随机生成节点形成一棵树，直到扩展至目标点^[18]。树的节点代表无人船的可能位置，边代表无碰撞的运动路径。RRT算法原理图见图1。

1.2 贝叶斯优化算法基本原理

贝叶斯优化（Bayesian Optimization, BO）算法是一种基于概率模型的序列优化方法，贝叶斯优化由代理模型和采集函数2个部分组成，代理模型用于对目标函数进行建模，采集函数则通过权衡预测值和方差来度量未知点的采样价值^[19]。

贝叶斯优化算法收敛效果的关键影响部分为采集函数，目前以期望提升准则（Expected Improvement，EI）为代表的采集函数应用广泛^[20]，期望改进（EI）准则的数学表达式由2个加和项构成：第一项对应局部开发特性，第二项对应全局探索特性^[21]。其形式如下：

$ \begin{split} {{EI }}(x) =&\left[ {m(x) - {f_{{\text{max}}}}} \right] \cdot {{\Phi }}\left(\frac{{m(x) - {f_{{\text{max}}}}}}{{\sigma (x)}}\right) + \\ &\sigma (x) \cdot \phi \left(\frac{{m(x) - {f_{{\text{max}}}}}}{{\sigma (x)}}\right)。\end{split} $

(1)

式中：$ {f_{{\text{max}}}} $为当前最大观测值；$ m{\text{(}}x{\text{)}} $和$ \sigma {\text{(}}x{\text{)}} $分别为贝叶斯模型预测的均值与方差。

2 改进RRT算法介绍 2.1 贝叶斯优化的混合采样策略

传统RRT算法进行目标点采样时存在随机性过强的问题，在障碍物密集或解空间狭窄时易产生大量无效扩展，导致算法求解效率低。为此，本文引入贝叶斯优化算法的混合采样方法对采样过程进行建模和引导，实现一种具备目标导向性和环境适应性的智能采样策略。贝叶斯优化的核心在于使用历史采样数据来更新高斯过程回归模型，并使用采集函数选出下一个最优采样点。

具体采样过程如下：

1）采样评分模型构建。首先定义一个采样评分函数f(x)，用于度量某一采样点x的“采样价值”，“采样价值”与评分函数值成正比。该函数综合考虑采样点与目标点距离、与障碍物的安全距离以及路径角度变化3个因素，评分函数为：

$ f{\text{(}}x{\text{)}} = - \alpha \cdot D(x,{x_{{\text{goal}}}}{\text{)}} + \beta \cdot C(x{\text{)}} + \gamma \cdot S(x)。$

(2)

式中：$ D(x,{x_{{\text{goal}}}}{\text{)}} $为采样点到目标点的欧氏距离；$ C(x{\text{)}} $为采样点与最近障碍物之间的最小距离；$ S(x{\text{)}} $为采样点与其最近树节点间形成路径的夹角平滑度指标；$ \alpha $、$ \beta $和$ \gamma $为各因子的权重系数，三者取值分别为0.4、0.3和0.3，该组参数通过多次预实验获得，能够在搜索速度与安全性之间取得较好平衡。

2）贝叶斯优化建模采样函数。将评分函数f(x)看作黑盒函数优化问题，使用高斯过程回归（GPR）作为先验模型，定义为：

$ f(x)\sim GP{\text{(}}m{\text{(}}x{\text{),}}k(x,x'))。$

(3)

式中：$ m{\text{(}}x{\text{)}} $为均值函数，设置为0；$ k{\text{(}}x{\text{,}}x'{\text{)}} $为核函数，本次使用径向基核（RBF核），即

$ k(x,x' ) = {\text{exp}}\left( { - \frac{{\parallel x - x' {\parallel ^2}}}{{2{l^2}}}} \right)。$

(4)

式中：$ \parallel x - x' {\parallel ^2} $为输入点之间的欧氏距离平方；$ l $为长度尺度（length-scale），控制函数的平滑程度。

3）采集函数设计。将采样视为优化问题，通过贝叶斯优化预测评分函数f(x)的分布，并在当前采样历史中选取最有前景的新采样点。使用“期望改进（Expected Improvement, EI）”作为采样准则，即

$ {{EI}}(x) = \left[ {m(x) - {f^ + }} \right] \cdot \Phi(z) + \sigma (x) \cdot \phi (z) ，$

(5)

$ z = \frac{{m(x) - {f^ + }}}{{\sigma (x)}} 。$

(6)

式中：$ m{\text{(}}x{\text{)}} $和$ \sigma {\text{(}}x{\text{)}} $分别为贝叶斯模型预测的均值与方差；$ {f^ + } $为当前评分函数最大值；$ \Phi ( \cdot ) $和$ \phi {\text{(}} \cdot {\text{)}} $为标准正态分布的累积分布函数与密度函数。

最终把$ {{EI(}}x{\text{)}} $最大值出现的位置作为采样点，有

$ {x_{{\text{sample}}}} = {\text{argmax}}EI(x{\text{)}}。$

(7)

式中：函数argmax表示让某个函数取得最大值的输入变量。

4）采样方式。为平衡采样时的目标导向性与探索性，本文采用贝叶斯采样与随机均匀采样的混合策略，定义如下：

$ {{x}_{\text{rand}}=\left\{ \begin{aligned} &{贝叶斯采样，\;概率为p}，\\ &{随机均匀采样，概率为1-p}。\end{aligned} \right.}$

(8)

式中：p的范围为[0.6, 0.9]，多次实验表明p取值为0.75时，能更好地提高算法采样效率和环境适应性。

2.2 自适应动态步长策略

利用传统RRT算法进行路径规划时，随机树的生长步长是固定的，步长过长或过短都会影响算法搜索效率^[21]。针对以上问题，对算法引入自适应动态步长，使路径扩展过程具备“初期快速探索、后期精细收敛”的能力。

在动态步长策略的引导下，扩展步长受目标点距离和障碍物密度的双重影响，具体过程为：1）在远离目标点时使用较大步长加快搜索速度，靠近目标点时减小步长以提高搜索精度；2）在障碍物密集区域自动减小步长，避免碰撞。

自适应动态步长计算式为：

$ {l_k} = {l_{\min }} + \left( {{l_{\max }} - {l_{\min }}} \right) \cdot \left( {{\lambda _1} \cdot {e^{ - \alpha \cdot \frac{{{d_{{\text{goal}}}}}}{{{d_{\max }}}}}} + {\lambda _2} \cdot {e^{ - \beta \cdot {\rho _{{\text{obs}}}}}}} \right)，$

(9)

$ {\rho _{{\text{obs}}}} = \frac{1}{{1 + \exp ({\text{μ }} \cdot {d_{{\text{nearest}}}})}}。$

(10)

式中：${l_k}$为第k次扩展时的步长；${l_{\min }}$和${l_{\max }}$分别为步长范围的下限和上限；${d_{{\text{goal}}}}$为当前节点到目标点的欧氏距离；$ {d_{{\text{max}}}} $为搜索空间对角线长度，用于归一化；${\lambda _1}$和${\lambda _2}$为加权因子且满足${\lambda _1} + {\lambda _2} = 1$；$\alpha $和$\beta $为衰减系数，控制对距离与密度的敏感程度；$ {\rho _{{\text{obs}}}} $为当前节点周围的障碍物密度；${{\mu }}$为控制密度变化速率的参数；${d_{{\text{nearest}}}}$为当前节点与最近障碍物边缘之间的欧式距离。为更好地提高算法效率，大量预实验表明当${\lambda _1}$、${\lambda _2}$、$\alpha $、$\beta $和${{\mu }}$取值分别为0.35、0.65、2.0、5.0和1.5时能充分平衡算法的扩展速度和精度。

2.3 双向贪心剪枝策略

利用上述3种策略对传统RRT算法进行改进后，规划的路径大部分为锯齿状，不符合无人船航行要求，同时会产生冗余路径。因此本文引入双向贪心剪枝策略优化冗余路径，具体过程为：1）初始化：初始化路径节点集合，设定起点和终点；2）正向剪枝：从起点开始，依次跳跃到下一个节点；3）反向剪枝：同时从终点出发，依次回退到前一个节点；4）碰撞检测：每一次跳跃后，将当前节点与前一个剪枝断点进行连接，执行碰撞检测。若连线不与任何障碍物相交，则继续向前或向后跳跃；若连线发生碰撞，则将此段的前一节点或后一节点标记为“剪枝断点”；5）剪枝终止条件：当正反2个剪枝方向的连线末端相遇或重合时，停止剪枝过程，最后更新路径。

双向路径剪枝过程示意图如图2所示。图中，虚线为原始路径，实线为剪枝后路径。

2.4 路径平滑策略

执行双向贪心剪枝策略后，能够得到更短、更高效的航行路径，但在剪枝断点处仍存在转弯点，目前市面上的无人船大多为欠驱动，较多转弯点不利于欠驱动无人船航行。因此需要对路径平滑处理，由于三次B样条曲线具备平滑性好、可控性强等优点被广泛使用，然而经大量实验后发现传统三次B样条曲线用于路径平滑时存在以下缺陷：1）对所有控制点一视同仁，无法判断控制点权重而出现“过度平滑”现象，容易导致平滑后路径长度增加过多，如图3(a)所示；2）在复杂环境中，大角度转弯点处路径进行拟合平滑后易与障碍物发生碰撞，如图3(b)所示。

为解决上述问题，在三次B样条曲线中引入由局部转弯角度和障碍物距离双重因素作用的动态权重$ {w_i} $，提出一种改进的三次B样条曲线。

标准三次B样条曲线的数学表达式^[22]为：

$ P\left(u\right) = {\sum }_{i=0}^{n}{P}_{i}\cdot {N}_{i,3}\left(u\right)。$

(11)

式中：$ {N_{i ,3}}\left( {{\mkern 1mu} u} \right) $为第i个三次B样条基函数，且自身满足归一性，即$ \sum _{i = 0}^n{N_{i ,3}}\left( {{\mkern 1mu} u{\mkern 1mu} } \right) = 1 $；$ {P_i} $为控制点；$ u \in [{u_3}, {u_{n + 1}}] $，即在节点向量范围内。

从标准三次B样条曲线表达式出发，对每个控制点引入动态权重$ {w_i} $后，三次B样条表达式为

$ P\left(u\right) = {\sum }_{i=0}^{n}{w}_{i}\cdot {P}_{i}\cdot {N}_{i,3}\left(u\right)。$

(12)

观察式(10)可发现，对控制点加入动态权重后可得$ {\mathop {{N}_{{i}}}\limits^\sim }(u) = {w_i} \cdot {N_{i,3}}(u) $，此时加权基函数总和就不再等于1，因此需要归一化处理以恢复插值的几何合理性，最终引入动态权重的三次B样条曲线表达式：

$ P\left(u\right) =\frac{{\displaystyle\sum }_{i=0}^{n}{w}_{i}\cdot {P}_{i}\cdot {N}_{i,3}\left(u\right)}{{\displaystyle\sum }_{i=0}^{n}{w}_{i}\cdot {N}_{i,3}\left(u\right)} 。$

(13)

为使平滑后路径既能保持必要的几何形状，又能有效避障，将动态权重$ {w_i} $定义为：

$ {{w_i} ={w_{{\text{min}}}} + {\text{(}}{w_{{\text{max}}}} -{w_{{\text{min}}}}{\text{)}} \dfrac{1}{{1 + {\text{exp}}\left( { - \dfrac{a}{{1 + \dfrac{{{\theta _i}}}{{\text{π}}}}} \cdot {\text{exp}}\left( { - \dfrac{b}{{{d_i} + \varepsilon }}} \right)} \right)}} 。}$

(14)

式中：$ {\theta _i} $为第i个控制点处的转弯角度，$ {d_i} $为其与最近障碍物的欧式距离；$ {w_{{\text{min}}}} $和$ {w_{{\text{max}}}} $分别为权重最小值和最大值，设置为0.3和1.0；a、b分别为转角调节系数和避障调节系数，ε为避免除零的常数，为平衡路径平滑度和安全性，多次实验表明三者的数值分别取4、2和10⁻³时效果更佳。

式(14)中通过嵌套指数函数和Logistic函数来控制权重在最大值和最小值之间变化。当路径较平坦时，控制点处转角较小，此时权重$ {w_i} $的值较大，平滑后路径能够更贴合原始路径，避免平滑过度；当控制点处转弯较大，即转角较大时，$ {w_i} $的值减小，让路径更自由、更平滑，同时会根据障碍物距离调整权重大小，充分平衡路径的平滑性与安全性。

为验证改进后算法的合理性与适用性，在Matlab中用改进前后2种三次B样条曲线对贪心剪枝后的路径进行平滑实验，相同环境下进行多次实验后随机选出1组三次B样条平滑失败仿真图和改进后样条平滑成功仿真图，如图4所示；实验数据如表1所示。

图4中，虚线为RRT算法贪心剪枝后的路径，实线为平滑后路径，图4(a)中①处发生碰撞导致平滑失败。根据表1数据，改进后三次B样条曲线平滑的路径平均曲率更小，说明路径更平滑；改进后样条平滑的路径在小转角路段中贴合度明显更高，能够避免平滑后路径长度增加；动态权重的样条曲线平滑成功率为100%，高于改进前27.79%，能有效避开障碍物。

实验表明，将动态权重三次B样条曲线融入RRT算法后，能有效提升RRT算法路径规划效果，充分平衡路径平滑度和安全性。

2.5 改进算法流程

在RRT算法的基础上，引入混合采样、自适应动态步长以及双向贪心剪枝3种策略，帮助RRT算法更高效地找到初始路径，然后引入加权三次B样条曲线对初始路径平滑处理。本文改进RRT算法的流程图如图5所示。

3 仿真实验与结果分析

为验证改进RRT算法的可行性以及效率提升效果，利用Matlab 2024a进行仿真实验，实验平台CPU为Intel(R) Core(TM) i5-8265U 1.60GHz，RAM为8 Gb。

3.1 实验环境设置

在本次仿真实验中，实验对象为小型欠驱动无人船，船体长度为10 m，宽度为3 m。实验时设计3类具有代表性的二维仿真环境，分别为：简单障碍物环境、复杂障碍物环境和真实电子海图转化的障碍物环境。3种环境横向尺寸均为300 m，纵向尺寸为500 m，各障碍物之间的通道宽度大于15 m，环境尺寸适配性和安全性均符合实验要求。简单环境和复杂环境中起点和终点分别为(40 m, 40 m)和(260 m, 460 m)，电子海图转化的障碍物环境中起点和终点分别为(20 m, 210 m)和(40 m, 450 m)。电子海图以及转化后地图环境如图6所示。

3.2 仿真实验

利用RRT、RRT*、和本文改进RRT算法在3种环境中分别进行100次仿真实验。最大采样次数设置为5000。为便于观察，仿真图中仅保留最终路径。随机选取一组仿真路径以及取平均值后的仿真数据，分别如图7～图9和表2～表4所示。

3.3 仿真结果分析

1）图7～图9中，虚线为改进RRT算法贪心剪枝后的路径，平滑曲线为最终路径。根据仿真路径可知，在3种实验环境下，RRT和RRT*算法规划的路径中存在大量拐点，路径曲折；改进RRT算法所规划的路径中无拐点，路径更平滑，最终路径质量均优于RRT和RRT*算法。

2）分析表2数据，在简单障碍物环境下，RRT算法的规划时长、路径长度和节点数量分别为8.85 s、937.62 m和338个；RRT*算法路径长度和节点数量分别为707.91 m和260个，效果略优于RRT算法，然而RRT*算法因重布线机制需额外计算，因此对比RRT，RRT*算法规划时长增加较多；改进RRT算法的规划时长、路径长度和节点数量分别为3.62 s、572.60 m和49个，改进RRT算法的规划效率和路径质量明显更优于其余2种算法。此外，由于环境简单，3种算法规划成功率均为100%。

3）分析表3数据，在复杂障碍物环境下，改进RRT算法的规划时长为6.60 s，对比RRT算法和RRT*算法分别减少了63.37%和73.09%；在路径长度方面，与改进前相比，改进RRT算法路径长度缩短了44.36%；由于贪心剪枝策略，改进算法规划路径中节点数量明显减少，为RRT算法的0.22倍。由于该环境下障碍物较多且排列复杂，RRT和RRT*算法的规划成功率有所下降，而改进RRT算法成功率稳定在100%。

4）分析表4数据，电子海图转化的障碍物环境也较为复杂，改进RRT算法的规划时长和路径长度分别为5.98 s和658.76 m，与RRT算法相比分别降低了66.02%和45.74%，同时路径节点数也大幅下降。改进RRT算法在平衡搜索效率的同时，明显提升了路径质量。

综上，基于多策略改进的RRT算法用于无人船路径规划时，能实现耗时短、路径短以及路径平滑度高的要求，能够充分平衡规划效率和路径质量。改进RRT算法性能明显优于RRT算法和RRT*算法。同时该算法稳定性强，在简单、复杂以及模拟真实海图的3种障碍物环境下规划成功率均能达到100%。

4 结　语

本文针对RRT算法用于无人船路径规划时存在的搜索效率低、路径长以及路径不平滑等问题，利用基于贝叶斯优化算法改进的混合采样和基于动态权重改进的三次B样条曲线在内的4种策略对RRT算法进行改进优化。在3种类型障碍物环境下对改进RRT算法进行仿真实验并与RRT、RRT*算法进行对比，数据表明改进RRT算法在规划效率、路径长度、路径质量以及稳定性等方面具有明显优势，有效解决了RRT算法用于无人船路径规划时存在的问题，同时为无人船全局路径规划问题研究提供新思路，具有一定的实际应用价值。