近年来，我国海上风电装机量日益攀增，海上风电市场发展前景广阔。然而，海上风电运维技术落后、运维费用高昂等因素成为限制海上风电开发规模的主因之一[1]。因此，开展海上风电运维船路径排程优化及运维船多个运维点的路径规划研究极具现实意义。海上风电运维过程中运维船舶需要根据指控中心的指令到达多个运维目标点进行风电运维作业，针对此问题融合改进Bi-RRT(bi-directional rapidly-exploring random trees)与TEB(timed elastic band)算法实现海上运维船舶的多目标点避障路径规划，以提高海上风电运维的智能化水平。

传统路径规划算法包括人工势场算法、模糊逻辑算法[2]、遗传算法[3]、A*算法、PRM算法[4]等。对于海上风电运维场景下的多目标点路径规划，需要对运维船所处位置进行环境建模。在存在障碍物约束下的复杂场景下，通常使用RRT算法进行避障并寻得最优路径。然而，传统的RRT算法一般应用于单目标避障路径规划中，且其本身所具有的随机采样特性，使其存在导向性弱，生成树构建过程中冗余采样点较多等问题[5-7],不可直接用于船舶多目标点的海上避障运维路径规划的系统中。

以海上风电运维为背景，建立海上风电场的模拟场景图。考虑RRT自身所存在的导向性差、冗余路径点较多的问题，引入启发式采样策略削弱算法采样过程中的随机性，使得生成树可以快速寻得最优路径，接着，利用三次B样条曲线对算法所规划得到的路径进行平滑处理，使其更适用于实际应用环境[8]。一方面，在Matlab中导入所建立的模拟场景图，验证改进Bi-RRT算法应用于多目标点路径规划的优越性。另一方面，通过ROS仿真平台，搭建模拟仿真环境，利用激光雷达实时感知周围环境数据，利用改进Bi-RRT算法实现SLAM自主建图，完成地图构建。采用改进Bi-RRT与TEB融合算法作为仿真机器人的自主路径规划算法，并在仿真实验平台中利用该算法进行多目标点路径规划实验。

1、问题描述与仿真场景搭建

对于远海风场，往往需要借助运维母船(简称SOV)上的子船进行各待运维风机的运维工作，运维子船需从SOV所停留的位置出发，依次到达多个待运维风机进行运维(访问多个待运维点),最终再返回起点。对于有多个待运维目标点需要访问的风场水域内路径规划，需要在确定各目标点访问次序的前提下，利用可行的全局路径规划算法得到依次到达各个目标点的全局规划路径，并判断风场水域内是否存在障碍物区域约束，选用合适的局部路径规划算法，使船舶移动过程中可以实时避障。因此，才可有效解决在风场水域中有障碍区域限制的船舶遍历多目标点的路径规划问题。

以江苏沿岸某海上风电场为例，其海上风电机群有风机47台，装机容量为6.45 MW,总装机容量为303.15 MW。该风场配置有一座220 kV的海上升压站，场区中心离岸距离为64 km, 风场形状呈不规则多边形。为了避免尾流效应对场区风机的影响，每台风机之间的距离不一，依据场区风机布局图，建立如图1所示机组分布模型。

运维子船从起点出发，在完成所有运维任务后，最终返回起点，形成一条闭环运维线路。

图1 风电机组分布

2、路径规划算法

2.1 基于Bi-RR的全局路径规划算法实现

基本Bi-RRT算法一般应用于两点间路径规划，不能直接进行具有连续性的多目标点路径规划，因此，通过对RRT算法进行性能分析，将多扩展树思想应用于Bi-RRT多目标点路径规划问题的求解中，该算法具体描述：SOV停滞点与第一个目标点分别作为双向生成树构建的根节点，开始向两侧扩展路径；以第一个目标点和第二个目标点为根节点向两侧扩展路径；以此类推，直到以第n个目标点和运维起始点位置点作为根节点构建完生成树后，整个算法结束。这里以3个目标点为例，多目标点演示路径扩展示意图见图2。

图2 多目标点路径扩展示意

文中从基于均匀概率合理化采样机制和路径平滑两方面进行改进。

2.1.1 基于均匀概率的分配采样机制

