0 引　言

水面无人艇在海洋科学、水产养殖和环境保护等领域发挥着重要作用^[1]，如海水检测、智能投料、水面垃圾清理等工作^[2]。因此要求其具备在狭窄和复杂水域航行和强大的自主规划能力。为了确保无人艇能够在狭窄以及复杂工况下准确、安全的进行路径规划，研究高效实用的路径规划算法显得尤为重要且十分迫切。

路径规划旨在通过某种算法，规划出从起点到目标区域满足自身约束条件的无碰撞路径^[3]。目前，比较常见的路径规划算法包括基于几何模型的A*算法^[4]、Dijkstra算法^[5]，基于智能优化的PSO算法^[6]以及基于智能采样的RRT算法^[7]等。相对于其他算法，RRT算法具有参数少、适用范围广等优点，被广泛应用^[8]。为了提高RRT算法路径搜索速度，Kuffner等^[9]在传统RRT算法的目标点增加一棵树实现双向搜索，提出Bi-RRT算法。

Bi-RRT算法在一定程度上加快了搜索速度，但稳定性较差，为了进一步提升Bi-RRT算法性能和效率，Guo等^[10]将Bi-RRT算法与Dijkstra算法和二次贝塞尔曲线进行结合，增强了无人艇在复杂水面环境的路径规划能力。Sun等^[11]在Bi-RRT算法中引入一种新的随机树生长策略来提高效率并优化局部最小值问题。Zhou等^[12]通过优化随机树扩展方式以减少冗余节点，改进样本点采样策略以增强Bi-RRT算法搜索效率。张一帆等^[13]在Bi-RRT算法基础上改进随机点采样机制，在节点生成过程中引入改进的势场函数提高路径生成效率。黄健堃等^[14]针对两树连接慢的问题提出了改进Bi-RRT算法，为加快两树相遇，在Bi-RRT算法引入生长引导机制。赵贵祥等^[15]针对传统Bi-RRT算法效率低的缺点，提出了启发式节点扩展策略，提升算法搜索速度。陈慧敏等^[16]在常规Bi-RRT算法的基础上加入基于均匀概率的分配机制和基于对立扩展树的新节点导向策略，提高算法求解质量和效率。

综合分析现有的研究成果，本文提出改进Bi-RRT算法，对基础Bi-RRT算法进行无人艇路径规划时存在的规划效率低、偏航角过大、路径不平滑和路径长度大4个问题进行改进，改进后算法通过双树渐进引导策略高效引导两树生长，避免两树“背向扩展”，同时路径直连机制有效解决了两树连接处过于曲折的问题。加入自适应权重的3次B样条函数以及动态步长等优化机制，加快路径规划速度并提高路径质量，最后通过实验对改进前后Bi-RRT在内的4种算法进行对比。改进后算法能够高效引导水面无人艇在狭窄和复杂水域中自主进行路径规划。

1 环境建模和算法介绍 1.1 环境模型描述

水面无人艇进行路径规划前，需要把获取的环境信息栅格化，然后进行阈值化处理，获取静态环境的二值图像或点集。规定障碍物区域为黑色，用数字1表示，安全水域为白色，用0表示。为了简化模型，通常把无人艇视为质点，由于无人艇本身具有长度，因此需要对障碍物进行膨胀处理来避免与无人艇发生碰撞^[17]。水面障碍物大多为不规则形状，因此文中选取形态学膨胀。根据障碍物类型，通常选择圆形或长方形膨胀核对障碍物膨胀处理，膨胀核大小根据无人艇长度确定，膨胀过程通过对原始图像进行扫描和卷积计算来实现。形态学膨胀如式(1)所示，障碍物形态学膨胀效果图如图1所示。

$ A_{\text{inflate}}= B\oplus S。$

(1)

式中：B为障碍物边界；通常为二值图像或点集；$ \oplus $为形态学膨胀操作；S为膨胀核。

1.2 基础Bi-RRT算法原理

