基于改进RRT算法的AGV路径规划研究

胡兵　向凤红　毛剑琳

摘要：路径规划是自动导引小车（AGV）控制中的核心问题之一。针对经典RRT算法在静态全局状态空间中随机采样搜索节点时随机性大与效率低的问题，提出了一种改进的RRT（快速搜索随机树）路径规划算法。该算法结合双向搜索功能与自适应目标引力思想，利用双向搜索速度快与自适应目标引力朝目标点方向生长的特性，使AGV在规划路径时路径搜索效率更高，路径更平滑。实验仿真结果证明，改进的RRT算法可以在有效提高路径搜索效率的同时生成最优路径。

关键词：路径规划；自动导引小车；RRT；双向搜索；自适应目标引力

DOIDOI：10.11907/rjdk.172598

中图分类号：TP311

文献标识码：A文章编号文章编号：16727800（2018）003002804

英文摘要Abstract：The path planning of automatic guided vehicle is one of the core issues in the control. For the classical RRT algorithm in global static random sampling in the state space search node is random and low efficiency problem， we propose an improved RRT （rapidly randomexploring trees） path planning algorithm. This algorithm combines the two the search function and adaptive target gravity theory， using the twoway search speed and characteristics of adaptive target gravity toward the target growth path， AGV path planning in higher searching efficiency and smoother paths. The experimental simulation results. The results show that the improved RRT algorithm can effectively improve the path search efficiency and generate the optimal path at the same time.

英文关键词Key Words：path planning； AGV； RRT； bidirectional search； adaptive target gravity

0引言

自动导引小车（Automatic Guided Vehicles，AGV）作为物流业、制造业、机场、军事以及烟草业等行业中的自动化柔性制造设备，得到了越来越多的关注[1]。路径规划是指机器人在当前环境中按照一定标准搜索出一条从起始状态点到目标状态点，并且能够绕开障碍物的最优或次优路径，是自动导引小车控制中的核心问题之一[2]。AGV在运行环境中会遇到包括充电桩、工作站及存贮站等障碍物，而其主要任务就是避障及路径规划，最后生成一条畅通的路径。

AGV在运行过程中除需要获取周围信息避开障碍物外，还需要使规划出的路径长度和时间更短，效率更高。许多国内外学者正在研究AGV的路径规划问题，研究出许多可行方法，包括人工势场法、遗传算法、神经网络法及RRT算法等[3]。其中，RRT算法由Steven M LaValle[4]于1998年首先提出，为了进一步优化路径，后来学者在其基础上进行改进后提出偏向RRT[5]、双向RRT[67]等算法。双向RRT算法在一定程度上解决了经典RRT算法在搜索路径时速度慢的问题，而随机性大的问题未能解决。

针对经典RRT算法在静态全局状态空间中随机采样搜索节点时随机性大与效率低的问题，本文提出一种将双向搜索功能与自适应目标引力相结合的RRT算法，即在双向RRT算法的基础上加入人工势场法中的目标引力思想策略[8]，并使目标引力具有自适应周围环境的功能。借助自适应目标引力让随机搜索树不仅能够朝着目标点方向扩展生长，还能顺利地避开障碍物，在此过程中无需建模和对全局空间随机采样。改进后的RRT算法能够在AGV路径规划时提高路径搜索效率和避障能力。

1问题描述

AGV的运行环境较为复杂，包括静态环境与动态环境[9]，本文针对静态环境对AGV的规划路径进行优化。静态环境是指AGV运行路线周围属于恒态环境，包括车间柱子、设备、噪音及电磁干扰等。它影响到AGV行走路径的选择及AGV的稳定性。运行环境（状态空间）可以分为障碍空间与自由空间。为了避开障碍物规划出一条合理路径，AGV在障碍空间应放慢运行速度，并改变方向避開障碍物；在自由空间应加快运行速度向目标点生长。因工作环境不同，AGV的形状大小会不一样，为了研究需要可设AGV为一圆点状，空间中的障碍物形状不一，包括车间柱子、设备等，可随机设置。AGV所处的虚拟工作环境可定义为如图1所示，此时在AGV的路径规划中需解决的两个核心问题如下：

（1）效率问题。AGV在全局空间中进行路径规划，需要获取全局环境信息，增加了算法的时间复杂度。

（2）避障问题。障碍物是AGV在运行中必不可少的环境因素，AGV不能合理地避开障碍物，将不能顺利到达目标点，最终无法规划出一条通畅的路径。

2AGV路径规划优化算法

AGV的路径规划问题与许多因素有关，包括时间、空间等，经典RRT算法不能很好地满足问题的需求。因此，针对该问题，本文提出一种基于自适应目标引力的双向RRT路径规划算法。

2.1经典RRT算法

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

假设AGV的工作空间属于二维，系统的状态空间为C，从初始点Xinit开始来搜索扩展随机树T，对随机树T进行逐步扩展构建，其构建过程如图2所示。

2.2引入目标引力的双向RRT算法