传统Bi-RRT算法在产生随机点时，是基于全局统一的随机采样概率，即在整个工作空间中随机产生采样点，从而导致路径生成过程中存在很多冗余节点。因此引入基于均匀概率的分配采样机制，减少随机采样过程中的盲目性[9-10]。具体步骤如下。

步骤1。设置采样阈值k,k∈(0,1)。

步骤2。进行随机采样前，生成随机采样值n,对比n与k的大小，若n∈(0,k),则将另一棵扩展树最新生成的pnew确定为随机采样点，以提高Bi-RRT算法的收敛效率。否则，在起始点和目标点之间生成的全局工作域内进行随机采样，保证算法自身的全局搜索性。采样阈值k越大收敛速度越快，为了使算法具有更好的全局搜索性及更佳的路径规划效果，k一般处于0.1～0.3之间。

步骤3。当n∈[0,k]时，新节点的扩展方式为

式中：pnear为以source为根节点扩展生成树中距离另一生成树中最新生成的pnew节点最近的点，该扩展树会在pnear的基础上以特定步长s向目标节点goal扩展。

步骤4。当B=(Q,τ)时，另一棵生成树获得的pnew节点会对当前扩展树的随机采样过程产生引力作用，即pnear节点会启发当前扩展树的扩展方向向pnew靠近。具体新节点的扩展方式为

式中：X1,X2分别为引力作用与随机点影响下的扩展比重，其中：

式中：s′,s″分别为另一扩展树p′new节点与当前扩展树prand对新节点扩展比重步长，s′/s″越大表示另一扩展树p′new节点对于当前节点扩展的引力作用越强。

2.1.2 路径平滑处理

基于均匀分配采样机制虽然减少了冗余空间的搜索，但生成的路径仍然存在冗余节点，使得多目标点路径规划轨迹不够平滑，增加了路径长度与船舶能耗。因此，对Bi-RRT算法生成的生成树轨迹进一步平滑处理是极为必要的。基于Dijkstra算法思想的路径平滑处理，路径优化效果见图3。

图3 路径平滑处理效果

具体处理步骤：计算已获取路径上所有相邻两节点间的距离，以source为起始点检测source→pk(k≥1)是否可以形成一条新的无碰路径；若可以则判断source→pk是否小于source→p1→…→pk;若小于则将新路径添加到扩建树，循环执行直到碰撞检测不通过时，得到最短路径path1。接着，对中间节点pk进行检测，得到其到达后面节点所形成的最短无碰路径，检测到终止点goal为止。

2.2 基于TEB算法的局部路径规划

TEB算法可以理解为在具有固定两端点的弹性路径之间，增加一些含有时间信息的轨迹点，通过添加带时间信息的轨迹点使规划出的轨迹包含速度信息[11]。其效果见图4。

图4 TEB算法原理示意

在ROS中，可以根据全局路径规划算法得到机器人在map坐标系中的一系列位姿点，设这些位姿点序列为

式中：ξi为序列长度。相邻两个连续位姿点时间间隔记为ΔTi,那么一连串位姿点的时间序列可表示为

因此，TEB算法是指由位姿序列和时间序列组成的一个元组。

TEB算法基于全局优化路径，提取其中一部分离散位姿点加入时间信息，利用G2O(general graphic optimization)算法优化目标函数，使得这些离散位姿形成的局部轨迹路线达到长度最短、耗时最短并平滑规避障碍物等目标，同时所得轨迹需要满足机器人运动学方面上速度和加速度的约束。

TEB算法的流程图见图5,该算法首先从全局路径规划所得轨迹中提取一定长度的部分姿态点，一方面检测这些姿态点的位置和状态是否可以规避障碍物，另一方面向这些姿态点中加入初始间隔时间进行初始化操作。接着再依据相邻姿态点间的距离及间隔时间等信息增加或删除差的姿态点以得到优化过的初始轨迹。然后考虑规避障碍、运动学模型、最短化路径长度等约束条件，通过调节参数实现多目标最优的效果。利用G2O构建优化超图，求解所构建的大规模稀疏优化问题。

图5 TEB算法路径规划流程

TEB算法中的位姿点与时间间隔等信息表示超图中的节点，不同节点间的关联形成目标函数或约束函数作为超图的边。如图6所示，两个相邻位姿点距离信息和时间间隔形成了速度约束，结合所得速度信息进而得到加速度约束，位姿点信息与障碍物位置信息构成了障碍约束。