与RRT算法不同，Bi-RRT算法采用2个随机树同时生长来加快搜索，但两棵树的生长方式与RRT算法相同。在Bi-RRT算法中构建2个随机树T₁和T₂，T₁和T₂分别从起始点和目标点进行扩展，当T₁树上节点到T₂树上节点之间距离小于设定步长时，则连接这2个节点，完成搜索。基础Bi-RRT算法原理图如图2所示。

图中，左右两侧分别为随机树T₁和T₂，q_start为随机树T₁的起点，q_goal为随机树T₂的起点，q_rand和q_rand'分别为T₁和T₂的采样点，q_new和q_new'为沿固定步长生成的新节点，q_nearest和q_nearest'分别为随机树T₁和T₂中距离新节点最近的节点^[18]。

2 改进Bi-RRT算法 2.1 双树渐进引导策略

Bi-RRT算法在扩展两棵树的过程中，受随机采样影响，树的末端节点可能会远离另一棵树的末端，造成“背向扩展”；此外，在两树连接处路径过于曲折。针对这一问题，本文提出在Bi-RRT中引入爬山算法，使两棵树的末端更快地相互靠近。

爬山算法是一种简单而有效的局部搜索优化算法，旨在通过逐步改进当前解来寻找更优解^[19]。具体优化步骤如下：

步骤1　定义目标函数$f(q)$。$f(q)$为当前节点与另一棵树末端节点的欧氏距离，目的是通过邻域搜索找到一个节点，使得$f(q)$最小化，以引导树扩展至更接近另一棵树末端的位置。

步骤2　执行邻域搜索策略。从当前节点${q_{{\text{near}}}}$出发，生成若干候选节点$N({q_{{\text{near}}}})$。候选节点的生成方式为：

$ {q_i} = {q_{{\text{near}}}} + \Delta {q_i},{\text{ }}\Delta {q_i}\sim u( - \delta,\delta)。$

(2)

式中：$\Delta {q_i}$是以${q_{{\text{near}}}}$为中心的小扰动；δ为邻域搜索范围，为确保搜索精度与效率的平衡，本文δ取0.2。同时，需对候选节点进行障碍物检测，剔除不可行点。

步骤3　选择最优节点。在所有候选节点中，选择使目标函数值最小的节点${q_{{\text{best}}}}$，如下式：

$ {q_{{\text{best}}}} = \arg \mathop {\min }\limits_{{q_{\text{i}}} \in N({q_{{\text{near}}}})} f({q_i})。$

(3)

式中：${q_i}$为候选节点；${q_{{\text{best}}}}$为最优节点。

若$f({q_{{\text{best}}}}) \lt f({q_{{\text{near}}}})$，则将${q_{{\text{best}}}}$加入树中；若无合适的候选节点，则随机选择一个方向进行扩展。

步骤4　执行路径直连机制。每次生成新节点，两树的新节点尝试进行连接，并对路径进行碰撞检测，若碰撞则放弃该连接，继续寻找新节点；若没有碰撞则停止拓展，完成路径规划。路径直连示意图如图3所示。

为验证在基础Bi-RRT算法中引入该策略后用于路径规划的效果，在相同环境和参数下与基础算法进行对比实验。输出一组路径图像和实验数据，分别如图4和表1所示。

图4(a)中曲线为基础Bi-RRT算法规划的最终路径，由于两树扩展时缺乏引导，导致两树末端位置偏移较大、路径曲折，从而产生冗余路径且规划时间长，如图4(a)中①处曲线所示；图4(b)中曲线为加入双树渐进引导策略后算法规划的路径，图中②处线段为路径直连部分，通过对比路径图像可看出该策略能够有效引导两树的扩展方向，减少路径长度，加快末端连接。

根据表1数据可知，基础Bi-RRT算法的平均搜索时长和平均路径长度分别为4.01 s和1831.24 m，加入双树渐进引导策略后平均搜索时长和平均路径长度分别缩短了33.67%和19.67%。分析可知，在算法中引入该方法有效增强了两树扩展的导向性。

2.2 动态步长策略

在基础Bi-RRT算法中，两棵树扩展步长是固定值^[20]，步长过大或过小均会降低算法搜索性能，且固定步长会导致两树连接时错位较大，不利于两树末端交汇。

