摘 要：为解决快速扩展随机树（RRT）算法随机性强，扩展分支多，收敛时间长等问题，本文提出了一种改进的RRT算法。改进的RRT算法可以结合环境约束问题，快速搜索出一条起始节点到目标节点的的路径，该路径比传统RRT算法路径短，且有效减少搜索时间。通过在MATLAB上进行相关路径规划仿真实验，实验结果证明了算法的準确性和有效性。

关键词：快速扩展随机树；环境约束；MATLAB；路径规划

DOI：10.16640/j.cnki.37-1222/t.2018.14.193

1 引言

随着科学技术的迅速发展，机器人在工业，农业等各个领域广泛应用[1，2]，在机器人大量应用的同时，路径规划问题需要被更好的解决[3]。

2 传统RRT算法

传统的快速快展随机树（RRT）算法是由Lavalle[4]提出来的。RRT算法的主要思想是在路径规划中从一个已知数据的节点开始作为起始节点，通过随机采样的方式在环境中无规律的产生大量节点，新产生的节点为叶子结点，通过增加叶子节点的数目，逐渐向目标节点靠近，当增加的叶子节点中包含有目标节点时，便可在随机树中找到一条从起始节点到目标节点的有效路径。传统RRT算法的扩展过程如图2.1所示。

RRT算法的伪代码为：

传统的RRT算法是从一个根节点向周围环境中的未知领域搜索扩展，可以使得路径规划达到全局搜索。但传统RRT算法的随机性，造成路径规划的不稳定性，且搜索环境复杂时，搜索时间过长，收敛性差。

3 改进的RRT算法

基于上述传统RRT算法的不足，本文提出了一种改进的RRT算法，改进的RRT算法通过在路径规划过程中增加平面墙等环境约束，缩短搜索区域，提高了搜索的效率，使得规划的路径比传统RRT算法路径更优。

改进RRT算法的伪代码如下：

改进RRT路径规划图如图3.1所示：

为了更好地对比传统RRT算法和改进RRT算法的路径规划效果，把两种算法编写到同一个环境中进行对比观察，效果图如下3.2所示。其中起始点用绿色节点标识，目标点用红色节点标识，从起始节点到目标节点规划出两条路径，其中红色路径是传统RRT算法的规划路径，用时4.391秒，而黑色路径是改进RRT算法所得，用时1.389秒，在时间上明显后者更优，且由图可以明显观察到改进的RRT算法在路径的长度质量上优于传统算法。

4 总结

由上述的路径规划仿真图可以看出，传统的RRT算法具有随机性，在搜索过程中产生了大量不必要分支，使得搜索路径长，且速度过慢时间花费大。改进后的算法减少了路径规划的时间，提高了搜索效率。通过仿真验证了其可行性。

参考文献：

[1]毕昆，赵馨，机器人技术在农业中的应用方向和发展趋势[J].中国农学通报，2011，27（04）：469-473.

[2]李磊，叶涛，谭民等.移动机器人技术研究现状与未来[J].机器人，2002，24（05）：475-480.

[3]高晓巍.移动机器人的路径规划和仿真[J].计算机仿真，2013，30（07）：379-382.

[4]KHATIB O.Real-Time obstacle Avoidance for Manipulators and Mobile Robots[J].The International Journal Robotics Research，1986，5（01）：90-98.

作者简介：郭梦诗（1993-），女，河南辉县人，硕士研究生，研究方向控制科学与工程，