一种改进的RRT机器人路径规划算法研究

胡兵 向凤红 毛剑琳

摘 要：路径规划技术是目前机器人领域研究热点，而路径规划算法是其核心内容。可变步长的快速随机搜索树（Rapidly-exploring Random Tree，RRT）算法在机器人路径规划算法中复杂度高、效率较低，针对这一问题，提出一种改进的RRT算法。在可变步长的随机树生长过程中，引入双向生长策略，利用双向生长特性，提高路径搜索效率，解决了最优路径与低效率间的矛盾。实验仿真数据表明，改进后的RRT算法在路径规划中不仅算法复杂度低，且搜索效率提高了约一倍。

关键词：快速随机搜索树；可变步长；双向生长；路径规划；搜索效率

DOI：10.11907/rjdk.172931

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）006-0013-04

Abstract：Path planning technology is currently a hot research in the field of robotics， and the path planning algorithm is the core content. Aiming at high complexity and low efficiency of RRT（Rapidly-exploring Random Tree） in robot path planning algorithm， this paper proposes an improved RRT algorithm on the basis of in the process of RRT. In the variable step size RRT random tree growth， the bidirectional growth strategy is introduced， and the efficiency of path search is improved by using the characteristic of bidirectional growth， and the contradiction between the optimal path and the low efficiency are solved. The results of simulation data show that the improved RRT algorithm not only has low complexity， good smoothness， but also improves the search efficiency twice as much in path planning.

Key Words：RRT； variable step-size； Bidirectional growth； path planning； search efficiency

0 引言

隨着智能机器人不断发展，路径规划问题研究越来越深入。路径规划指机器人在当前环境中按照一定的标准，搜索出一条从起始状态点到目标状态点，能够绕开障碍物的最优或次优路径。传统的人工势场法[1]、神经网络法[2]和遗传算法[3]在解决机器人路径规划问题时，需在一确定空间内对障碍物建模，在实际应用中路径搜索效率较低。RRT（Rapidly Random-exploring Trees）算法[4-6]因快速随机搜索和无需建模等特点，无需预处理，因而在路径规划问题上得到广泛运用，能有效解决高维空间和复杂环境下的路径规划问题[7]。

经典RRT算法具有随机性大、避障能力强、实时性弱与搜索效率低等特点[8]。为了解决搜索效率低的问题，研究人员在经典RRT算法基础上提出了很多改进方法，如偏向RRT算法[9]。偏向RRT算法在一定程度上解决了经典RRT算法效率低的问题，却遗留了随机性大的缺点。本文在加入目标引力思想的经典RRT算法基础上首先引入可变步长思想，借助可变步长的鲁棒性，让随机搜索树朝着目标点方向扩展生长，无需对全局空间进行随机采样，解决了随机性大的问题，但搜索效率较低[10-11]。

为解决经典RRT算法效率较低、复杂度高的问题，本文在改进的RRT算法基础上引入双向生长策略。改进后的RRT算法不仅避障能力强，而且路径搜索效率高，很好地解决了获取最优路径与搜索效率低之间的矛盾。

1 经典RRT算法

经典RRT算法是从状态空间一初始点出发，通过随机采样扩展增加新节点，生成一个随机扩展树，当随机树中的新节点包含目标点或进入目标区域时，初始点到目标点间至少形成一条以随机树新节点组成的路径[12]。

假设在二维工作空间内，C为系统的状态空间。从初始点X-init出发搜索扩展随机树T，对随机树T逐步构建，构建过程如图1所示。

在状态空间C中，T为扩展树，X-init为初始状态点，X-goal为目标状态点。状态空间C中路径不通区域称为障碍区X-obs（X-obsX），路径可通区域称为自由区X-free（X-freeX）。X-rand（X-randX-free）为每次扩展随机树时在C空间的自由区域中随机取的点，X-near为每次扩展随机树时随机树中与X-rand最近的点，在X-near和X-rand的连线上求X-new（X-newX-free）。一个随机扩展树T从初始点X-init出发，生成 K个顶点的算法基本结构如下：

RRT_BCV（X-init，X-goal）

Ti（X-init）；

for k=1 to K do

X-rand=random_state（）；

X-near=nearest_neighbor（X-rand，T）；

u=select_input（X-rand，X-near）；

X-new=new_state（X-near，u，t）；

if collision（X-new）

continue；

T.add.vertex（X-new）；

if ||X-near-X-good||

return Reached；

Return T

随机树T生长过程中，函数random_state（）在状态空间中随机选取一点X-rand；函数nearest_neighbor（）在当前搜索树上选取离X-rand距离最近的节点X-near加以扩展；函数select_input（）在X-rand与X-near结合下得到输入U。根据给定标准，在输入U中选择一个输入，使得X-near尽可能接近X-rand，生成一个节点X-near，函数new_state（）得到新节点X-new。每次扩展得到新节点后均要判断其是否在障碍区域内，若是，则返回到for循环重新选取新的随机点；若否，则直接将其加入当前树中。当加入的新节点与目标点间的距离足够小时，路径搜索结束，生成规划后的路径。

