基于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-10875H、内 存 为 16G、系 统 版 本 为Windows10。3.1无障碍物环境对比实验为了看出更直观的效果，首先在无障碍物环境中进行实验，起点设置为（100，500），目标节点设置为（900，500）。RRT算法的步长为15，实验环境的程满等：基于RRT改进算法的AGV路径规划6082023 年第 3 期计算机与数字工程地图单位为m，时间单位为s，无障碍环境下的仿真实验的迭代次数设置为2000次。100090080070060050040030020010000100 200 300 400 500 600 700 800 900 1000图6无障碍RRT算法仿真100090080070060050040030020010000100 200 300 400 500 600 700 800 900 1000图7无障碍RRT改进算法仿真表1图6和图7参数比较不同算法RRT改进RRT时间/s2.47350.8916行驶距离/m1125.6340804.1749采样节点2001130.4由于算法的随机性，将实验50次的数据取其平均值，改进算法相较于传统算法来讲，运行效率大大提高，算法运行时间缩减了63.95%，距离相较于理想距离更加接近，采样节点减少了93.48%，行走的线路较于传统算法而言，行驶路径较平滑，易于跟踪行驶。3.2狭窄通道环境对比实验当我们探索的路径需用通过一个很狭窄的通道时，过于狭窄的通道会导致我们路径被碰到的概率极其之低，找到路径时间的长短很随机，全靠运气。有时运气好，RRT很快就在狭窄通道找到了路径，运气差的时候，就可能一直无法通过。目前有好多学者都在对RRT算法进行改进，目的在于解决通过狭窄通道这个难题。改进算法将目标节点加入到了启发的一部分，加强了算法通过狭窄通道的能力。以下仿真实验设置一个宽度只有10m的狭窄通道。100090080070060050040030020010000100 200 300 400 500 600 700 800 900 1000图8狭窄通道RRT算法仿真100090080070060050040030020010000100 200 300 400 500 600 700 800 900 1000图9狭窄通道RRT改进算法仿真表2图8和图9参数比较不同算法RRT改进RRT时间/s3.72452.7953行驶距离/m1396.3436803.6503采样节点2588.61517.5改进后的算法是启发式变步长的生长，当扩展开始，无障碍物时候，主要考虑目标节点的启发式生长，当在障碍物附近的时候，主要考虑随机生长状态，可以很好地避障的同时穿过狭窄通道。由于算法的随机性，取50次试验的平均数据，算法的运行时间减少24.95%，行走的路径接近于最短路径，采样节点减少了41.38%。3.3普通环境对比实验100090080070060050040030020010000100 200 300 400 500 600 700 800 900 1000图10普通环境RRT算法仿真609第 51 卷100090080070060050040030020010000100 200 300 400 500 600 700 800 900 1000图11普通环境RRT改进算法仿真表3图10和图11参数比较不同算法RRT改进RRT时间/s13.48678.1776行驶距离/m3062.20162314.7145采样节点6322.72646.3改进后的算法相较于传统算法而言，效率大大提高，运行时间减少了 39.37%，行驶距离减少了24.41%，采样节点减少了58.15%，行驶路径较于传统算法而言，路径较为平缓，转弯的次数较少，易于跟踪行驶。4结语改进后的算法在AGV的路径规划中采用了正态分布的思想，将节点的随机分布探索范围集中在正态分布的区域，避免了无效冗余节点的探索，大大提高算法的执行效率。由传统的固定步长变成了变步长启发式生长，动态调整两个分量的大小，以达到不同环境下的侧重点不同，距离目标过远，重点在于目标节点的启发生长，当附近存在障碍物时，那么此时的重点在于随机生长，可以有效地避障，避免局部最小值。在Matlab上完成了仿真对比实验，验证了算法改进后，生成质量更高的路径，探索节点减少，效率提高，生成较平滑的路径有利于跟踪行驶，同时在面对狭窄通道时也可以快速顺利通过。参 考 文 献1陈秋莲，蒋环宇，郑以君.机器人路径规划的快速扩展随机树算法综述J.计算机工程与应用，2019，55（16）：10-17.CHEN Qiulian，JIANG Huanyu，ZHENG Yijun.Overview of fast extended random tree algorithm for robot pathplanningJ.Computer Engineering and Applications，2019，55（16）：10-17.2司徒华杰，雷海波，庄春刚.动态环境下基于人工势场引导的RRT路径规划算法 J.计算机应用研究，2020：1-5.SHITU Huajie，LEI Haibo，ZHUANG Chungang.RRTpath planning algorithm based on artificial potential fieldin dynamic environmentJ.Computer Application Research，2020：1-5.3刘恩海，高文斌，孔瑞平，等.改进的RRT路径规划算法J.计算机工程与设计，2019，40（08）：2253-2258.LIU Enhai，GAO Wenbin，KONG Ruiping，et al.Improved RRT path planning algorithmJ.Computer Engineering and Design，2019，40（08）：2253-2258.4Lavalle S.Rapidly-exploring random trees：a new tool forpath planning R.Iowa State University，1998.5谭建豪，潘豹，王耀南，等.基于改进RRT*FN算法的机器人路径规划 J.控制与决策，2020：1-7.TAN Jianhao，PAN Bao，WANG Yaonan，et al.Robotpath planning based on improved RRT*FN algorithmJ.Control and Decision，2020：1-7.6陈敏，李笑，武交峰.基于改进RRT算法的差动机器人路 径 规 划J.计 算 机 应 用 与 软 件，2019，36（09）：276-280.CHEN Min，LI Xiao，WU Jiaofeng.Path planning of differential robot based on improved RRT algorithmJ.Computer Applications and Software，2019，36（09）：276-280.7董敏，陈铁桩，杨浩.基于改进RRT算法的无人车路径规划仿真研究 J.计算机仿真，2019，36（11）：96-100.DONG min，CHEN Tiezhuang，YANG Hao.Simulation ofunmanned vehicle path planning based on improved RRTalgorithmJ.Computer Simulation，2019，36（11）：96-100.8孙钦鹏，李猛，王中华.基于改进快速扩展随机树算法的移动机器人路径规划 J.济南大学学报（自然科学版），2019，33（05）：431-438.SUN Qinpeng，LI Meng，WANG Zhonghua.Path planning of mobile robot based on improved fast extended random tree algorithmJ.Journal of Jinan University（Natural Science Edition），2019，33（05）：431-438.9杨瑶，付克昌，蒋涛，等.启发式RRT算法的AGV路径规划 J.计算机工程与应用，2020，56（12）：125-133.YANG Yao，FU Kechang，JIANG Tao，et al.AGV pathplanning based on heuristic RRT algorithm J.ComputerEngineering and Applications，2020，56（12）：125-133.10阮晓钢，周静，张晶晶，等.基于子目标搜索的机器人目标导向RRT路径规划算法 J.控制与决策，2020，35（10）：2543-2548.RUAN Xiaogang，ZHOU Jing，ZHANG Jingjing，et al.Robot target oriented RRT path planning algorithm basedon sub target searchJ.Control and Decision Making，程满等：基于RRT改进算法的AGV路径规划6102023 年第 3 期计算机与数字工程2020，35（10）：2543-2548.11杨莹，张莉，郭瑞鸿，等.基于改进RRT的包裹分拣路径规划算法 J.计算机集成制造系统，2020：1-15.YANG Ying，ZHANG Li，GUO Ruihong，et al.Parcelsorting path planning algorithm based on improved RRTJ.Computer Integrated Manufacturing System，2020：1-15.12C.Urmson，R.Simmons.Approaches for heuristically biasing RRT growth J.IROS，2003，2：1178-1183.13J.Nasir，F.Islam，U.Malik，et al.RRT*-SMART：Arapid convergence implementation of RRT*J.Int.Jour.of Adv.Robotic Systems，2013.14S.Karaman，E.Frazzoli.Sampling-based algorithms foroptimalmotionplanning J .IJRR，2011，30（7）：846-894.15S.Karaman，M.R.Walter，A.Perez，et al.Anytime motion planning using the RRT*J.ICRA，2011：1478-1483.16刘成菊，韩俊强，安康.基于改进RRT算法的RoboCup机器人动态路径规划 J.机器人，2017，39（1）：8-15.LIU Chengju，HAN Junqiang，AN Kang.RoboCup robotdynamic path planning based on improved RRT algorithmJ.Robot，2017，39（1）：8-15.4郭斌，闫富菊，胡晓峰，等.高速机车防滑阀检测系统设计 J.液压与气动，2017（10）：46-51.GUO Bin，YAN Fuju，HU Xiaofeng，et al.Design of anti-skid valve detection system for high-speed locomotiveJ.Chinese Hydraulics&Pneumatics，2017（10）：46-51.5徐文明.气动调节阀智能检测系统的设计与实现 J.自动化仪表，2021，42（12）：33-38.XU Wenming.Design and implementation of intelligent detection system for pneumatic control valve J.Process Automation Instrumentation，2021，42（12）：33-38.6申九菊.PLC 控制系统在电气自动化设备中的应用J.造纸装备及材料，2021，50（5）：13-15.SHEN Jiuju.Application of PLC control system in electrical automation equipmentJ.Papermaking Equipmentand Materials，2021，50（5）：13-15.7王兴，侯礼宁，白雪.基于RFID技术的身份证识别门禁系统开发 J.高技术通讯，2019，29（6）：539-545.WANG Xing，HOU Lining，BAI Xue.Development of IDcard identification access control system based on RFIDtechnolo-gy J.High Technology Letters，2019，29（6）：539-545.8周政伟.PC机与PLC串口通信设计与应用 J.技术与市场，2019，26（4）：133-135.ZHOU Zhengwei.Design and application of serial communication between PC and PLC J.Technology&Market，2019，26（4）：133-135.9蒋俊，冯贻江，屈寒冰，等.设计了一种基于PLC控制的变速操纵阀自动化测试系统 J.液压气动与密封，2018，38（5）：85-87.JIANG Jun，FENG Yijiang，QU Hanbing，et al.An automatic test system for variable speed control valve LOUbased on PLC control is designedJ.Hydraulics Pneumatics&Seals，2018，38（5）：85-87.10崔世亮，刘广斌.基于专家系统的船舶结构优化设计J.船舶物资与市场，2022（5）：24-26.CUI Shiliang，LIU Guangbin.Optimal design of shipstructure based on expert system J.Marine EquipmentMaterials&Marketing，2022（5）：24-26.11林隆荣，彭文竹.物料分拣实验系统的研究与开发J.曲靖师范学院学报，2018，37（3）：44-48.LIN Longrong，PENG Wenzhu.Research and development of material sorting experimental system J.Journalof Qujing Nor-mal University，2018，37（3）：44-48.12黄磊，赵亚明.阀门故障分析及诊断技术研究 J.设备管理与维修，2018（20）：146-147.HUANG Lei，ZHAO Yaming.Research on valve faultanalysis and diagnosis technology J.Plant MaintenanceEngineering，2018（20）：146-147.13娄松涛.基于RBF神经网络的船用低速柴油机故障诊断系统 J.舰船科学技术，2022，44（4）：108-111.LOU Songtao.Fault diagnosis system for marine low-speed diesel engine based on RBF neural networkJ.Ship Science and Technology，2022，44（4）：108-111.14任笑莹，王英民，王奇.基于径向基神经网络的波束优化方法 J.电子与信息学报，2021，43（12）：3695-3702.REN Xiaoying，WANG Yingmin，WANG Qi.A beam optimization method based on radial basis neural networkJ.Journal of Electronics&Information Technology，2021，43（12）：3695-3702.15段铭钰，袁瑞甫，杨艺.基于改进RBF神经网络的采煤机截割煤岩性状智能识别 J.河南理工大学学报（自然科学版），2022，41（1）：43-51.DUAN Mingyu，YUAN Ruifu，YANG Yi.Intelligent identification of coal rock properties for shearer cutting basedon impr-oved RBF neural network J.Journal of HenanPolytechnic University（Natural Science），2022，41（1）：43-51.16张博峰.基于KPCA与径向基神经网络的滚动轴承故障诊断 J.内燃机与配件，2021（13）：133-135.ZHANG Bofeng.Fault diagnosis of rolling bearing basedon KPCA and radial basis neural networkJ.InternalCombustion Engine&Parts，2021（13）：133-135.（上接第588页）611