改进的RRT算法在路径规划中的应用

邵伟伟, 朱云国, 胡 超

(铜陵学院 电气工程学院,安徽 铜陵 244061)

0 引言

随着科技的快速发展,移动机器人在日常的应用越来越多,人们对机器人路径规划的研究也在逐渐深入,针对不同的应用环境,研究者提出了多种路径规划算法,如可视图法[1]、A*算法[2]、Dijkstra算法[3]、PRM算法[4]、Voronoi 图法[5]、遗传算法[6]、栅格法[7]、RRT算法[8]等。其中RRT算法具有简单、实时性强、适用于三维空间等特点,其在路径规划的应用中较多,但RRT算法生成随机树的节点具有随机性,这就决定了RRT算法生成的路径通常都不是最优路径,为了提高RRT算法的性能,人们不断地对RRT算法进行改进,以期得到较优的路径。

文献[9]提出通过改变生成节点的概率,生成偏向目标点的节点,即产生目标导向性的节点,从而使随机树朝着目标点生成,这样使得随机树的扩展速度加快,但该方法对复杂的环境适应性不强,只适用于较为简单的环境。文献[10]提出双向生成随机树的算法,即从起点和目标点同时产生随机树,该方法可以缩短随机树生成的时间,大大提升随机树生成的效率,但该方法仍只适用于简单环境,对于复杂的环境,可能得不到规划的路径,或得到路径所需要的时间较长。李磊等[11]提出采用贪婪策略的改进算法,让随机树在生成的过程中朝着目标点的方向进行生长,从而得到最优的路径。文献[12]提出在随机树生成的过程中,通过改变机器人行走的步长和目标点对机器人的吸引力,从而快速地提高随机树的扩展。文献[13] 提出了基于安全场的改进算法,虽然可以大幅减少随机树搜索的时间,但机器人规划的路径比原始算法要长。

1 RRT算法简介

1998年La Valle[14]提出RRT(Rapid Random Tree)算法,他提出在机器人的工作空间中,以机器人的起点作为随机树的起点,将该点作为随机树的父节点,采用随机函数生成随机节点。通过函数选取上述随机生成的节点中的一个节点作为父节点,将生成的父节点作为随机树的起点,并重复上述步骤生成多个节点,直至生成的节点靠近目标点。当生成的节点与目标点的距离在设定的区间内,则将该节点作为父节点,终止节点的生成,将生成的父节点与起点和目标点相连接,得到的随机树的路径即为所要规划的路径。

RRT算法在生成路径的过程中,因其具有简单[15]、实时性强[16]、适用于三维空间[17]等优点,所以在日常的应用中较多。但因其产生的随机节点具有随机性,其生成的路径也是随机的,很难得到最优路径[18]。针对上述情况,本文提出了引导随机树节点生成的概率,通过引入人工势场的思想指引随机树节点朝目标点方向的生成,从而减少随机树产生的时间和随机树的长度。

2 改进的RRT算法

随机树节点的生成具有较强的随机性,生成的节点可能在障碍物附近,为了保证机器人的效率,引导随机树节点生成的概率,并引入人工势场法的思想到RRT算法中,筛选随机树生成的节点。

2.1 生成随机树节点概率的引导

图1 随机树节点的生成图

图2 随机树节点的栅格图

(1)若在25个栅格中不存在障碍物,则随机树随机地在所有的栅格中生成节点。

(2)若障碍物占据n个栅格,则剩余(25-n)个栅格内无障碍物。将第1个空白栅格的中心分别与n个障碍物栅格边沿求欧氏距离,取最小的欧氏距离为该空白栅格与障碍物的欧氏距离,并记为d1,同理分别求剩余空白栅格与n个障碍物栅格边沿的欧氏距离,分别记为d2,d3,……,d25-n,每个空白栅格中生成节点的概率pi为

(1)

2.2 随机树节点的选取

以2.1节的方法引导随机树节点生成的概率,在随机树节点生成后,采用人工势场的思想对生成的节点进行筛选,引导随机树的生成,避免对全局环境的精准建模,从而减小随机树的长度和规划随机树的时间。

如图2所示,针对栅格中生成的随机节点,引入人工势场的思想。由引力势能

(2)

可以求出随机节点和目标点的引力为

