基于改进RRT算法的移动机器人路径规划
郭梦诗冯丽娟代传垒
（郑州科技学院电子与电气工程学院河南郑州450064）
摘要：针对传统RRT算法在多障碍物、曲折狭窄道路等无规律环境下随机性大、收敛速度慢、效率低等问题，提出一种改进RRT路径规划算法，以提高在二维环境下移动机器人的路径规划性能。改进算法通过引入障碍物因子进行区域节点采样，减少采样时间和次数；同时，对新产生的节点进行约束，降低方向随机性，减少目标区域振荡情况，加快搜索速度；此外，剔除冗余节点使路径更加平滑，路径长度缩短且对内存需求降低。通过实验仿真验证：改进算法能满足复杂环境下的避障路径规划，随机性降低速度较快，具有较好的可行性和有效性。
关键词：改进RRT算法路径规划平滑避障
中图分类号：TP242文献标识码：A文章编号：1674-098X(2022)02(a)-0037-04
Path Planning of Mobile Robot Based on Improved
RRT Algorithm
GUO Mengshi FENG Lijuan DAI Chuanlei
(School of Electronics and Electrical Engineering,Zhengzhou University of Science and Technology,
Zhengzhou,Henan Province,450064China)
Abstract:Aiming at the problems of large randomness,slow convergence and low efficiency of traditional RRT algorithm in irregular environments such as multi obstacles and tortuous narrow roads,an improved RRT path planning algorithm is proposed to improve the path planning performance of mobile robot in two-dimensional environment.The improved algorithm reduces the sampling time and times by introducing the obstacle factor to sample the regional nodes.At the same time,the new nodes are constrained to reduce the direction randomness, reduce the oscillation in the target area and speed up the search speed.In addition,eliminating redundant nodes makes the path smoother,the path length shorter and the memory demand lower.The experimental simulation shows that the improved algorithm can meet the obstacle avoidance path planning in complex environment,reduce the randomness quickly,and has good feasibility and effectiveness.
Key Words:Improved RRT algorithm;Path planning;Smooth;Obstacle avoidance
随着科技的发展，机器人机械臂在生产生活中的应用愈加广泛［1］。与此同时，路径规划问题成为此领域的热点及难点问题。由于机器人应用场景广、灵活性强，若避障规划效率低，则工作质量易受到影响［2］。避障规划是指在有障碍物等特定环境下，机器人机械臂在自身和约束条件下寻到一条从起点到终点的无碰撞有效路径［3］。多种路径规划算法被广泛提出，并在实际生产生活中取得了较好的效果，比如基于搜索的粒子算法［4］、A*算法［5］、人工势场法［6］等。以上算法当机器人环境维度、自由度、空间复杂度等增加时，其避障规划复
DOI：10.16660/jki.1674-098X.2201-5640-5994
作者简介：郭梦诗（1993—），女，硕士，助教，研究方向为机器人路径规划及智能控制。
杂度倍增［7］
。快速搜索随机树（RRT ）算法是一种典型
的基于采样的规划方法，此算法不必对环境障碍物进行
精确描述，且在多维复杂环境中效果明显［8］。
传统RRT 算法采样均匀，复杂环境收敛慢，且其搜索路径一般不是最优，因此，大量学者对此算法存在的缺陷提出了多种改进和解决方案。Faris 等人通过引入多次样条曲线将RRT 算法路径点进行排序获得
平滑路径［9］；Gammell 引入空间约束减少规划时间［10］；
尹高扬等人通过改进邻近点的采样选取进行全局采
样，但在搜索时间上有所延长［11］。以上算法在路径规
划长度上明显减少，但运算时耗时较长。故而，如何高效地获取一条可行较优的路径仍是目前避障规划研究的热点和重点。
对于传统RRT 算法搜索慢、路径冗余节点多和终点附近振荡等问题，本文进行了算法改进，使得机器人机械臂在避障路径规划上更加平稳。通过Matlab 仿真验证了本文算法在路径长度和节点数量等方面的有效性。
1基本RRT 算法
传统RRT 算法在1998年由Lavalle 提出［12］
，无需
对环境进行精确建模即可到一条可行路径。此算法的中心思想是从已知的确定的节点作为起始点，通过随机采样的方法在状态空间中无规律地产生大量叶子
节点，通过叶子节点逐渐向目标点靠近的树状结构，当增加的节点中包括终点时，即到一条起点到终点的有效路径。此算法在全局路径规划中应用广泛。传统RRT 算法搜索仿真如图1所示。
算法的扩展示意图如图2所示。RRT 算法的伪代码为：GENERATE _RRT (q start ，K ，Δt
)1T.init (q start
)
2for k =1to K do
3q rand ←Random _Configuration ()4q near ←Nearest _Neighbor (
q rand ，T
)5u ←Select_Input (
q near ，q rand )6q new ←New _Configuration (
q near ，u ，Δt )
7T.add_vertex (q new )
8T.add_edge (
q near ，q new ，u
)
9return T
其中，q start 为搜索起点，q rand 指状态环境中随机采样点，q near 为搜索过程的最近邻点，q new 是扩展后生成的叶子节点。
首先，对算法进行初始化，q start 既是扩展树起始点，同时作为第一个邻近点q near ，随后在空间中随机寻一
点q rand ，
之后距离此点最近距离的点作为下一个邻近点q near ，同时，以一定的扩展步长获得新的节点q new ，且
图1算法搜索扩展仿真示意图
图2算法节点扩展示意图
q new和q near的连线间不能存在障碍物，当q new到终点或到达最大迭代次数时，算法终止。
此算法的有效性已得到充分验证，且在全局搜索和多维空间规划上应用广泛。但算法本身也存在一定的不足，由于传统算法采样均匀、信息引导不充分、缺乏路径导向性，因此，在狭窄或多障碍物等复杂环
境下易出现搜索时间长、占用内存大，且冗余节点多易导致路径转折多、距离长等缺陷。
2改进RRT算法
针对传统RRT的上述问题进行了改进。
首先，对算法添加导向因子，增加路径规划引导域，同时，对环境进行栅格化，可以在低分辨率环境中搜索出有效路径。
其次，去除多余采样节点，可以提高收敛速度。之后改变节点生成方式，在引导域中不断进行扩展搜索，到一条可行无碰撞渐进最优路径。
最后，进行路径简化，同时，路径多余节点剔除后进行平滑，缩短规划路径的长度，满足机器人机械臂平
稳工作的要求。
对于相同的起止点，进行改进前后算法对比，如图3
其中，多岔的细线搜索路线是传统RRT算法规划路径，较粗的路径是改进RRT算法规划路径。左下角为起始点，右上角为目标点。
从图4可以看出，改进的算法在路径长度上有明显的改善，且在运行和搜索时间上有明显优势，通过对比可看出改进算法的高效性和优越性。
此外，经过验证，在非栅格化狭窄空间中，改进算法路径规划也有明显效果，如图5所示。
其中，较细的折线为传统RRT算法，加粗曲线为改进后算法。左上角圆点为起始点，右下角圆点为目标点。通过仿真可明显看出，改进后的算法剔除不必要的冗余节点，使规划路径更简，总体搜索代价更低。3结语
本文针对基本RRT算法在避障规划中的一些不足，对其进行了改进。改进算法剔除了大量冗余节点，并加入引导域指引新节点朝向目标方向搜索。通过两种算法的仿真对比，可验证改进后的算法减少了随机性，能够高效快速地规划出可行路径，同时，在路径长度和平滑方面更优，更符合机器人机械臂在运作过程中的平稳性，整体效果更佳。
reactor technology参考文献
[1]胡嘉阳，韦巍.基于五次NURBS曲线的六轴机器人
多目标轨迹优化[J].电子测量与仪器学报,2020, 34(6):198-203.
[2]王洪斌，尹鹏衡，郑维，等.基于改进的A~*算法与动
态窗口法的移动机器人路径规划[J].机器人,2020, 42(3):346-353.
[3]张玉伟，左云波，吴国新，等.基于改进Informed-RRT*算法的路径规划研究[J].组合机床与自动化
图3两种R R T算法路径搜索图
图4改进R R T算法路径搜索图图5狭窄环境下两种算法路径对比
加工技术,2020(7):5.
[4]WU X,YAN M,WANG J.An improved path planning approach based on Particle Swarm Optimization[C]// International Conference on Hybrid Intelligent Systems. IEEE,2012:157-161．
[5]BB MENG,GAO X.UAV Path Planning Based on Bidi⁃rectional Sparse A*Search Algorithm[J].IEEE,2010: 1106-1109.
[6]CHEN Y B,LUO G C,MEI Y S,et al.UAV path plan⁃ning using artificial potential field method updated by optimal control theory[J].International Journal of Sys⁃tems Science,2016,47(6):1407-1420.
[7]朱佑滔，何志琴，施文烨.多种蚁算法在机械手
臂路径规划中的设计与应用[J].机械传动,2021, 45(4):160-165.
[8]张卫波，肖继亮.改进RRT算法在复杂环境下智能
车路径规划中的应用[J].中国公路学报,2021,34(3): 225-234.
[9]FARIS,JANJOŠ,RON,et al.Niermeyer.Smooth Path-Generation Around Obstacles Using Quartic Splines and RRTs[J].Ifac Papersonline,2017,50(1):9108-9113.
[10]J D GAMMELL,S S SRINIVASA,BARFOT.Informed-RRT:Optimal sampling-base path focused via direct sampling of an admissible ellipsoidal heuristic[C].In⁃ternational Conference on Intelligent Robots and Sys⁃tems IEEE,shanghai,2014:2997-3004. [11]尹高扬，周绍磊，吴青坡.基于改进RRT算法的无人
机航迹规划[J].电子学报,2017,45(7):1764-1769. [12]LAVALLE S M，KUFFNER J J.Randomized kinody⁃namic planning[C]∥Proc.of IEEE International Con⁃ference on Robotics and Automation.Piscataway, NJ:IEEE Press,1999:473-479.
（上接21页）
哈尔滨：哈尔滨工程大学,2018.
[5]王晨阳.船用非能动余热排出系统可靠性分析方法
研究[D].哈尔滨：哈尔滨工程大学,2020. [6]陈艳霞，朱成华，郭健，等.海上浮动核电站总体设计
初探[J].核动力工程,2021,42(3):171-176. [7]郭翔，孔凡富，朱成华，等.浮动核电站设计中的安全
准则研究[J].核动力工程,2021,42(4):244-249. [8]程坤，谭思超.海洋条件下反应堆热工水力特性研究
进展[J].哈尔滨工程大学学报,2019,40(4):655-662.
[9]LIU D,TIAN W,XI M.Study on safety boundary of flow instability and CHF for parallel channels in motion[J]. Nuclear Engineering and Design,2018,335:219-230.
[10]陈炳德，宗桂芳，李长林.AC600非能动安全系统首
期实验研究[J].核动力工程,2000(1):63-67. [11]PARK H S,CHOI K Y,CHO S,et al.Experiments on
the performance sensitivity of the passive residual heat removal system of an advanced integral type reactor[J]. Nuclear Engineering and Technology,2009,41(1): 53-62.
[12]李亮国，苏前华，严超，等.二次侧非能动余热排出系
统流动不稳定性研究[J].原子能科学技术,2019, 53(7):1272-1279.
[13]李亮国，苏前华，郝陈玉，等.二次侧非能动余热排出
系统运行及换热特性研究[J].核科学与工程,2020, 40(4):532-539.
[14]周磊，郗昭，熊万玉，等.基于RELAP5的蒸汽发生器
二次侧非能动余热排出系统影响因素分析[J].核动力工程,2012,33(6):72-75.
[15]皇甫幼明.基于RELAP5的海上浮动电站二次侧非
能动余热排出系统设计与研究[D].哈尔滨：哈尔滨工程大学,2019.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。