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

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

2、1907/rjdk.172931：TP312：A ：1672-7800（2018）006-0013-04Abstract：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 a

3、lgorithm， 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

4、 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； Bidir

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

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

7、高，很好地解决了获取最优路径与搜索效率低之间的矛盾。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-

8、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 doX-rand=random_state（）；X-near=nearest_neighbor（X-rand，T）；u=select_input（X-rand，X-near）；X-new=new_state（X-near，

9、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（）得到新

10、节点X-new。每次扩展得到新节点后均要判断其是否在障碍区域内，若是，则返回到for循环重新选取新的随机点；若否，则直接将其加入当前树中。当加入的新节点与目标点间的距离足够小时，路径搜索结束，生成规划后的路径。RRT算法扩展生长时的最小单位为步长。经典RRT算法在状态空间C中随机扩展新节点X-new时，以为固定步长计算新节点X-new位置时的方法如式（1）所示。2 改进后的经典RRT算法2.1 引入目标引力思想的经典RRT算法针对经典RRT算法随机性大的问题，许多学者提出了解决方法。本文将人工势场法中的目标引力思想引入到经典RRT算法，确定目标后使随机树朝着目标点或目标区域方向扩展生长。改进后

11、的RRT算法只需局部随机采样，故在减小经典RRT算法随机性的同时改善了路径的光滑性13。引入目标引力思想的经典RRT算法在规划路径时的关键，是在路径从初始点随机扩展后的每一个节点处都引入一个目标引力函数，新节点计算方法如式（2）所示。引入目标引力思想后，经典的RRT算法有效减小了路径规划时的随机性，与经典RRT算法相比，不仅具有随机方向的随机点x-rand，还增加了目标区域方向的目标点x-goal。目标点x-goal是新节点x-new生成的主要影响因素，新节点x-new的位置会随着步长的变化而变化。当大于k-时，新节点将朝着随机点x-rand方向生长，此时x-rand跟经典RRT算法的随机点选

12、取很接近，具有大随机性和强避障能力；当小于k-时，新节点x-new朝向目标点x-goal生长，随机树将朝着目标点或目标区域扩展。机器人应用所处的工作环境都较为复杂14。从初始点到目标点路径规划时，障碍物是不可避免的。引入目标引力思想的经典RRT算法适用于无障碍的理想环境与少障碍物环境，当遇到多障碍物的复杂工作环境时，因不具有经典RRT算法的随机性，不能顺利绕开障碍物，导致最终无法规划出有效路径。2.2 引入可变步长的经典RRT算法本文在引入目标引力思想的经典RRT算法基础上引入可变步长策略，实现RRT动态随机与强避障能力优点。改进后的算法在随机树扩展新节点x-new时起着关键作用，即在x-ra

13、nd与x-near的连线上以一个步长为距离确定生长新节点x-new。在障碍物环境下，可变步长可以有效利用经典RRT算法的随机性。当遇到障碍物时，可取大于k-，此时随机树将具有经典RRT算法的随机性，朝着随机点方向扩展，不会碰到障碍物；当没有遇到障碍物时，可取引入可变步长的经典RRT算法保证了随机树从初始点朝着目标点方向生长，同时保证了RRT算法的强避障能力与良好的路径光滑性。路径规划中的时间复杂度是算法的重要参数之一15。经典RRT算法因需对全局空间进行扩展，生长的节点较多，因此时间复杂度是RRT算法需要考虑的因素。许多改进后的RRT算法在路径规划上可以接近最优解，但时间复杂度较高，引入可变步

14、长的经典RRT算法在扩展新节点时，无需通过计算和比较多个扩展随机点的值来确定新节点。2.3 引入双向生长策略的经典RRT算法经典RRT算法从初始点到目标点随机扩展生长时随机性很大，搜索效率低；而引入目标引力思想与可变步长策略的经典RRT算法有效解决了随机性大和避障能力低的问题，但路径搜索效率较低。本文在此改进算法基础上引入双向生长策略，以期解决效率低的问题。双向生长策略指从初始点和目标点同时生成两棵RRT隨机树，两棵随机树同时扩展生长后于状态空间某一点相遇时，生成一条有效路径。算法在初始点x-init和x-goal同时开始构造RRT树T-i和T-j，从任意一个RRT树中选取与x-rand距离最

