基于变参数阈值的随机扩展树算法路径规划研究

姜利光+甘屹+孙福佳

摘要：针对随机扩展树算法在未知空间中进行路径规划扩展时随机性大，且扩展的树节点在整个环境空间中搜索过于均匀等问题，提出一种基于变参数阈值的随机扩展树算法。改进后的算法在路径规划中，针对具体情况选取参数阈值作下一步扩展，使得每次扩展都有着一定的概率性偏向目标；同时设定可变参数阈值，避免了陷入局部极小值，有效解决了随机性大和搜索均匀问题。通过Matlab仿真实验，验证了該算法的可行性和有效性。

关键词：随机扩展树算法；路径规划；参数阈值

DOIDOI：10.11907/rjdk.171936

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2017）012-0067-03

Abstract：A stochastic extension tree algorithm based on variable parameter threshold is proposed to solve the large random of extension tree algorithm in the unknown space and the searching uniformity of extended tree nodes in the whole environment space. And then the improved algorithm is applied to the path planningto select the parameters for the next expansion aiming at the specific situation， so that each expansion has a certain probability of bias target； Meanwhile， the variable parameter threshold is set to avoid falling into the local minimum，which effectively solves the problem of large random and searching uniformity. Finally， the feasibility and validity of the algorithm are verified by MATLAB simulation experiment.

Key Words：stochastic expansion tree algorithm； path planning； parameter threshold

0 引言

路径规划技术是移动机器人研究领域的一个重要组成部分。其目的是机器人按照某一性能（时间、路程、耗能）搜索出一条由起始位置节点到目标位置节点之间的最优或次优无碰路径。路径规划主要分为：完全已知的全局路径规划、完全未知或部分未知的局部路径规划[1]。已有研究多是关于全局已知的静态环境中的路径规划。但在实际工作中，环境中的障碍物位置、大小信息都是未知或部分已知，有时障碍物的位置还会随着时间的变化而不断移动，增加了路径规划中的建模难度[2]。

随机扩展树（Rapidly-exploring Random Tree，RRT）算法采用随机采样的规划方法，无需对环境空间进行建模，避免了预处理[3]。但由于RRT算法是基于随机采样的机制，导致在路径规划时扩展的树节点均布于整个空间内，产生大量的无效搜索。针对该问题，提出通过重复使用前一个周期的随机树信息对RRT算法进行改进，如ERRT算法[4]、DRRT算法[5]等均在一定程度上提高了RRT算法的稳定性，但RRT算法所采用的固有规划方式限制了其进一步应用。本研究采用RRT算法进行机器人路径规划，以避免复杂的空间建模，并提出通过引入变参数阈值引导随机树在扩展树节点时以一定的概率偏向目标点，避免了搜索点过于平均的问题。此外，参数阈值存在可变性，使得算法避免收敛于局部极小值。

1 RRT算法原理

RRT算法以机器人移动的开始点作为树的初始根节点，利用随机采样原则，选定一个随机节点。根据机器人移动约束条件（如步长、角度），在所选择的节点上避开障碍物进行扩展，直到产生一个新节点，并将此新节点添加到搜索树中，以此为树节点作下一步扩展，依次重复上述过程，直至找到所要寻找的目标点才停止搜索。RRT算法扩展方式如图1所示。

图1中，C表示扩展环境空间，X0表示初始点，Xi表示随机点，Xj表示离随机点最近的一个树节点，Xi为在Xi和Xj的连线上以步长Δ为单位截取的新节点。

该算法在搜索过程中要保证随机采样使得机器人向未知区域扩展，并在搜索过程中不断推进搜索树生长，同时使得树节点与目标点的距离不断接近，最终该目标点为树上的一个节点或者在最后的节点附近（小于一个步长距离），即完成搜索任务[6]。

