摘 要：针对移动机器人运用快速扩展树(RRT)算法进行路径规划，随机性大的问题，提出了一种目标引力式的RRT路径规划算法。该算法在RRT算法的基础上，引入了一个目标引力函数，促使扩展随机树朝目标点方向生长。仿真结果表明，该算法提高了复杂环境下机器人路径规划的效率，能够得到接近于最短的路径，并对同一任务的规划具有一定的可重复性，能够安全的避开障碍物。
关键词：路径规划；快速扩展随机树(RRT)；目标引力函数
文献标识码：A 中图分类号： TP24
The Improved RRT Path Planning Algorithm based on Unknown Environment
SUN Lina，SHEN Zhengjun
(College of Automation & Electronic Engineering，Qingdao University of Science and Technology, 266042, China)
Abstract: Aiming to solve the uncertainty using rapidly-exploring random tree (RRT) for path planning algorithm, an algorithm of mobile robot path planning based on target gravity is proposed. The algorithm introduces target gravitational function, which makes the random tree grow toward the target. Simulation results show that the algorithm improves path planning efficiency in the complex environment; the path is close to the shortest path, avoids obstacles safely and has a certain repeatability for the planning of same task.
Key Words: Path Planning; Rapidly-Exploring Random Tree (RRT); target gravitational function
路径规划技术是移动机器人研究领域的一个重要方面，主要解决如何在工作空间中找到一条从起始点到终点的最优路径，并在运动中能够安全无碰撞的绕过障碍物。在未知环境下，机器人没有先验知识，不能离线做出一次性的全局规划，只能依靠实时探测的局部环境信息规划局部路径，如何规划出全局路径且使路径较优，研究者已经提出了不少解决方法和策略[1,2]。然而，在环境趋于复杂或障碍物的数目增加时，如何避免震荡和死锁，如何使机器人所走路径全局最优或较优，仍是有待解决的问题。
快速扩展随机树（RRT）是目前应用比较广泛的基于采样的单查询运动规划方法，通过状态空间的随机采样点，把搜索导向空白区域，从而寻找一条从起点到目标点的路径规划，适合于复杂环境和变化场景的路径规划。但是RRT算法所具有的采样随机性，产生了路径规划实时性不高，在执行同一任务时可重复性比较差和很难规划出最优路径等问题。
目前RRT算法产生了许多改进，如具有启发式的RRT算法、基于滚动窗口的RRT算法等[3-5]，可是产生的路径存在绕远或者出现明显的拐角，使路径不平滑；或产生死锁振荡等。为此，本文引入人工势场法中的目标引力，使规划路径接近最优或次优，并改进了路径不平滑这一缺陷，通过合理的设置引力系数，克服了局部极小的问题。
1 RRT算法分析
RRT算法是以状态空间中的一个初始点作为根节点，用过随机采样扩展，逐渐增加叶节点，生成一个随机扩展树，当随机树的叶节点中包含了目标点或目标区域中的点时，从初始点到目标点之间的一条以随机树的叶节点组成的路径就是路径规划。
图1 RRT的构建
Fig.1 The RRT construction
由于RRT算法是按照树枝的生长路径进行规划，从而导致规划的路径有时接近最短路径，有时远离最短路径，缺乏光滑性，并对同一任务的规划缺乏可重复性。该算法具有很多的随机性，其本身所包含的一些缺点，对其在移动机器人中的应用产生了一定的限制。
2 改进的RRT算法
将人工势场法中的目标引力思想引入RRT算法，引导随机树朝着目标方向生长，大大减少规划时间,提高了算法的实时性保证了规划路径的最优性，改进路径不光滑的缺点，避免了产生局部极小，使算法在规划路径方面的能力得到很大的提高。
在通过RRT算法增加新叶节点时，目标引力函数会通过计算每个节点到目标的引力量来影响新节点的选取，引导随机树向目标方向生长。
3仿真分析
图2 RRT算法规划的路径
Fig.3 The path planning for RRT algorithm
图3 算法改进后规划的路径
Fig.3 The path planning for improved RRT algorithm
仿真实验结果显示：通过合理地设置引力系数，使改进后的算法保留了RRT算法中向空旷地带搜索的特性，可以快速绕过障碍物找到可行路径，大大减少了不必要的扩展，提高了机器人运动的实时性，使生成的路径相对平滑，满足机器人机器人在复杂环境下的路径规划。
4结论
本文针对复杂环境下移动机器人的路径规划问题，在随机扩展树算法的基础上，结合势场法的目标引力函数，对原有算法进行了改进。改进后的算法能够引导新叶节点向目标方向扩展，减少了采样点的数目，大大缩短了规划时间，规划出的路径更接近最优或次优；同时，使机器人在执行同一任务的可重复性得到提高，路径也更加的光滑。大量的仿真实验结果表明，该算法显著提高机器人规划效率，具有较高的计算实时性，适合机器人实际应用。
参考文献
[1] 张纯刚,席裕庚.动态未知环境中移动机器人的滚动路径规划及安全性分析.控制理论与应用, 2003, 20(1): 37-44.
[2] 王丽.移动机器人路径规划方法研究[D].西北工业大学硕士论文.2007,3.
[3] 康亮,赵春霞,郭剑辉.未知环境下改进的基于RRT算法的移动机器人路径规划[J].模式识别与人工智能.2009,22(3)337-343.
[4] MelchiorNA, SimmonsR. Particle RRT for Path Planning with Uncertainty[J].Proc of the IEEE International Conference on Robotics and Automation. Roma, Italy, 2007:1617- 1624.
[5] 冯林,贾菁辉.基于对比优化的RRT路径规划改进算法[J].计算机工程与应用,2011,47 (3):210-213.
[6] 王滨,金明河,谢宗武等.基于启发式的快速扩展随机树路径规划算法[J].机械制造,2007, 45 (12):1-4.
[7] 宋金泽,戴斌,单恩忠等.一种改进的RRT路径规划算法[J].电子学报,2010,2A (38):225-228.
[8] 高云峰,黄海.复杂环境下基于势场原理的路径规划方法[J].机器人,2004,26(2):114-118.
QQ交流群