15、近的节点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 doX-rand=random_state（）；if not（BCV_CONNECT（Ti， X-rand）=trapped） thenif（BCV_CONNECT（Tj，X-new）=reached）

16、thenReturn PATH（Ti，Tj）；swap（Ti，Tj）；Return（Ti，Tj）；BCV_CONNECT（T，X）RepartX-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算法）中的两棵随机树在同时扩展生长时，不仅具有目标引力产生的朝目标点方向生

17、长特性，还具有可变步长产生的高避障能力。两随机树各自朝着自己的目标点方向生长，当它们产生的新节点X-new在空间中某点相遇时，将形成一条有效路径，最终规划出的路径将接近最优解。3 实验结果与分析设机器人为圆点状，将可变步长的双向RRT算法实验仿真数据与可变步长的RRT算法实验仿真数据进行比较，验证算法的正确性与高效率。实验环境为Windows 2007，Intel（R） Core（TM）2.3GHz、2G内存，编译工具为MATLAB 2 012b。图2中左下角的机器人为圆点状，即为根节点；状态空间1 0001 000，X轴与Y轴坐标范围均为0，1 000，原点为0，0，两点间的直线距离约为1

18、414m；实验环境中障碍物为黑色斑块，大小形状不一，随机设置。实验1：对可变步长的RRT算法进行仿真实验，如图2所示。从左下角初始点出发的随机树在状态空间C中扩展搜索，生成的新节点用小黑点表示。从左下角初始点出发的随机树生长线用黑点和细线相间表示，规划出的路径用粗线表示。图3是路径规划仿真效果。实验2：对可变步长的双向RRT算法进行仿真实验，图4是实验仿真结果，从初始点出发的随机树与从目标点出发的随机树在状态空间C中同时扩展搜索，生成新节点，在某点相遇后生成一条路径。由于目标引力的作用，新节点生成位置比较集中。从左下角初始点出发的随机树生长线用星点与细线相间表示，从右上角目标点出发的随机树生长

19、线用黑点和细线相间表示，规划出的路径用粗线表示。图5是路径规划仿真效果。表1是两组实验20次仿真数据的平均值。通过实验数据对比可知，在实验所设定的已知静态障碍物环境下，可变步长的双向RRT算法路径搜索成功率高；平均新节点个数生成量减少近一半，算法复杂度降低；平均路径长度为1 556，规划出的路径也相对改进前的算法趋于平缓；路径搜索所需平均时间显著减少，搜索效率提高近一倍。可变步长的双向RRT算法解决了最优路径与效率低间的矛盾，最终规划出的路径更接近最优解。4 结语本文针对可变步长的经典RRT算法在路径搜索时效率较低与算法复杂度高的问题，在算法中引入双向生长策略，两随机树从初始点和目标点同时搜索

20、扩展，生成的新节点在状态空间中的某点相遇后形成一条有效路径，进而完成对机器人的路径规划实验。实验仿真结果表明，可变步长的双向RRT算法在路径搜索时除具有避障能力强、随机性小等特点外，还具有生成新节点少、算法复杂度低和路径搜索效率高的优点，最终生成的路径更接近最优解，具有一定的实用价值。Reference：1 徐飞.基于改进人工势场法的机器人避障及路径规划研究J.计算机科学，2016，43（12）：293-296.2 朱爱斌，何大勇，罗文成，等.基于双目视觉方法的可穿戴式导盲机器人研究J.机械设计与研究，2016，32（5）：31-34.3 万善余，范迪.基于遗传算法的信号灯配时J.电子科技，2

21、017，30（3）：45-52.4 LAVALLE S M. Planning algorithms.IllinoisM.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 prospectsC.Proc of the International Workshop on Algorithmic Foundations of Robotics. Hanover，USA，2000：54-59.7 刘佳顺，刘检华，张之敬，等.基于任意时间RRT算法的三维自动布线技术J.机械工程学报，2016，52（13）：156-165.8 王全