基于未知环境下改进的RRT路径规划算法 改进4.0算法

2013/5/23 14:04:05 供稿:孙丽娜,沈政军 打印

本文针对复杂环境下移动机器人的路径规划问题,在随机扩展树算法的基础上,结合势场法的目标引力函数,对原有算法进行了改进。改进后的算法能够引导新叶节点向目标方向扩展,减少了采样点的数目,大大缩短了规划时间,规划出的路径更接近最优或次优;同时,使机器人在执行同一任务的可重复性得到提高,路径也更加的光滑。大量的仿真实验结果表明,该算法显著提高机器人规划效率,具有较高的计算实时性,适合机器人实际应用。



摘 要:针对移动机器人运用快速扩展树(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算法增加新叶节点时,目标引力函数会通过计算每个节点到目标的引力量来影响新节点的选取,引导随机树向目标方向生长。





图2 RRT算法规划的路径

Fig.3 The path planning for RRT algorithm



图3 算法改进后规划的路径
基于未知环境下改进的RRT路径规划算法 改进4.0算法

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

3仿真分析

  

爱华网本文地址 » http://www.413yy.cn/a/25101011/101417.html

更多阅读

win7环境下红色警戒2的联网问题 红色警戒联网平台

win7环境下红色警戒2的联网问题——简介红警2是个很老的游戏了,与现在的主流win7系统有些冲突。虽然能玩一下单机游戏,但是不能连接局域网。如果你有此类麻烦,来这儿就对了。win7环境下红色警戒2的联网问题——工具/原料

GPA的标准算法 gpa标准4.0算法

GPA及其换算办法GPA是英语“GradePointAverage”的缩写,意思是平均分,美国的GPA满分是4分,即A=4,B=3,C=2,D=1。GPA的精确度往往达到小数点后1到2位,如:3.0,3.45等。GPA的计算一般是将每门课程的学分乘以学时,加起来以后除以总的学时,得出平均

linux环境下tinyos的搭建 linux lamp环境搭建

linux环境下tinyos 的搭建 注:安装过程中需要下载很多文件,由于学校网络的原因,可能会有部分文件下载失败,只需要重新输入这条命令就可以继续下载。整个安装过程可能需要4-5小时。1.首先添加tinyos和网易源:在终端输入sudo gedit /etc

声明:《基于未知环境下改进的RRT路径规划算法 改进4.0算法》为网友梦绕魂牵分享!如侵犯到您的合法权益请联系我们删除