经典RRT算法在AGV路径规划中，从初始点到目标点随机搜索生成的路径避障能力很强，但搜索效率低。针对AGV路径规划问题（1），本文在经典RRT算法基础上提出引入目标引力的双向RRT算法。

Step1：分别以初始点和目标点为起点同时生成随机树Ti和Tj。当两棵树扩展生长后于某一点相遇时，路径产生。算法在初始点Xinit和Xgoal同时开始构造随机树，从任意一个随机树中选取与Xrand距离最近的节点Xnear，在Xrand与Xnear的连线上找到一个距离Xrand最近的点Xnew，将其加入随机树中。同时再寻找另一个随机树中距离Xnew最近的点，在扩展过程中试图用相同的算法将两树连接起来，若两树中的两节点距离足够小或重合，则可确定Ti与Tj连通，基本算法如下所示：

RRT_BCV（Xinit，Xgoal）

1： Ti（Xinit），Tj（Xgoal）

2： for k=1 to K do

3： Xrand=random_state（）；

4： if not（BCV_CONNECT（Ti，Xrand）=trapped） then

5： if（BCV_CONNECT（Tj，Xnew）=reached） then

6： Return PATH（Ti，Tj）；

7： swap（Ti，Tj）；

8： Return（Ti，Tj）；

BCV_CONNECT（T，X）

1： Repart

2： Xnear=nearest_neighbor（Xnear，T）；

3： u=select_input（Xrand，Xnear）；

4： Xnew=new_state（Xnear，u，t）；

5： if collision（Xnew）

6： continue；

7： T.add.vertex（Xnew）；

8： T.add.edge（Xnear，Xnew）；

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

双向RRT算法具有路径搜索速度较快和随机性大的特点[11]。若随机性大的问题继续存在，随机树生成的路径会缺少光滑性，路径搜索效率不高，而且多次规划后得到的路径不尽相同，也不一定为最优路径。

Step2：对于双向RRT算法随机性大的问题，许多学者提出了不同的方法，本文将人工势场法中的目标引力思想加入到双向RRT算法，其功能是确定目标后使随机树朝着目标点或目标区域扩展生长。该算法只需在局部进行随机采样，不仅减小了双向RRT算法的随机性，而且提高了算法的路径搜索效率，改善了路径的光滑性，确保规划出最优路径。

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

Xnew=Xnear+ρXrand-Xnear‖Xrand-Xnear‖+Xgoal-Xnear‖Xgoal-Xnear‖（1）

其中，ρ为朝着随机点方向生长的步长，k为引力场系数，k与ρ之积kρ为朝着目标点方向生长的步长。

引入目标引力思想后的双向RRT算法有效地减小了路径规划时的随机性。与双向RRT算法相比，该算法不仅具有原来随机方向的随机点Xrand，还增加了目标区域方向的目标点Xgoal，目标点Xgoal是新节点Xnew生成的关键影响因素，新节点Xnew的位置会随着步长的变化而变化。当ρ>kρ时，新节点将朝着随机点Xrand方向生长，此时Xrand跟双向RRT算法的随机点的选取很接近，具有很大的隨机性，强避障能力得以彰显；当ρ

AGV在实际应用中所处的工作环境较为复杂。在现实环境的工作空间从初始点到目标点路径规划时，障碍物是不可避免的因素，无障碍物只是理想环境。引入目标引力思想的双向RRT算法适用于无障碍的理想环境与少障碍物的环境，当遇到多障碍物的复杂工作环境时，因没有双向RRT算法一样大的随机性，可能不能顺利地绕开障碍物，从而不能规划出有效路径。

2.3引入自适应目标引力策略

引入目标引力的双向RRT路径规划算法的AGV在有障碍物的环境中可能不能规划出合理高效的最优路径，无法实现它的实际价值，也显现不出双向RRT算法避障能力强的优良特性。针对问题（2），本文在问题（1）改进后的基础上提出自适应目标引力的双向RRT算法。

随机树在扩展新节点Xnew时起着关键作用，即在Xrand与Xnear的连线上以一个步长为距离来确定生长新节点Xnew。在障碍物环境下，自适应目标引力可以有效地利用双向RRT算法的随机性与目标引力使路径朝向目标点发展。利用函数collision（Xnew）判断随机树生长时步长在状态空间C中随障碍物的有无来自适应变化，方法如式（2）所示。

Collision（Xnew）=Xrandρ>kρ

Xgoalρ

其中，Xrand代表随机树朝随机点方向扩展，Xgoal代表随机树朝目标点方向扩展。当AGV在运动范围内遇到障碍物时，取ρ>kρ，此时目标引力比较小，随机树将具有双向RRT算法随机性大的特性，绕开障碍物朝着随机点Xrand方向扩展，不会碰到障碍物，具有很强的避障能力；而在运动范围内没有遇到障碍物时，取ρ

自适应目标引力的双向RRT算法不仅保证了两棵随机树从初始点和目标点分别朝着目标点和初始点方向生长，而且保证了双向RRT算法的强避障能力和快速搜索效率，路径光滑性也得以改进，从而使路径达到最优。自适应目标引力的双向RRT算法具有的优良特性使得它更适合解决高维空间和复杂环境下的运动规划问题[4]。自适应目标引力的双向RRT算法在遇到障碍物时的随机树扩展示意图如图3所示。