RRT算法扩展生长时的最小单位为步长ρ。经典RRT算法在状态空间C中随机扩展新节点X-new时，以ρ为固定步长计算新节点X-new位置时的方法如式（1）所示。

2 改进后的经典RRT算法

2.1 引入目标引力思想的经典RRT算法

针对经典RRT算法随机性大的问题，许多学者提出了解决方法。本文将人工势场法中的目标引力思想引入到经典RRT算法，确定目标后使随机树朝着目标点或目标区域方向扩展生长。改进后的RRT算法只需局部随机采样，故在减小经典RRT算法随机性的同时改善了路径的光滑性[13]。

引入目标引力思想的经典RRT算法在规划路径时的关键，是在路径从初始点随机扩展后的每一个节点处都引入一个目标引力函数，新节点计算方法如式（2）所示。

引入目标引力思想后，经典的RRT算法有效减小了路径规划时的随机性，与经典RRT算法相比，不仅具有随机方向的随机点x-rand，还增加了目标区域方向的目标点x-goal。目标点x-goal是新节点x-new生成的主要影响因素，新节点x-new的位置会随着步长的变化而变化。当ρ大于k-ρ时，新节点将朝着随机点x-rand方向生长，此时x-rand跟经典RRT算法的随机点选取很接近，具有大随机性和强避障能力；当ρ小于k-ρ时，新节点x-new朝向目标点x-goal生长，随机树将朝着目标点或目标区域扩展。

机器人应用所处的工作环境都较为复杂[14]。从初始点到目标点路径规划时，障碍物是不可避免的。引入目标引力思想的经典RRT算法适用于无障碍的理想环境与少障碍物环境，当遇到多障碍物的复杂工作环境时，因不具有经典RRT算法的随机性，不能顺利绕开障碍物，导致最终无法规划出有效路径。

2.2 引入可变步长的经典RRT算法

本文在引入目标引力思想的经典RRT算法基础上引入可变步长策略，实现RRT动态随机与强避障能力优点。改进后的算法在随机树扩展新节点x-new时起着关键作用，即在x-rand与x-near的连线上以一个步长为距离确定生长新节点x-new。在障碍物环境下，可变步长可以有效利用经典RRT算法的随机性。当遇到障碍物时，可取ρ大于k-ρ，此时随机树将具有经典RRT算法的随机性，朝着随机点方向扩展，不会碰到障碍物；当没有遇到障碍物时，可取ρ

引入可变步长的经典RRT算法保证了随机树从初始点朝着目标点方向生长，同时保证了RRT算法的强避障能力与良好的路径光滑性。

路径规划中的时间复杂度是算法的重要参数之一[15]。经典RRT算法因需对全局空间进行扩展，生长的节点较多，因此时间复杂度是RRT算法需要考虑的因素。许多改进后的RRT算法在路径规划上可以接近最优解，但时间复杂度较高，引入可变步长的经典RRT算法在扩展新节点时，无需通过计算和比较多个扩展随机点的值来确定新节点。

2.3 引入双向生长策略的经典RRT算法

经典RRT算法从初始点到目标点随机扩展生长时随机性很大，搜索效率低；而引入目标引力思想与可变步长策略的经典RRT算法有效解决了随机性大和避障能力低的问题，但路径搜索效率较低。本文在此改进算法基础上引入双向生长策略，以期解决效率低的问题。

双向生长策略指从初始点和目标点同时生成两棵RRT隨机树，两棵随机树同时扩展生长后于状态空间某一点相遇时，生成一条有效路径。算法在初始点x-init和x-goal同时开始构造RRT树T-i和T-j，从任意一个RRT树中选取与x-rand距离最近的节点x-near，在x-rand与x-near连线上找到一个距离x-rand最近的点x-new，将其加入RRT树中。同时再寻找另一个RRT树中距离x-new最近的点，在扩展过程中试图用相同的算法将两树连接起来。若两树中的两节点距离足够小，则可确定T-i与T-j连通，基本算法如下：

RRT_BCV（X-init，X-goal）

Ti（X-init），Tj（X-goal）

for k=1 to K do

X-rand=random_state（）；

if not（BCV_CONNECT（Ti， X-rand）=trapped） then

if（BCV_CONNECT（Tj，X-new）=reached） then

Return PATH（Ti，Tj）；

swap（Ti，Tj）；

Return（Ti，Tj）；

BCV_CONNECT（T，X）

Repart

X-near=nearest_neighbor（ X-rand，T）；

u=select_input（ X-rand，X-near）；

X-new=new_state（X-near，u，t）；

if collision（X-new）

continue；

T.add.vertex（X-new）；

T.add.edge（X-near，X-new）；

改进后的RRT算法（下文简称为可变步长的双向RRT算法）中的两棵随机树在同时扩展生长时，不仅具有目标引力产生的朝目标点方向生长特性，还具有可变步长产生的高避障能力。两随机树各自朝着自己的目标点方向生长，当它们产生的新节点X-new在空间中某点相遇时，将形成一条有效路径，最终规划出的路径将接近最优解。

