郭梦诗 冯丽娟 代传垒

摘要：针对传统RRT算法在多障碍物、曲折狭窄道路等无规律环境下，随机性大、收敛速度慢、效率低等问题，提出一种改进RRT路径规划算法，以提高在二维环境下移动机器人的路径规划性能。改进算法通过引入障碍物因子进行区域节点采样，减少采样时间和次数;同时对新产生的节点进行约束，降低方向随机性，减少目标区域振荡情况，加快搜索速度;此外，剔除冗余节点使路径更加平滑，路径长度缩短且对内存需求降低。通过实验仿真验证：改进算法能满足复杂环境下的避障路径规划，随机性降低速度较快，具有较好的可行性和有效性。

关键词：改进RRT算法路径规划平滑避障

Path Planning of Mobile Robot Based on Improved RRT Algorithm

GUO Mengshi FENG LijuanDAI Chuanlei

（School of electronic and electrical engineering， Zhengzhou University of science and technology， Zhengzhou， Henan Province， 450064 China）

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]等。以上算法当机器人环境维度、自由度、空间复杂度等增加时，其避障规划复杂度倍增[7]。快速搜索随机树（RRT）算法是一种典型的基于采样的规划方法，此算法不必对环境障碍物进行精确描述，且在多维复杂环境中效果明显[8]。

传统RRT算法采样均匀，复杂环境收敛慢，且其搜索路径一般不是最优。因此大量学者对此算法存在的缺陷提出了多种改进和解决方案。Faris 等人通过引入多次样条曲线将RRT算法路径点进行排序获得平滑路径[9]; Gammell 引入空間约束减少规划时间[10];尹高扬等人通过改进邻近点的采样选取进行全局采样，但在搜索时间上有所延长[11]。以上算法在路径规划长度上明显减少，但运算时耗时较长。故而，如何高效地获取一条可行较优的路径仍是目前避障规划研究的热点和重点。

对于传统RRT算法搜索慢、路径冗余节点多和终点附近振荡等问题，本文进行了算法改进，使得机器人机械臂在避障路径规划上更加平稳。通过Matlab仿真验证了本文算法在路径长度和节点数量等方面的有效性。

1 基本RRT算法

传统RRT算法在1998年由Lavalle提出[12]，无需对环境进行精确建模即可找到一条可行路径。此算法的中心思想是从已知的确定的节点作为起始点，通过随机采样的方法在状态空间中无规律地产生大量叶子节点，通过叶子节点逐渐向目标点靠近的树状结构，当增加的节点中包括终点时，即找到一条起点到终点的有效路径。此算法在全局路径规划中应用广泛。传统RRT算法搜索仿真如图1所示。

算法的扩展示意图如图2所示。

RRT算法的伪代码为：

其中，qstart为搜索起点，qrand指状态环境中随机采样点，qnear为搜索过程的最近邻点，qnew是扩展后生成的叶子节点。

首先对算法进行初始化，qstart既是扩展树起始点同时作为第一个邻近点qnear，随后在空间中随机找寻一点qrand，之后距离此点最近距离的点作为下一个邻近点qnear，同时以一定的扩展步长获得新的节点qnew，且qnew和qnear的连线间不能存在障碍物，当qnew找到终点或到达最大迭代次数时，算法终止。

此算法的有效性已得到充分验证，且在全局搜索和多维空间规划上应用广泛，但算法本身也存在一定的不足。由于传统算法采样均匀、信息引导不充分、缺乏路径导向性，因此在狭窄或多障碍物等复杂环境下易出现搜索时间长、占用内存大，且冗余节点多易导致路径转折多、距离长等缺陷。

2 改进RRT算法

针对传统RRT的上述问题进行了改进。首先对算法添加导向因子，增加路径规划引导域，同时对环境进行栅格化，可以在低分辨率环境中搜索出有效路径。其次去除多余采样节点，可以提高收敛速度。之后改变节点生成方式，在引导域中不断进行扩展搜索，找到一条可行无碰撞渐进最优路径。最后进行路径简化，同时路径多余节点剔除后进行平滑，缩短规划路径的长度，满足机器人机械臂平稳工作的要求。

对于相同的起止点，进行改进前后算法对比，如图3和图4所示。

图3  两种RRT算法路径搜索图

其中多岔的细线搜索路线是传统RRT算法规划路径，较粗的路径是改进RRT算法规划路径。左下角为起始点，右上角为目标点。

图4  改进RRT算法路径搜索图

从图4可以看出，改进的算法在路径长度上有明显的改善，且在运行和搜索时间上有明显优势，通过对比可看出改进算法的高效性和优越性。

此外，经过验证，在非栅格化狭窄空间中，改进算法路径规划也有明显效果，如图5所示。

图5  狭窄环境下两种算法路径对比

其中较细的折线为传统RRT算法，加粗曲线为改进后算法。左上角圆点为起始点，右下角圆点为目标点。通过仿真可明显看出，改进后的算法剔除不必要的冗余节点，使规划路径更简，总体搜索代价更低。

3 结语

本文针对基本RRT算法在避障规划中的一些不足，对其进行了改进。改进算法剔除了大量冗余节点，并加入引导域指引新节点朝向目标方向搜索。通过两种算法的仿真对比，可验证改进后的算法减少了随机性，能够高效快速地规划出可行路径，同时在路径长度和平滑方面更优，更符合机器人机械臂在运作过程中的平稳性，整体效果更佳。

参考文献

[1] 胡嘉阳，韦巍.基于五次 NURBS 曲线的六轴机器人多目标轨迹优化[J].电子测量与仪器学报，2020，34（6）：198-203.

[2] 王洪斌，尹鹏衡，郑维，等.基于改进的 A～*算法与动态窗口法的移动机器人路径规划[J].机器人，2020，42（3）：346-353

[3] 张玉伟， 左云波， 吴国新，等.基于改进Informed-RRT*算法的路径规划研究[J].组合机床与自动化加工技术，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 Bidirectional Sparse A* Search Algorithm[J].IEEE，2010：1106-1109.

[6] CHEN Y B， LUO G C， MEI Y S， et al.UAV path planning using artificial potential field method updated by optimal control theory[J].International Journal of Systems 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 Reichart， Philipp 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].International Conference on Intelligent Robots and Systems IEEE，shanghai，2014：2997-3004.

[11] 尹高揚，周绍磊，吴青坡.基于改进 RRT 算法的无人机航迹规划[J].电子学报，2017，45（7）：1764-1769.

[12] LAVALLE S M，KUFFNER J J. Randomized kinodynamic planning[C]∥Proc. of IEEE International Conference on Robotics and Automation. Piscataway，NJ：IEEE Press，1999：473-479.