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

一种改进RRT算法的机器人路径规划研究摘要：针对传统RRT算法在寻找路径时扩展结点选取的随机性，规划出来的路径常存在冗余节点和众多转折点等缺点，本文提出一种改进的RRT算法。首先，改进后的算法在随机点生成时以一定概率P偏向目标点；其次，引入合向量并加入自适应动态步长，并对新节点的生成进行约束，使产生的节点向目标靠近，也避免了大量无效节点的产生。最后，根据三角形原理对路径进行修剪，修剪后的路径采用三次B样条曲线进行优化。仿真结果表明，与传统的RRT算法相比，改进后的算法在路径长度，路径规划时间，路径平滑程度，生成节点数量等方面均有较大提升。关键词：路径规划；RRT算法；目标偏向；合向量；B样条曲线0引言随着人工智能的快速发展，各类新型机器人逐渐出现并且迅速地发展。在机器人的众多研究领域中，机器人的路径规划技术成为研究者们的重要研究之一[1-2]。机器人路径规划技术不仅应用于各种工业制造、工程技术上，也逐渐渗透于人们的日常生活中。诸如自动驾驶汽车、无人机技术、多关节机械臂、医疗手术机器人[3-8]等都需要一条满足距离最优、耗时最短，并且不会与障碍物产生碰撞的平滑轨迹。目前，已有大量的路径规划算法被国内外研究学者提出，其中包括概率路线图（PRM）算法，A*算法、粒子群(PSO)算法、神经网络法、RRT算法等。其中PRM算法在复杂环境下的搜索效率低；A*算法的计算复杂度依赖于网格分辨率的完整性，不适合应用于高维环境路径规划；PSO算法容易陷入局部最优解，不适用于局部和高维环境路径规划；神经网络算法则高度依赖于当前的学习环境，泛化能力比较差；RRT算法搜索能力强，不需要对环境进行建模，且易与其它算法结合解决高纬度、复杂环境下的路径规划，不足之处在于算法的后期节点利用率偏低，计算量偏大，路径不稳定[9-12]。针对RRT的不足之处，衍生出一系列的改进算法。Karaman和Frazzoli提出RRT*算法[13]，该算法解决了生成路径并非最优解的问题，但收敛速度缓慢。Kuffner等提出的RRT-Connect[14]算法减少了规划路径的时间消耗。仲健宁等人NEI-RRT*算法[15]，解决了曲折狭窄环境下路径寻找困难的问题。涂睿等人提出的DRT-RRT*[16]算法增强了重规划性能和执行路径的实时优化性能。许万等人提出的SMRS-RRT*[17]算法解决了收敛速度慢、占用内存大的问题。为了实现规划效率与最优路径之间的良好平衡，针对原始RRT算法的盲目搜索，大量无效节点，局部最小值以及目标点附近振荡等问题，提出了一种改进RRT算法。并对改进后的算法所规划出的路径进行优化处理，使输出的路径质量得到有效的提升。1基本RRT算法1.1问题描述给定一个路径规划问题的状态空间，并将其记为，式中的n为空间维度，且。空间中含有障碍物的区域记为，空闲区域记为，两者之间满足。路径的起始点，目标点，机器人的路径函数。当存在，满足，，，即可获得一条从起点到目标点连续且无碰撞的路径点。1.2原理介绍及实现RRT算法由LaValle[18]于1988年提出，可应用于多维的空间规划中。该算法搜索过程类似于树的生长过程。以根节点作为树的路径起始点，不断地生成新的随机点（），当满足碰撞检测，选取随机树中距离最近的节点,连接与。以一定步长向与的连线方向扩展，新生成的节点记为。当以及与两节点间的连线均满足碰撞检测，将加入树中。重复上述步骤，直到扩散的叶子节点到达目标点，则完成整个算法的搜索过程，并返回一条从目标点到根节点的无碰撞路径。节点的扩展方式如下图1所示：图1RRT扩展方式示意图算法的伪代码如下：1~2行，随机树的初始化过程，当满足迭代次数K的情况下进入for循环。3~9行，生成新节点的过程。10~11行，将新节点和边加入随机树。12~16行，结束循环，返回一条从目标点到起始点的无碰撞路径。2改进RRT算法2.1随机点的生成传统RRT算法随机点的生成采用均匀分布函数的方式，生成的节点缺乏目标导向性，每一次生成路径时所需迭代次数也会相差较大。因此，本文决定采用概率偏置的方式来控制采样点的生成，具体方法如下：设一固定值记为，每一次在内随机生成一个数记为。当，随机点以随机的方式生成；当，随机点向目标点附近生成。添加目标方向的引导后，有效增快了原始算法的收敛速度，减少了迭代次数。2.2新节点扩展方式的改进原始RRT算法沿着与的连线方向以固定步长进行采样，因没有加入目标节点的引导方式，扩展树的生成过程中产生大量的无效节点。针对这一缺点，本文以合向量的方式进行采样，同时将固定步长的扩展方式改进为动态步长，并将其引入合向量的表达式中。在上述改进方法的基础上，考虑到采样时采样域可能出现采样域偏离，随机树出现逆向生长的情况，本文通过向量与向量之间的角度决定新节点的选取，可阻止出现逆向生长的情况。引入合向量和动态步长的节点扩展方式如图2所示。图2改进节点扩展方式示意图向量的方向沿着至，权重系数为可变步长，当遇到障碍物时，可变步长的变化为，当没有障碍物的情况下恢复为原步长；向量的方向沿着至，权重系数为。在两个向量的共同作用下，沿着和向量的方向生成新节点。（1）为避免随机树出现反向生长的情况，本文采用如下方法控制的生成。如下图3所示：图3防随机树逆生长示意图向量与向量之间的夹角记为。（2）当，将生成的节点加入随机树中，如图2中角对应的节点；其它情况下，生成的节点会引起采样域的偏离，随机树出现逆向生长的情况，因此将生成的节点视为无效节点，如图2中角对应的节点。上述改进方法可有效避免树的逆生长情况，在探索空间可行轨迹点的同时，加快了算法的规划速度。2.3目标点附近防振荡机制当进入目标点的邻域内，设此邻域是以为半径的圆。若此时的步长仍大于半径，生成的可能出现于邻域外，导致节点在目标点附近振荡的情况。本文采用如下策略避免振荡的情况发生。如下图所示：图4目标点防振荡示意图当筛选出最近点时，首先判断是否到达邻域内。若位于邻域内，则将步长缩短，且此时的步长小于邻域半径；若不在邻域内，则采用原步长生成节点。3路径修剪与平滑3.1路径修剪改进算法后，产生的初始路径仍有较多冗余节点，利用三角形的原理对路径长度进行优化处理。设输出的路径点为,从目标点开始依次向上回溯节点，若两节点之间满足碰撞检测，则将该两点之间的其余节点全部剔除;若发生碰撞，则以不满足碰撞检测的节点作为起点，再依次向上回溯，重复上述操作，直至遍历完整个序列。优化过后的路径转折点，路径长度都得到优化。图5路径剪枝示意图3.2路径平滑上述经过修剪后的路径在转折点处仍不符合机器人运动学规律，为获得平滑的路径，需要对路径进一步优化。B样条曲线的曲率具有一定的连续性，且修改曲线的局部线段时，对曲线的其余部分不产生影响，因此能够很好地控制曲线的平滑度K阶B样条曲线表达式如下：（3）其中为曲线的控制顶点，称为k阶（k-1）次B样条基函数，节点向量确定分段曲线。三次B样条曲线的基函数如公式（4）所示：（4）三次B样条曲线段如公式（5）所示：（5）4仿真实验与分析为了验证改进算法的可行性和优越性，本文选择在matlabR2018a平台下进行仿真验证。验证所采用的硬件实验平台为华硕W519L笔记本电脑，计算机配置为win7操作系统，处理器i5-4210U，主频2.40GHz，运行内存8GB。4.1仿真实验在matlab仿真平台选取三种不同复杂程度的地图进行验证，三种地图的大小均为。路径规划的起始点均为（1,1），目标点（500,500）。初始扩展步长为40，目标点阈值为30，最迭代次数为3000，权重系数为0.1。仿真结果如图6所示:地图1基本RRT算法(b)地图1改进RRT算法(c)地图2基本RRT算法(d)地图2改进RRT算法(e)地图3基本RRT算法(f)地图3改进RRT算法图6不同算法路径规划图表1地图1的仿真数据对比算法时间/s路径长度/m采样点/个路径节点数/个基本RRT算法10.5921952.7202331.225.42改进RRT算法1.6861737.817834.924.24变化率-84.08%-22.56%-89.46%-83.32%表2地图2的仿真数据对比算法时间/s路径长度/m采样节点数/个路径节点数/个基本RRT算法14.07441284.5800442.8833.78改进RRT算法6.07581083.5380186.089.36变化率-56.83%-15.65%-57.98%-72.29%表3地图3的仿真数据对比算法时间/s路径长度/m采样节点数/个路径节点数/个基本RRT算法11.58201199.4560368.7631.60改进RRT算法5.7317971.73172.026.88变化率-50.51%-18.99%-53.35%-78.23%表的数据经过50次仿真实验取平均值所得。由图6（），表仿真测试的数据可知：在三种不同复杂程度的地图中，改进后的算法在时间性能上分别提高了84.08%、56.83%、50.51%;路径长度上缩短了22.56%、15.65%、18.99%;采样节点数减少了89.46%、57.98%、53.35%;路径节点数减少了83.32%,72.29%;78.23%。上述数据证明，改进后的算法在性能上具有一定的提升。4.2路径平滑优化上述生成的路径仍存在部分转折点，转折点处的路径并不满足机器人的运动学规律。本文采用三次B样条曲线对改进后的RRT算法生成的路径再次优化处理。优化过后的路径如图7所示:(a)地图1优化结果(b)地图2优化结果(c)地图3优化结果图7三次B样条优化图5结语本文针对原始RRT算法路径规划时的不足之处，提出了改进方法。首先，以概率偏置的方式对随机点的生成进行引导，有效避免了随机点的盲目生成。生成新节点时，采用启发式的思想，以合向量的方式并在此基础上引入目标点防振荡和随机树防逆生长机制后，大大减少了冗余节点的产生，提高了路径规划的效率。最后，对输出的路径进行优化处理，首先采用三角形原理使用贪婪策略对冗余点进行剔除，再采用三次B样条曲线对剔除冗余节点后的路径进行平滑处理。针对三种不同复杂程度的地图进行仿真实验，仿真实验的结果证明了改进算法的有效性和优越性。参考文献[1]栗红生,刘莹.复杂路径下机器人路径规划优化方法仿真[J].计算机仿真,2014,31(01):407-411.[2]郝宗波,洪炳熔.未知环境下基于传感器的移动机器人路径规划[J].电子学报,2006(05):953-956.[3]LiZ,LiangH,ZhaoP,etal.EfficentLaneChangePathPlanningbasedonQuinticsplineforAutonomousVehicles[C]//2020IEEEInternationalConferenceonMechatronicsandAutomation(ICMA).IEEE,2020.[4]PadillaG,KimKJ,ParkSH,etal.FlightPathPlanningofSolar-PoweredUAVforSustainableCommunicationRelay[J].IEEERoboticsandAutomationLetters,2020,PP(99):1-1.[5]ZhenXU.Rotaryunmannedaerialvehiclespathplanninginroughterrainbasedonmulti-objectiveparticleswarmoptimization[J].JournalofSystemsEngineeringandElectronics,2020,31(1):130-141.[6]InotsumeH,KubotaT,WettergreenD.RobustPathPlanningforSlopeTraversingUnderUncertaintyinSlipPrediction[J].IEEERoboticsandAutomationLetters,2020,5(2):3390-3397.[7]袁蒙恩,陈立家,冯子凯.基于单目视觉的多种群粒子群机械臂路径规划算法[J].计算机应用,2020,40(10):2863-2871.[8]SayolsN,SozziA,PiccinelliN,etal.Global/localmotionplanningbasedonDynamicTrajectoryReconfigurationandDynamicalSystemsforAutonomousSurgicalRobots[C]//2020IEEEInternationalConferenceonRoboticsandAutomation(ICRA).IEEE,2020.[9]冯来春.基于引导域的参数化RRT无人驾驶车辆运动规划算法研究[D].中国科学技术大学,2017.[10]张广林,胡小梅,柴剑飞,赵磊,俞涛.路径规划算法及其应用综述[J].现代机械,2011(05):85-90.[11]NoreenI,KhanA,HabibZ.OptimalPathPlanningusingRRT*basedApproaches:ASurveyandFutureDirections[J].InternationalJournalofAdvancedComputerScienceandApplications,2016,7(11).[12]陈秋莲,蒋环宇,郑以君.机器人路径规划的快速扩展随机树算法综述[J].计算机工程与应用,2019,55(16):10-17.[13]KaramanS,Frazzoli