3实验结果与分析

设AGV為圆点状，将自适应目标引力的双向RRT算法的仿真数据与目标引力双向RRT算法的仿真数据进行比较，验证前者算法的优越性与正确性。实验环境为windows 2010，Intel（R） Core（TM）2、3GHZ、4G内存，编译工具为MATLAB 2014b。图4中左下角的AGV为圆点状，即为根节点；状态空间1 000×1 000，X轴与Y轴坐标范围均为[0，1 000]，AGV的起点位置为原点[0，0]，终点位置为目标点[1 000，1 000]；两点间的直线距离为1 414，障碍物为黑色斑块，随机设置，形状大小不一；从初始点（原点）出发的随机树生长线用黑色细线表示，从目标点（终点）出发的随机树生长线用灰色细线表示；规划出的路径用灰色粗线表示。针对所提供的实验环境对每组实验进行25次实验。

实验1：首先通过计算机对目标引力的双向RRT算法进行仿真实验，图4是对应的实验仿真图，从初始点出发的随机树与从目标点出发的随机树在状态空间C中同时扩展搜索，生成新节点，在某点相遇后生成一条路径。由于目标引力作用，新节点的位置比较集中，图5是路径规划仿真结果。

实验2：通过计算机对自适应目标引力的双向RRT算法进行仿真实验，图6是对应的实验仿真图。由于引入自适应目标引力策略，生成较少的新节点后就能将路径连通，图7是路径规划图。

表1是每组实验中25次实验数据的平均值，通过实验数据可以得出，AGV在静态的全局状态空间运行时，与实验1相比，实验2在实验1的基础上引入自适应目标引力策略后可以很好地避开障碍物，不会像双向RRT算法一样随机扩展新节点，减少了路径生成时间，降低了时间复杂度，提高了搜索效率，使自适应目标引力的双向RRT算法在已知静态环境下规划出的路径更接近最优解。实验表明：与目标引力的双向RRT算法相比，自适应目标引力的双向RRT算法具有明显的优越性和正确性。

4结语

针对AGV路径规划的效率问题与避障问题，本文以经典RRT算法为基础提出一种双向搜索功能与自适应目标引力相结合的RRT算法。双向搜索虽能提高路径搜索效率，但随机性大而不能达到最优路径[12]。引入目标引力的双向RRT算法既保证了双向RRT算法良好的路径搜索效率，又解决了其随机性大的问题，无需对全局空间进行搜索，避障能力却有所减弱，可能导致目标不可达。自适应目标引力的双向RRT算法在扩展新节点时通过周围环境有无障碍物来控制随机树的生长方向，不仅能够引导新节点朝着目标点方向扩展生长，还能有效避开障碍物，算法复杂度低，路径搜索效率高，同时规划出的最优路径比之前更光滑。实验仿真数据证明：自适应目标引力的双向RRT算法在AGV路径规划的效率问题与避障问题上具有兼得特性，该改进方法对进一步深入研究AGV路径规划问题具有实际参考价值。

参考文献参考文献：

[1]赵德云，杨厚华，王哲.基于模糊神经网络控制的AGV避障路径规划仿真[J].机电工程，2010，27（9）：2731.

[2]肖本贤，齐东流，刘海霞，等.动态环境中基于模糊神经网络的AGV路径规划[J].系统仿真学报，2006，18（9）：24012404.

[3]郭二东，刘楠嶓，吴立辉，等.一种基于遗传算法的AGV路径规划方法[J].科技创新与生产力，2016，6（8）：8788.

[4]LAVALLE S M. Department of computer science[C]. TR9811，Ames，USA，lows State University： Technical Repeat，1998.

[5]LAVALLE S M，KUFFNER J. Proceedings of algorithmic and computational robotics： new directions[C]. Rapidly Randomexploring Trees：Progress and Prospects，2001：293308.

[6]QURESHI AH，AYAZ，Y. Intelligent bidirectional rapidlyexploring random trees for optimal motion planning in complex cluttered environments[J].Robotics and Autonomous Systems，2015，68（1）：111.

[7]王凡，冯楠，胡小鹏.一种基于RRTConCon改进的路径规划算法[J].大连理工大学学报，2014（6）：637643.

[8]郝利波，侯媛彬.基于一种改进的RRT算法的足球机器人路径规划[J].西安科技大学学报，2011，31（1）：8185.

[9]马志远.智能控制下的AGV路径规划研究[J].河南科技，2013（19）：98.

[10]张浩杰，龚建伟，姜岩，等.基于变维度状态空间的增量启发式路径规划方法研究[J].自动化学报，2012，39（10）：16021610.

[11]HI LIN.2DSpan resampling of BiRRT in dynamic path planning[J].International Journal of Automation and Smart Te，2015，4（4）：3948.

[12]莫栋成，刘国栋.改进的快速探索随机树双足机器人路径规划算法[J].计算机应用，2013，33（1）：199201.

责任编辑（责任编辑：何丽）