G=kp·‖xgoal-xnear‖,

(3)

其中,kp为引力系数,‖xgoal-xnear‖为目标点向量Xgoal和随机节点向量Xrand的几何距离的绝对值。由式(3)可以得到任意随机节点的目标引力函数G(n)为

(4)

图3 增加目标偏向性的随机树节点

通过上述操作生成随机树节点,直至生成的随机树节点与目标点的距离小于设定的阈值,随机树节点的生成停止。

2.3 平滑随机树路径

如图4所示,随机树生成节点的随机性决定了生成的随机树节点具有一定的冗余性,因此需要对产生的节点进行平滑处理。从第2个节点起,依次与起始节点Xinit相连接,若节点Xi+1与起始节点Xinit的连线没穿过障碍物,则将节点Xi删除;若节点Xi+1与起始节点Xinit的连线穿过障碍物,则将节点Xi作为随机树节点,并将节点Xi作为起始节点,重复以上操作。通过上述操作可将冗余的随机树节点删除。

图4 平滑随机树路径的操作

如图5为改进RRT算法的流程图。

图5 改进RRT算法的流程图

3 实验

3.1 实验平台和实验环境简介

实验平台采用的是HCR开源机器人移动平台作为机器人的硬件搭载平台,机器人的主控器采用的是三星Exynos 4412 Soc开发板,机器人搭载有激光雷达、防撞传感器等,它能获取前方0°～180°的障碍物信息,并将障碍物识别出来。机器人如图6所示。在室外随机摆放一些箱子作为障碍物,以一台机器人作为目标点,让另一台机器人进行实验。

图6 机器人的实物图

3.2 随机障碍物的路径规划

随机摆放的障碍物如图7所示,为防止机器人在行走的过程中存在碰撞现象,在路径规划时需要对障碍物进行适当的膨化处理(障碍物膨胀时需要考虑机器人的大小,即障碍物膨胀时把障碍物的尺寸加上机器人的尺寸后再适当放大,因此机器人在行走时可以看成质点,此时机器人从障碍物周围经过时,只要不触碰障碍物就不会发生碰撞)。机器人由起点出发,采用改进的RRT算法进行路径规划,机器人按改进后的算法生成节点和路径,进行路径规划,并走完全程。在机器人采用改进的RRT算法走完全程后,再采用未改进的RRT算法做对比实验,并记录相关数据,采用Matlab软件将其运动轨迹表现出来。图8为其中一次实验的路径轨迹,其中实心圆为机器人。在该次实验完成后,随机地改变障碍物的位置,重复做20次实验,实验结果如表1。

表1 路径长度实验数据

图7 随机障碍物实验图

图8 机器人的行走轨迹

表1记录了滚动RRT路径长度和改进算法路径长度,为了得到较为直观的改进算法和未改进算法的数据,根据上述实验数据可以进一步得到表2。

表2 路径长度分析表

由表2可知未改进的RRT算法,它的路径平均长度为336.7 cm,比改进后的RRT算法的路径平均长度多10.4 cm。未改进的RRT算法,它的路径长度方差为340.54 cm,比改进后的RRT算法的路径方差多10 cm。从这里可以看出改进后RRT算法的路径相对较短,而且相对稳定一些。分析未改进算法和改进后的算法规划的路径最值,可以看出改进后RRT算法的路径比较短。从上述的分析中可知改进后的RRT算法具有可行性。

4 结语

原始RRT算法随机树的生成具有随机性,为了让随机树的生成具有一定的目标导向性,本文提出了改进的算法。本文提出在随机树节点生成的过程中引入人工势场法的思想,降低障碍物附近生成节点的概率,通过人工势场法的思想筛选节点,从而缩短规划的路径。针对生成的随机树节点具有冗余性,本文提出将冗余的节点进行剔除的算法,通过该方法可以剔除多余的节点,减少了规划的节点,从而使规划的路径变短。

改进后的RRT算法,具有规划的路径短、实时性强、实用性高等特点。虽然本文提出的改进算法比未改进的算法性能具有一定的提升,但随机树节点的生成仍具有一定的随机性,针对该局限性,后续的研究应会朝着随机树节点生成的方向研究,尽量让随机树节点的生成具有导向性,使其满足路径最短的要求。