图6 超图优化描述

3、仿真实验

首先根据风电运维场景中，各风电机组布局建立二维仿真场景，将常用的人工势场算法、基础RRT算法、基础Bi-RRT算法与平滑改进的Bi-RRT算法进行二维路径规划仿真对比实验。进而借助ROS平台搭建三维仿真场景，分别使用A*算法和融合Bi-RRT和TEB的路径规划算法进行仿真对比实验。最后，验证了融合Bi-RRT和TEB的路径规划算法的优越性和可行性，从而进一步在三维场景中确定多个目标点，使用基于Bi-RRT算法和TEB算法分别进行全局路径规划和实时避障局部路径规划的仿真实验，以验证在复杂风电运维场景下多目标点路径规划能力和对未知障碍进行自主避障的效果。

3.1 Matlab中的仿真实验

为了验证改进Bi-RRT算法进行多目标点路径规划的优越性，以第1节建立的风场运维模型为基础，在Matlab中进行算法仿真。假设目前需要维修的海上风电机组为6号、18号、21号、32号、38号5台风机，设定依次访问待维修风机的顺序为38号→6号→18号→21号→32号。针对人工势场、基本RRT、Bi-RRT与改进的Bi-RRT算法进行500次实验。对于RRT相关算法均设置其扩展步长为20,为保证改进的Bi-RRT算法进行路径规划的效果，设置其采样阈值，且节点扩展比重步长取，比重为1/2。各个算法的最大采样值为10 000。四种算法的实验仿真效果见图7。

图7中，运维船舶从SOV停滞点出发依次经过38号、6号、18号、21号、32号风机进行运维作业，最后再返回起始点。由仿真图7a)、b)可知，人工势场与RRT算法经改进后均可进行多目标点路径规划，但对于效果而言，基于采样的RRT算法更为适用；由仿真图7c)可知，相较于基本RRT算法，基于Bi-RRT算法进行的多目标点路径规划，其采样过程所生成的冗余路径较少，但其所获得的路径效果没有较大改善。因此利用基于均匀概率的分配采样机制对基本Bi-RRT进行改进，并由Dijkstra算法思想优化后，由仿真图7d)可见，其所寻得的路径不仅冗余节点相对减少，路径的长度与曲折程度也有一定改善。

由于RRT算法自身具有较强的随机性，因此为进一步验证算法的普遍适用性，对所做的100次实验进行数据记录，得出仿真的平均数据结果见表1。

表1 不同算法路径规划结果数据统计表

由表1可知，利用人工势场算法路径寻优过程中往往陷入局部最小值，难以及时到达目标点；传统RRT算法路径规划时间缩短，所规划路径长度较人工势场算法缩短近50%;而Bi-RRT算法在传统算法的基础上，路径规划效率提升51.1%,路径长度缩短32.8%;改进的Bi-RRT算法相较于原算法，其迭代次数减少50.4%,求解时间减少11.7%,路径长度缩短30.5%。通过上述对比，可得出改进的Bi-RRT算法不仅可以减少冗余搜索，而且进一步提高路径规划的效率。

图7 多目标点路径规划结果

3.2 ROS仿真系统中的实验验证

3.2.1 ROS仿真系统

为了进一步验证融合改进Bi-RRT与TEB路径规划算法的效果，在Ubuntu20.04LTS系统中搭载ROS-Noetic系统进一步实验，建立小型仿真机器人作为运维船只，并设定其最大航行速度为0.8 m/s,最大角速度为1 rad/s。同时，在Gazebo中建立虚拟仿真环境，让仿真机器人模拟船舶所处的大型海上风场环境中的场景。仿真模拟场景见图8,另外，借助仿真机器人搭载的激光雷达传感器感知外部环境信息，利用改进Bi-RRT算法实现机器人SLAM自主建图，所构建的全局代价地图见图9。

图8 仿真模拟场景

图9 全局代价地图

3.2.2 改进Bi-RRT与TEB融合算法实验