3 实验结果与分析

设机器人为圆点状，将可变步长的双向RRT算法实验仿真数据与可变步长的RRT算法实验仿真数据进行比较，验证算法的正确性与高效率。实验环境为Windows 2007，Intel（R） Core（TM）2.3GHz、2G内存，编译工具为MATLAB 2 012b。图2中左下角的机器人为圆点状，即为根节点；状态空间1 000×1 000，X轴与Y轴坐标范围均为[0，1 000]，原点为[0，0]，两点间的直线距离约为1 414m；实验环境中障碍物为黑色斑块，大小形状不一，随机设置。

实验1：对可变步长的RRT算法进行仿真实验，如图2所示。从左下角初始点出发的随机树在状态空间C中扩展搜索，生成的新节点用小黑点表示。从左下角初始点出发的随机树生长线用黑点和细线相间表示，规划出的路径用粗线表示。图3是路径规划仿真效果。

实验2：对可变步长的双向RRT算法进行仿真实验，图4是实验仿真结果，从初始点出发的随机树与从目标点出发的随机树在状态空间C中同时扩展搜索，生成新节点，在某点相遇后生成一条路径。由于目标引力的作用，新节点生成位置比较集中。从左下角初始点出发的随机树生长线用星点与细线相间表示，从右上角目标点出发的随机树生长线用黑点和细线相间表示，规划出的路径用粗线表示。图5是路径规划仿真效果。

表1是两组实验20次仿真数据的平均值。通过实验数据对比可知，在实验所设定的已知静态障碍物环境下，可变步长的双向RRT算法路径搜索成功率高；平均新节点个数生成量减少近一半，算法复杂度降低；平均路径长度为1 556，规划出的路径也相对改进前的算法趋于平缓；路径搜索所需平均时间显著减少，搜索效率提高近一倍。可变步长的双向RRT算法解决了最优路径与效率低间的矛盾，最终规划出的路径更接近最优解。

4 结语

本文针对可变步长的经典RRT算法在路径搜索时效率较低与算法复杂度高的问题，在算法中引入双向生长策略，两随机树从初始点和目标点同时搜索扩展，生成的新节点在状态空间中的某点相遇后形成一条有效路径，进而完成对机器人的路径规划实验。

实验仿真结果表明，可变步长的双向RRT算法在路径搜索时除具有避障能力强、随机性小等特点外，还具有生成新节点少、算法复杂度低和路径搜索效率高的优点，最终生成的路径更接近最优解，具有一定的实用价值。

参考文献：

[1] 徐飞.基于改进人工势场法的机器人避障及路径规划研究[J].计算机科学，2016，43（12）：293-296.

[2] 朱爱斌，何大勇，罗文成，等.基于双目视觉方法的可穿戴式导盲机器人研究[J].机械设计与研究，2016，32（5）：31-34.

[3] 万善余，范迪.基于遗传算法的信号灯配时[J].电子科技，2017，30（3）：45-52.

[4] LAVALLE S M. Planning algorithms.Illinois[M].USA：University of Illinois Press，2004.

[5] 刘成菊，韩俊强，安康.基于改进RRT算法的RoboCup机器人动态路径规划[J].机器人，2017，39（1）：8-15.

[6] LAVALLE S M，KUFFNER J. Rapidly random-exploring trees：progress and prospects[C].Proc of the International Workshop on Algorithmic Foundations of Robotics. Hanover，USA，2000：54-59.

[7] 刘佳顺，刘检华，张之敬，等.基于任意时间RRT算法的三维自动布线技术[J].机械工程学报，2016，52（13）：156-165.

[8] 王全，王维，李焱，等.基于混合策略的轮式机器人路径规划方法[J].计算机工程与应用，2014，54（4）：45-49.

[9] LAVALLE S M，KUFFNER J. Rapidly random-exploring trees：progress and prospects[C]. Proceedings of Algorithmic and Computational Robotics：New Directions，2001：293-308.

[10] AGIRREBEITIA J，AVILES R，DE BUSTOS I F，et al. A new APF strategy for path planning in environments with obstacles[J]. Mechanism and Machine Theory，2005，40（6）：645-658.

[11] 宋曉琳，周南，黄正瑜，等.改进RRT在汽车避障局部路径规划中的应用[J].湖南大学学报：自然科学版，2017，44（4）：30-37.

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

[13] 段锁林，王琳琳.智能轮椅路径规划优化问题的研究[J].计算机仿真，2015，32（3）：412-416.

[14] 徐雪松，杨胜杰，陈荣元.复杂环境移动群机器人最优路径规划方法[J].电子测量与仪器学报，2016，21（2）：274-282.

[15] 高庆吉，王磊，牛国臣，等.基于目标导向的连续型机器人路径规划[J].北京航空航天大学学报，2013，39（11）：1486-1490.

（责任编辑：杜能钢）