定义X0为初始位姿构建随机树T，搜索步骤如下：①在空间C中，从初始点X0出发先建立一颗遍历树T；②在所处的区域内随机选择一个位姿点Xi；③找出T中距离Xi最近的节点Xj，然后选择控制输入集U中的选择输入u∈U（如速度、角度等）作用在Xj，使得机器人沿着Xi直至Xj；④由Xj朝Xi方向扩展一定的距离Δ到Xk（Δ为步长），并且Xk属于该自由空间中的点；⑤选择能使Xj到Xi距离最近的控制输入u为最佳输入，依次重复该过程直到新生成的某个点与目标点（Xm）的距离小于该步长，至此随机树构建完毕。

2 变参数阈值RRT算法

2.1 偏向目标算法模型

RRT算法在全局规划中随机选取节点，能够扩大搜索空间，但这种随机选择也会导致路径规划中的盲目性，不仅使得路径解发散，同时也会耗费相当长的算法搜索时间。特别是在障碍物较少的局部空间中，随机性会将路径搜索点均匀遍布于空间内，延长路径解收敛时间。为了提升RRT算法效率，研究者[7-8]提出采用偏向目标RRT算法（Bias-goal，Bg-RRT）。随机函数生成树节点之前，先按照平均概率分布方式随机获取一个概率值，以一定的概率性将目标点作为牵引点，在一定程度上解决扩展节点时随机性大的问题。具体步骤为：取参数阈值q，表示该算法认定目标点Xm为随机点Xi的几率。如果q的值大于算法产生的概率值p，就选取目标点Xm为Xi。如果q的值小于算法产生的概率值p，就由随机函数Random_Configuration（）随机产生Xi。经过大量研究发现，加入参数阈值q后，该算法可以使得扩展树快速地向目标点生长，但过多偏向目标点时会使扩展树生长陷入局部最优[9-10]。

2.2 Vpt-RRT算法

3 实验仿真与分析

仿真实验所用的计算机处理器为Intel（R） CORE（TM）i5-2400 CPU @ 3.10GHz 3.10GHz，显卡为Intel（R） HD Graphics，内存为4.00G，采用MATLABR2014a工具编程实现。

3.1 参数阈值设定

Bg-RRT算法中，参数阈值q的值域为[0，1]。以q=0.1取值间隔为0.1，进行不同参数阈值q的路径规划仿真实验。仿真实验中选取相同的步长，以仿真结果中扩展的总节点数、路径平均规划时间作为性能指标。对每一个参数阈值q，分别做多次实验，通过统计分析实验到第10次时结果趋于收敛；故取10次实验的平均值作为该q值的Bg-RRT算法运行结果，仿真实验结果如图3、图4所示。

由图3可知，随着参数阈值q值的增大，Bg-RRT算法中随机树扩展的总节点数先减小后增大再减小，总体呈现下降趋势。由图4可知，路径规划时间总体上随着参数阈值q的增大先减小后增大。通过分析图3、图4可知，参数阈值q对Bg-RRT算法而言十分重要，直接影响路径规划相关性能指标。q值选取得是否合理直接影响最终路径规划的优劣。q值较小时，随机树扩展的树节点增多，说明规划中偏向目标搜索的趋势不明显，随机树会向其它空白区域进行无效扩展。q取值较大时，随机树以较大的概率选取目标节点进行扩展，更倾向朝着目标点生长，扩展的树节点较少；但由于随机节点选择单一，规避障碍物的能力减弱，甚至陷入局部极小值。因此需要花费更多的时间躲避障碍，进而增加了规划时间。

通过以上仿真分析可知，本文中的qmax可取0.7，此时扩展树有較大的偏目标趋势，且路径规划时间相对较少，在无障碍空间内能以较大的概率朝着目标搜索。而对于qmin，取0.1时，算法规划时间、扩展的树节点相对较多。在路径规划中，q值的选取根据定义视具体情况而定，合理完成RRT算法的路径规划。

3.2 仿真实验

机器人移动的仿真环境范围设置为100*100单位格，整个环境空间分为障碍区域和非障碍区域，其中空白处表示无障碍区域，黑色圆表示障碍物。仿真环境中设定机器人移动的起始点坐标为（5，5），目标点坐标为（95，95）。

