基于RRT改进算法的AGV路径规划_程满.pdf

第 51 卷收稿日期：2022年8月10日，修回日期：2022年9月20日基金项目：国家自然科学基金项目（编号：61761049，61261022）；云南省专业学位研究生教学案例库及研究生优质课程项目资助。作者简介：程满，男，硕士研究生，研究方向：AGV路径规划，轮式搬运机器人。杨光永，男，博士，副教授，研究方向：机器人技术，传感器技术。徐天奇，男，博士，教授，研究方向：智能电网，电气自动化。黄卓群，女，硕士研究生，研究方向：信号处理，智能控制。刘叶，男，硕士研究生，研究方向：电机，智能控制。1引言自动导引车（AGV）在自动化、灵活性方面具有独特的优势，使AGV成为智慧仓储，智能物流自动化上的最优选择。路径规划是AGV的核心，所以设计合理高效的路径规划算法十分重要1。AGV的路径规划目标在于通过采用某个算法，在包含有各种障碍物的空间中，避开障碍物于自由空间中安全行驶，最终生成一条从起点到终点的无碰撞的安全路径。路径规划的核心是算法，算法的高效、安全、路径最优等指标经常作为算法优劣的衡量项。目前对于一些常见算法的分类主要有全局路径规划和局部路径规划；图搜索算法和几何结构搜索算法；传统算法和人工智能算法。因为算法本身某些方面的局限性，所以在面对不同问题或者不同环境的时候不同的算法及其改进算法被用来解决某些基于 RRT 改进算法的 AGV 路径规划程满杨光永徐天奇黄卓群刘叶（云南民族大学电气信息工程学院昆明650500）摘要传统快速扩展随机树（RRT）算法在搜索空间中，随机采样生成我们所需要的树，由树的起始点直到终点，探索出一条无障碍的路径。采样点是均匀随机，导致算法过于随机，生成路径的效率不高且生成路径质量偏低，在面对狭窄通道时容易导致算法局部循环甚至搜索失败，传统算法生成的路径过于曲折不利于跟踪行驶。针对这些问题，改进后的算法在RRT的基础上，增加算法贪婪计算和目标节点的启发；将扩展的采样点重点集中于一定的区域，满足正态分布。仿真实验表明，改进后的算法效率更高，生成路径质量高，面对狭窄通道这个传统难题也可以高质高效地生成一条路径，利于AGV跟踪行驶。关键词AGV；RRT改进算法；路径规划；正态分布；启发式变步长中图分类号TP242.6DOI：10.3969/j.issn.1672-9722.2023.03.013AGV Path Planning Based on Improved RRT AlgorithmCHENG ManYANG GuangyongXU TianqiHUANG ZhuoqunLIU Ye（School of Electrical and Information Engineering，Yunnan Minzu University，Kunming650500）AbstractThe traditional fast expanding random tree（RRT）algorithm generates the tree we need by random sampling in thesearch space，and explores an obstacle free path from the start point to the end point of the tree.The sampling points are uniform andrandom，which leads to the algorithm is too random，the efficiency of generating path is not high and the quality of generated path islow.When facing the narrow channel，it is easy to cause the algorithm local cycle or even search failure.The path generated by traditional algorithm is too tortuous，which is not conducive to tracking.In order to solve these problems，based on RRT，the improvedalgorithm adds greedy computation and the heuristic of target nodes，and focuses the extended sampling points on a certain area tomeet the normal distribution.Simulation results show that the improved algorithm has higher efficiency and higher quality of generated path.In the face of the traditional problem of narrow channel，it can also generate a path with high quality and efficiency，whichis conducive to AGV tracking.Key WordsAGV，improved RRT algorithm，path planning，normal distribution，heuristic variable step sizeClass NumberTP242.6总第 401 期2023 年第 3 期计算机与数字工程Computer&Digital EngineeringVol.51 No.36062023 年第 3 期计算机与数字工程类型的问题，采取算法某些方面的优点，去粗取精的混合算法也越来越受到研究者的喜爱23。RRT算法于1998年由Lavall所提出的4，基于环境空间的随机采样点规划的一种算法，节点的扩展不需要预处理，建模简单，速度快并且是一种概率完备算法，同时在高维空间中表现优秀，受到很多研究人员的关注，各种改进算法也相继提出511。Lavalle等随后又提出了双向随机树（bi-RRT）12，在起始点和目标节点同时生长两棵树，两个方向进行扩展，加快算法的速度；RRT-connect算法又是在bi-RRT算法的基础上引入了贪婪的思想；Frazzoli等提出了RRT*算法13，在生成新节点的时候，通过比较代价替换父节点，随着迭代次数的增加生成 的 路 径 向 最 优 路 径 逼 近；Nasir 等 提 出RRT*-smart算法，在损失算法的随机性的代价下获得收敛速度的提升；刘成菊等提出变步长的RRT算法，改变随机树扩展节点时候的步长，加快收敛速度1416。2RRT算法的改进针对 RRT算法的缺陷，本文的改进重点在于通过在扩展节点的时候采用贪婪的思想，对已经规划的好路径进行两次重新选择父节点和布线，使生成的路径接近于最优路径；加入启发函数，将目标节点也加入算法的考量范围，使RRT算法的扩展具有方向性，不再盲目扩展；将节点的扩展集中在一定区域，剔除冗余节点，避免多余无用节点的反复扩展，加快算法的运行速度。2.1选择低成本树进行重新布线当随机树在自由状态空间已经生成的时候，RRT算法的规划器都是选择Xrand最近的Xnearest，并将Xnearest与Xrand连接起来，按照步长生成节点Xnew，不能保证算法的成本约束，当使用低成本树优化之后，规划器将低成本的节点连接起来，从起始点到当前节点保持距离成本的最小值，保障生成路径质量。H 节点是最新生成的Xnew节点，Xnew的父节点Xnearest如图1所示为E节点，起始节点Xstart为A节点。如图1所示，在第一次优化之前，节点路径为A-B-C-E-H，路径代价为11。现在进行第一次优化，以节点H为圆心，以一定长度为半径，作一个圆，将H与I、F、G、K连接，长度都为2，到达节点H有 多 条 路 径，例 如：A-B-I-H、A-B-C-E-F-H、A-B-C-E-G-H、A-J-K-H。将这些路径包括之前未优化之前的那条原始路径的代价进行比较，选择最短的路径代价的那条路径并且将之前的父节点变换成最短路径的父节点，第一次优化后的路径如图2所示。图1第一次优化示意图图2第一次优化重新布线在图2新路径代价为最短的A-B-I-H，此时代价为7。将之前的H实连接线去掉，并将虚线所示的I和H的连接线变成实现，运用贪婪思想计算新节点设定一定值半径范围内的所有节点的代价值计算，取其中最小代价为所走路径，这样生成的路径比较接近于最优路径。第二次优化，重复第一次优化的步骤。图3第二次优化示意图连接H-E、H-F、H-G、H-K比较到达E、F、G、K这四个节点，通过现有树的代价和通过H节点到达的代价，选择代价小的方式到达，重新布线。第二次优化如图4所示。607第 51 卷图4第二次优化重新布线2.2启发式变步长传统的 RRT 算法并没有将目标节点考量进去，树的扩展是随机的，每次扩展的步长也是一个固定的步长，现在改进的RRT算法将目标节点加入考量范围，树的扩展具有了方向性，扩展的方向不再仅是由随机方向的随机点Xrand单独控制，而是随机方向的Xrand和目标终点的Xend共同控制。新的步长扩展公式为Xnew=Xnearest+(Xrand-Xnearest)Xrand-Xnearest+(Xend-Xnearest)Xend-Xnearest（1）当无障碍物在行驶的路径附近时，引导树的扩展方向更多的朝着目标节点，可以加快目标节点的搜索速度；如果发现障碍物，改变和的值，此时，树的搜索更多地朝向随机搜索方向，和两个值大小的变化，有助于整个路径规划系统更好地逃避出局部最小值。2.3正态分布当随机变量服从数学期望为和方差为2的正态分布时，记作N(,2)。概率密度函数表示为1 2exp(-(x-u)222)（2）二维标准正态分布为p(x,y)=p(x)p(y)=12exp(-x2+y22)（3）若用随机变量v来表示，v=x yT即：p(v)=12exp(-12vTv)（4）由标准正态分布推广到一般v=A(X-u)。p(x)=|det(A)2exp-12(X-u)TATA(X-u)（5）=(ATA)-1（6）p(X)=12|1 2exp-12(x-u)T-1(X-u)（7）将正态分布加入算法中，主要是为了减少相对状态空间，将树的扩展限制在某些区域，使规划的效率提高。本文所使用的多元正态分布公式：P(x)=12d 21|1 2exp-12(x-u)T-1(x-u)（8）其中是协方差矩阵，=UUT，u1,u2是协方差矩阵的特征向量，1、2是相应的特征向量的特征值。图5正态采样点分布图图 5 起点位置为（20，40），终点位置为（90，40），可以有效地将随机采样点集中在一定区域。该算法以起点开始，随迭代增加，树开始扩展，通过规划生成Xnew节点，此节点的扩展不仅是在随机点的方向上，而且偏向目标区域，正是因为具有这种偏向性，可以更快地找到第一个解，当第一个解决方案生成之后，用这条路径作为参考，通过正态分布生成样本点，最后找到一条高质量的路径。如上图所示，图中的正态分布的形状取决于两个因素，分别为Cbest和Cmin。整个正态分布的区域可以表示为长度为Cbest，宽度为Cbest2-Cmin2，其中Cbest是所有可行解决方案中成本代价最小的，Cmin是 起 始 点 与 目 标 节 点 之 间 的 欧 氏 距 离，1=Cbest/2，2=Cbest2-Cmin2，若是无障碍空间，那么2的值会降到0，也就是可行路径的最优路径此时就是最短路径，直接生成一条直线连接起始点和终点。3改进算法仿真对比实验所有的对比仿真实验都是在个人 PC 上完成的，基于 Matlab-R2018a，环境地图大小设置为10001000。个人 PC 硬件配置：处理器 Inter（R）Core（TM）i7-