实验整体流程：先利用roslaunch命令启动gazebo仿真环境，并在环境中导入机器人模型；接着启动导航相关的launch文件，将保存的map地图信息导入；然后利用Rviz中的校准仿真机器人的位姿，最后以机器人所处位置为起点，设定同一目标点对机器人进行对比路径规划。将改进Bi-RRT与TEB融合算法与应用性能较好的A*算法进行对比实验，见图10,图10a)是改进Bi-RRT与TEB融合算法，图10b)是A*算法。从路径来看所提改进Bi-RRT与TEB融合算法得到的路径更短且更为平滑，实验结果表明，采用该算法可以更有效地完成机器人的路径规划任务。

图10 两算法路径规划结果

3.2.3 多目标点路径规划实验

多目标点路径规划实验设置4个目标点，机器人根据指定的先后顺序，依次自主导航到达各个目标点，采用改进Bi-RRT和TEB融合算法进行路径规划，并实现自主路径规划。

如图11所示，整个过程中，仿真机器人依次到达指定目标点A、B、C、D4点，同时所得规划路径平滑且规避障碍物，较好的完成了多目标点路径规划任务。

图11 多目标点路径规划实验过程

4、结论

1)针对传统Bi-RRT算法采样随机性较强，所规划路径效果较差、算法运行效率较低的问题，进行Bi-RRT算法的改进。引入基于均匀概率的分配机制和对立扩展树新节点导向决策，并利用Dijkstra算法思想进行路径平滑处理。通过在所设立二维环境中与人工势场、传统RRT算法、基础Bi-RRT算法对比，证明了改进Bi-RRT算法不仅减少了扩展树生成过程的冗余搜索，也进一步优化了算法运行效果，并提高所搜索路径的平滑度。

2)借助ROS仿真平台，搭建模拟仿真环境与小型机器人，通过Gazebo与Rviz联合验证，使用改进后的Bi-RRT算法与TEB算法规划出可行驶的平滑路径，且所得到的路径可以更快且更顺滑的规避障碍物。在多目标点路径规划实验中，确定机器人需到达的目标点位置，以及访问各目标点的顺序，机器人即可按照访问顺序依次进行自主路径规划并达到各目标点。

参考文献:

[1]王宇田.基于混沌云量子蝙蝠算法的海上风电场运维船路径排程优化方法研究[D].哈尔滨:哈尔滨工程大学,2021.

[2]刘建娟,刘忠璞,张会娟,等.基于模糊控制蚁群算法的移动机器人路径规划[J].组合机床与自动化加工技术,2023(1):20-24.

[3]圣文顺,徐爱萍,徐刘晶.基于蚁群算法与遗传算法的TSP路径规划仿真[J].计算机仿真,2022,39(12):398-402,412.

[4]林俊志,席万强,周俊,等.基于改进PRM和APF的移动机器人路径规划[J].国外电子测量技术,2022,41(12):1-6.

[5]刘渐道,张英俊,朱飞祥.一种水面无人艇多任务点路径规划方法[J].上海海事大学学报,2021,42(4):1-6.

[6]刘祥,叶晓明,王泉斌,等.无人水面艇局部路径规划算法研究综述[J].中国舰船研究,2021,16(增刊1):1-10.

[7]陈强,马健,杨蘩.求解多目标点路径规划问题的离散头脑风暴算法[J].智能系统学报,2023,18(1):96-103.

[8]黄国良,周毅,郑坤,等.基于改进蚁群算法的全局船舶路径规划方法[J].船海工程,2023,52(2):97-101,136.

[9]欧阳子路,王鸿东,王检耀,等.基于改进Bi-RRT的无人水面艇自动避碰算法[J].中国舰船研究,2019,14(6):8-14.

[10]叶鸿达,黄山,涂海燕.基于改进Bi-RRT~*算法的移动机器人路径规划[J].电光与控制,2022,29(2):76-81.

[11]郑凯林,韩宝玲,王新达.基于改进TEB算法的阿克曼机器人运动规划系统[J].科学技术与工程,2020,20(10):3997-4003.

基金资助:江苏省工业和信息产业转型升级专项资金(CMHI-2022-RDG-004); 江苏省研究生实践创新计划(SJCX22_1966);

文章来源:陈慧敏,窦培林,程晨,等.基于Bi-RRT和TEB算法的风电水域多目标点路径规划[J].船海工程,2024,53(04):130-136.