采用RRT算法、Bg-RRT算法和Vpt-RRT算法分别在大型障碍物环境、存有狭窄通道环境、复杂障碍环境下进行对比实验。各种环境中的障碍物大小、数量均随机生成。

图5为3种算法在大型障碍物环境下的路径规划结果，其中“+”表示随机树在规划过程中扩展的树节点，线条表示由起始点到目标点的路径规划拟合线。图6为狭窄通道环境下3种算法的路径规划结果，仿真过程设定迭代次数为500次时，RRT算法会出现无法成功规划的现象，Vpt-RRT算法则能够在每次仿真中快速找到一条有效路径。复杂障碍物环境下的路径规划如图7所示。

由图5-图7可看出，本文提出的Vpt-RRT算法在不同的障碍环境中都能合理地规划出一条有效路径。

为了更清楚地体现变参数阈值RRT算法的优越性，在以上3组实验中分别用RRT算法、Bg-RRT算法和Vpt-RRT算法各进行100次仿真实验，取平均值作对比。表1和表2分别为路径规划过程中的总节点数和有效节点数。

由表1、表2可知，Vpt-RRT算法在3种不同环境下路径规划过程中扩展的总节点数和有效节点数均优于其它两种算法，特别是在存有狭窄通道的环境下，这说明Vpt-RRT算法能够大大减少扩展的树节点，并且该算法具有很好的避障性能和寻优能力。

4 结语

本文针对基本随机扩展树算法在路径规划中随机性大、搜索方式过于平均、搜索效率低下等问题，分析其原因在于随机点在全空间分布过于均匀。鉴于此，提出了Vpt-RRT算法，在原算法中通过增加变参数阈值，视具体环境确定阈值大小；引导扩展中树节点的选取，使节点有偏向目标点的趋势，避免了扩展中的无效搜索，使得随机树能够朝着目标点快速地扩展生长，解决了随机点分布过于平均的缺点；并且由于每次扩展时参数阈值都具有可变性，因而避免了陷入局部极小值。最后在3种不同环境下，分别对RRT算法、Bg-RRT算法与本文提出的Vpt-RRT算法进行仿真实验。结果表明，在不同的仿真环境中，本文提出的算法均具有更好的可行性和有效性。

参考文献：

[1] 魏唯.智能规划方法中启发式搜索策略的研究[D].长春：吉林大学，2013.

[2] 朱大奇，颜明重.移动机器人路径规划技术综述[J].控制与决策，2010，25（7）：961-967.

[3] 张煜，任保安，陈璟.基于改进RRT算法的预警机实时航迹规划[J].计算机仿真，2016（9）：106-112.

[4] 冯林，贾菁辉.基于对比优化的RRT路径规划改进算法[J].计算机工程与应用，2011，47（3）：210-213，228.

[5] 宋金泽，戴斌，单恩忠，等.一种改进的RRT路径规划算法[J].电子学报，2010，38：225-228.

[6] 杜明博，梅涛，陈佳佳，等.复杂环境下基于RRT的智能车辆运动规划算法[J].机器人，2015（4）：443-450.

[7] 黄炳强，曹广益.基于人工势场法的移动机器人路径规划研究[J].计算机工程与应用，2006（27）：26-28.

[8] FRAGKOPOULO CHRISTOS，GRAESER AXEL.Extended algorithm with dynamic N-dimensional cuboid domains[C].Proceedings of the International Conference on Optimisation of Electrical and Electronic Equipment，OPTIM，2010：851-857.

[9] GARRIDO SANTIAGO，BLANCO DOLORES，MORENO LUIS，et al.Improving RRT motion trajectories using VFM [C].IEEE 2009 International Conference on Mechatronics，ICM，2009.

[10] 王滨，金明河，谢宗武，等.基于启发式的快速扩展随机树路径规划算法[J].机械制造，2007，45（12）：1-4.

（责任编辑：孙 娟）