改进Bi-RRT算法采用动态步长策略，该策略基于当前节点附近的最近邻节点数量来动态调整步长。动态步长调节如下式：

$ \left\{\begin{gathered} {S_{{\text{imp}}}} = {S_{\max }} \cdot \left( {{1 / {\left( {1 + \lambda \cdot \omega } \right)}}} \right)，\\ \lambda (\rho ) = {\lambda _{{\text{base}}}} + k \cdot \rho。\\ \end{gathered} \right.$

(4)

式中：$ {S_{\max }} $为最大步长；$ \lambda $为调节因子，根据局部范围障碍物占比取值；$ \omega $为当前节点邻域内节点数量；k为灵敏度系数；$ \rho $($ \rho \in [0，1] $)为当前节点局部范围内障碍物占比，通过对局部地图栅格化处理来获取。为更好地平衡搜索速度与精度，局部范围半径选取20，灵敏度系数取值2.5。

2.3 双向距离引导采样策略

针对基础Bi-RRT算法中采用固定目标采样概率所导致的搜索广度与精度不平衡等问题，提出双向距离引导采样策略。利用该方法进行路径搜索时，根据两树末端距离调整采样点生成概率。采样点位置分布图如图5所示，路径中间最大实心点为两树相遇点，空心圆圈代表采样点位置。距离引导的采样概率为：

$ {p_{{\text{dynamic}}}} = {p_{{\text{min}}}} + \left( {{p_{{\text{max}}}} - {p_{{\text{min}}}}} \right) \times {\left( {\frac{{{D_{{\text{global}}}} - {D_{{\text{end}}}}}}{{{D_{{\text{global}}}}}}} \right)^\alpha}。$

(5)

式中：$ {p_{{\text{min}}}} $为最小目标采样率；$ {p_{{\text{max}}}} $为最大目标采样率；$ {D_{{\text{end}}}} $为两树末端之间的欧氏距离；$ {D_{{\text{global}}}} $为从起始点到目标点的欧氏距离；α为非线性控制因子。为平衡算法搜索广度和精度，实验证明α取值为2时效果更优。

2.4 双向跃迁式路径剪枝和角度约束

利用上述Bi-RRT算法规划出完整路径后，大部分路径形态为锯齿状，导致路径长度过大。因此引入双向跃迁式连线法对路径长度进行优化。

从起始点开始，依次跃迁至下一个节点，另一端从目标点开始，依次跃迁至上一节点，2个节点进行连线并执行碰撞检测，若连线与障碍物之间无碰撞，则继续跃迁；当与某节点之间的连线有碰撞时，则标记这一节点的前一节点或后一节点为间断点，当两端连线末端重合或相遇时停止搜索。具体过程如图6所示。

路径剪枝后缩短了路径长度，但路径中可能存在一些大角度偏航角，因此采用角度约束来平滑路径。首先设定路径点的集合为$P$，从第二个点开始依次计算路径的偏航角度$ {\theta _p} $，计算如式(6)所示。当某拐点处偏航角度$ {\theta _p} $大于设定阈值$ \theta $时，则从原始路径中添加位于该节点两侧的父节点与子节点，重新规划此处路径，角度约束过程如图7所示，图7(b)中①处虚线为添加父子节点后路径。偏航角与节点位置如图8所示。文中$ \theta $取90°。

$ {\theta _p} = {{\text{π}} - {\rm{arccos}}}\left( {\frac{{({p_i} - {p_{i-1}}) \cdot ({p_{i+1}} - {p_i})}}{{\parallel {p_i} - {p_{i-1}}\parallel \cdot \parallel {p_{i+1}} - {p_i}\parallel }}} \right)。$

(6)

式中：$ {\theta _{{p}}} $为偏航角；$ {p_i} $为某节点；$ {p_{i- 1}} $为前一节点；$ {p_{i+ 1}} $为后一节点；$ \parallel {p_i} - {p_{i - 1}}\parallel $为2点之间的欧氏距离。

2.5 加权B样条曲线的路径平滑优化

路径经过剪枝后减少了路径长度和拐点数，但在障碍物密集处仍存在拐点，不利于水面无人艇航行。由于B样条曲线平滑路径时不影响路径的基本形态且调用相对简单^[21]，因此采用B样条曲线优化路径。然而为了提高控制点对曲线的调控能力，让曲线更加贴合路径点，本文在标准B样条的基础上为控制点引入自适应权重$ w $，改进过程如下。

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

$ P\left(t\right) = {\sum }_{k=0}^{n}{P}_{k}\cdot {N}_{k,d}\left(t\right)。$

(7)

从标准B样条式(7)出发，当引入一个与控制点相关的自适应权重$ {w_k} $时，意味着每个控制点$ {P_k} $对整体曲线的“影响力”将由权重$ {w_k} $加以调整。因此，每一项$ {P_k}{\mkern 1mu} \cdot {\mkern 1mu} {N_{k ,d}}\left( {{\mkern 1mu} t{\mkern 1mu} } \right) $被乘以一个权重$ {w_k} $，变成$ {w_k} \cdot {P_k} \cdot {N_{k,d}}(t) $。但此时整个曲线的数值范围会发生变化，因此为了保持曲线在几何上的一致性，必须进行归一化处理，即将分子除以所有权重与基函数乘积之和。改进后B样条曲线数学表达式为：

$ P(t) = \frac{{\displaystyle\sum _{k = 0}^n{w_k}{P_k}{N_{k,d}}(t)}}{{\displaystyle\sum _{k = 0}^n{w_k}{N_{k,d}}(t)}}。$

(8)

式中，基函数$ {N_{k,d}}(t) $使用递归关系定义，推导公式如下：

当$ d = 0 $时，基函数定义如下：

$ {N_{k,0}}(t) = \left\{ \begin{aligned} &1,\ \ {{t_k} \leqslant t}{<{t_{k + 1}}}，\\ &0,\ \ {\rm{otherwise}}。\end{aligned}\right.$

(9)

当$ d \geqslant {\text{1}} $时，基函数定义如下：

$ {N_{k,d}}(t) = \frac{{t - {t_k}}}{{{t_{k + d}} - {t_k}}}{N_{k,d - 1}}(t) + \frac{{{t_{k + d + 1}} - t}}{{{t_{k + d + 1}} - {t_{k + 1}}}}{N_{k + 1,d - 1}}(t) 。$

(10)

根据路径情况，本文采用3次加权B样条曲线对路径进行平滑优化，如下式：

$ P(t) = \frac{{\displaystyle\sum _{k = 0}^{\text{3}}{w_k}{P_k}{N_{k,{\text{3}}}}(t)}}{{\displaystyle\sum _{k = 0}^{\text{3}}{w_k}{N_{k,{\text{3}}}}(t)}}。$

(11)

式中：$ {P_k} $为第k个控制点；$ {w_k} $为控制点的权重；$ {N_{k,{\text{3}}}}(t) $为3次B样条基函数；t为描述曲线位置的参数。

为增强B样条曲线在路径转折处的拟合能力，提升关键控制点对曲线形状的调控作用，现将权重函数与偏航角度结合，根据式(6)计算的偏航角度$ {\theta _p} \in \left[ {0,{\text{π}}} \right] $反映路径在该点处的几何突变程度，并据此调整控制点权重$ {w_k} $的大小。权重函数定义为：

$ {w_k} = \gamma + \varphi \cdot \left( {{\theta _p}/{\text{π}}} \right) 。$

(12)

式中：γ为基础权重；$\varphi $为调节因子。通过实验对比不同的$ \gamma $和$\varphi $组合，当$ \gamma= 0.5 $、$ \varphi = 1.5 $时光滑度、拟合度以及综合效率最优，$ {\theta _p} $为当前偏航角度。该函数满足如下性质：当路径变化平缓时（$ {\theta _p} \to 0 $），控制点权重较小，从而减少对曲线形状的干预；而当路径急剧转折时（$ {\theta _p} \to {\text{π}} $），控制点权重增大，增强其对局部曲线形态的调控能力，使曲线更贴近转折点。

为验证加权B样条曲线函数的合理性以及路径平滑效果，在障碍物环境下进行仿真实验。优化前后对比结果如图9所示，图9(a)为平滑前路径，路径中存在拐点；图9(b)中实线为采用3次B样条曲线平滑后的路径，消除了路径中拐点，但偏离原始路径较多，易造成碰撞；图9(c)中实线为采用文中改进3次B样条曲线平滑后的路径，对比可知改进后方法平滑的路径更贴合原始路径，在关键点附近展现出更高的拟合精度。

通过上述方法改进Bi-RRT算法，能够有效增强算法中节点导向性，充分均衡扩展广度和精度，进而减少路径长度和搜索时间，同时路径质量更高，提高无人艇路径规划效率。改进Bi-RRT算法流程如图10所示。

3 仿真分析与实验验证 3.1 仿真分析

为了验证改进Bi-RRT算法用于水面无人艇路径规划的可行性与高效性，通过Matlab 2024a进行仿真实验，实验平台CPU为Intel(R) Core(TM) i5-8265U 1.60 GHz，RAM为8 Gb。

在狭窄地图环境和复杂地图环境中分别使用基础Bi-RRT算法、Bi-RRT*算法、RRT-Connect算法和改进Bi-RRT算法进行实验。其中，改进Bi-RRT算法目标采样概率最大值和最小值设置为0.7和0.2，最大步长设置为30，步长调节因子基础值$ {\lambda _{{\text{base}}}} $设置为1.5；其余3种算法固定步长设置为20，目标采样概率为0.2，最大迭代次数为5000。路径中最大偏航角不超过90°，水面无人艇长度为5 m。狭窄地图中路径起止坐标为(25, 25)和(970, 450)，通道宽度为20；复杂地图中路径起止坐标为(25, 25)和(970, 970)。2种环境下分别进行100次实验，实验结果取平均值。

3.1.1 仿真实验结果

在狭窄水面环境中使用基础Bi-RRT算法、Bi-RRT*算法、RRT-Connect算法和改进Bi-RRT算法进行仿真实验，实验数据取平均值，如表2所示。随机选取1组仿真结果，如图11所示。

图11(a)中蓝色曲线为基础Bi-RRT算法路径，由于该算法依赖两棵树的随机扩展，两树连接时缺乏引导，因此两树连接时产生冗余路径，如图11(a)中①处曲线所示。此外，该算法采用固定步长且缺乏路径平滑等步骤，导致路径中产生大量转弯点，如图11(a)中②处所示。Bi-RRT*算法在Bi-RRT算法的基础上引入重连机制优化路径质量，如图11(b)中曲线所示，但计算量增加，导致搜索时间增加。RRT-Connect算法在计算量方面有所降低，减少了规划时间，但该算法仅依靠扩展连接两棵树，导致路径质量差，如图11(c)中曲线。对比Bi-RRT算法，改进后Bi-RRT算法在未经过B样条函数平滑优化的情况下，路径质量增加，路径节点数量减少，同时路径直连机制介入后加速两树连接，如图11(d)所示，图中①处线段为路径直连，实线段为平滑前的路径，但此时路径中仍存在拐点，因此在此基础上利用改进3次B样条曲线对路径平滑处理，如图11(e)中平滑曲线所示。

在复杂水面环境中，再次对4种算法进行100次仿真实验，实验数据取平均值后如表3所示，随机选取一组仿真路径结果，如图12所示。

根据基础Bi-RRT算法仿真结果，路径中存在较多大角度拐点，例如图12(a)中①附近线段所示。由于该算法为随机扩展，在两树相遇处过于曲折，如图12(a)中②附近线段所示。相比Bi-RRT算法，Bi-RRT*算法搜索的路径长度较短、拐点数量有所减少，如图12(b)所示，但搜索速度下降，消耗大量时间。图12(c)为RRT-Connect算法规划的路径，该算法优点是计算效率较高，但路径较长且不光滑。在未进行平滑优化的情况下，改进Bi-RRT算法生成的路径中不存在大角度偏航角，路径更加平滑，但此时路径中在障碍物密集处仍存在拐点，如图12(d)中①处线段所示，最终利用改进3次B样条曲线平滑路径，如图12(e)中平滑曲线所示。

3.1.2 结果分析对比

1） 通过仿真结果可知，基础Bi-RRT算法在搜索路径时消耗时间较长、路径冗余大并且质量差，改进Bi-RRT算法有效提升了两树的连接速度和精确度，减少搜索时间。根据表2和表3中数据，对比基础Bi-RRT算法，改进Bi-RRT算法的平均规划时间减少46.45%，与Bi-RRT*算法和RRT-Connect算法相比分别减少了61.45%和32.27%。

2）根据表中数据，改进Bi-RRT算法搜索路径中节点数明显减少，能够快速地在空间中搜索，找到目标点。与基础Bi-RRT算法相比，改进Bi-RRT算法的平均路径节点数减少了49.95%。可知，Bi-RRT*算法的路径节点数最多，能够优化路径质量，但消耗大量时间。

3）改进Bi-RRT算法搜索路径时通过路径剪枝有效减少了路径长度。表中数据显示，在2种环境中基础Bi-RRT算法搜索的路径长度最大，与基础Bi-RRT算法相比，Bi-RRT*算法、RRT-Connect算法和改进Bi-RRT算法的平均路径从长度分别减少14.06%、3.93%和25.68%。

4）由于基础Bi-RRT算法和RRT-Connect算法中两棵树的扩展基于随机采样，路径上产生较多弯曲和分支。根据表2和表3中数据，基础Bi-RRT算法和RRT-Connect算法路径中均存在大量拐点，Bi-RRT*算法在后期加入了路径优化，路径中拐点数有所减少，但仍不利于无人艇航行。改进Bi-RRT算法前期通过路径剪枝减少了路径长度和拐点数，但在障碍物密集处仍然存在拐点，因此最后利用改进3次B样条曲线对路径平滑优化处理。

分析对比可知，在相同环境下与其余3种算法相比，改进Bi-RRT算法搜索效率更高。

3.2 实验验证

为进一步验证本文改进算法应用于水面无人艇时的实际规划效果，利用欠驱动水面巡检无人艇在狭窄和复杂水面环境开展路径规划实验。

分别使用4种算法进行20次实验，实验时路径中最大偏航角阈值θ设定为75°。路径规划实验结果如表4所示，同时随机选取一组4种算法的实验路径见图13。

可知，利用改进Bi-RRT算法搜索路径能够更好地引导欠驱动水面无人艇进行航行作业。

由表4数据可知，对比基础Bi-RRT算法、Bi-RRT*算法和RRT-Connect算法，改进Bi-RRT算法的搜索时长分别缩短了53.46%、56.66%和32.37%；路径长度分别减少了41.49%、20.52%和37.59%；路径质量方面，基础Bi-RRT算法、Bi-RRT*算法和RRT-Connect算法规划的路径均存在较多大角度偏航角，大于65°偏航角数量分别为改进Bi-RRT算法的3.96倍、2.58倍和3.66倍。分析对比可知，改进Bi-RRT算法的搜索效率更高、路径更优，能够缩短水面无人艇的实际航行时间。

4 结　语

本文提出一种改进Bi-RRT的水面无人艇全局路径规划算法，主要从两树扩展方式、扩展步长、采样方式和路径质量优化4个方面进行改进，并在算法中加入基于自适应权重的3次B样条函数来实现路径平滑优化。利用Matlab进行仿真分析并展开实艇实验，结果表明：

1） 改进算法优化了基础Bi-RRT算法规划效率低、偏航角过大、路径不平滑和路径长度大的问题。实验表明改进后算法能够高效引导无人艇完成航行任务。

2）仿真结果表明，改进Bi-RRT算法的平均规划时长缩短了46.45%，对比Bi-RRT*和RRT-Connect算法分别缩短32.27%和61.45%。平均路径长度比改进前缩短了25.68%。同时节点数和拐点数明显减少。实艇实验表明，改进Bi-RRT算法的规划时长和路径长度具有明显优势，大于65°的偏航角数量明显减少。

综上，本文提出的改进Bi-RRT算法为水面无人艇全局路径规划问题研究提供了新思路，具有一定实际应用价值。