一种偏向目标型的rrt算法实现.doc

一种偏向目标型的RRT算法实现摘要:本文针对基本快速扩展随机树(RRT)算法存在搜索过于平均、效率低下、用时较长的缺陷,提出了一种偏向目标型的改进型RRT算法。这种算法在生成随机点时以一定概率选择最终目标点作为局部目标点,使树的扩展有一个趋向于最终目标点的趋势,从而加快了算法的收敛速度,优化了规划路径。最后通过Matlab程序仿真,在二维平面上验证了改进型算法相对于基本算法的优越性。关键词:路径规划、RRT算法、偏向目标型引言机器人学是当今科学技术研究的热点问题,它汇聚了各个尖端学科最先进的研究成果。科学家们从上世纪40年代开始着手研制机器人到如今,机器人的发展主要经历了三次技术变革。从最简单的第一代机器人到现在的第三代智能机器人,机器人从只会机械的执行命令逐渐演变成利用各种先进的传感器自动的学****环境,适应环境,并完***类下达的任务。路径规划问题是机器人研究中的重要的组成部分,它的重点就是要使机器人自主并且安全的从起始位姿移动到目标位姿。机器人路径规划主要分为全局路径规划和局部路径规划两大方面。全局路径规划是一种利用环境全局信息的方法,它通常将周边环境信息存储在一张地图中,并且利用这张地图寻找可行路径。全局路径规划的优点是有利于找到全局可行解和最优解,但是它的运算时间长,不适用于快速变化的动态环境。常用的全局路径规划方法有栅格法、可视图法、拓扑法和自由空间法等。局部路径规划只考虑机器人当前能探测到的环境信息,运算速度快、反应迅速,非常适用于动态环境。但其缺点是算法可能无法收敛,不能保证机器人一定能够到达目标点,而且找到的可行路径可能会偏离最短路径。常用的局部路径规划算法有人工势场法、模糊逻辑法、神经网络法和遗传算法等等。RRT算法是最近几年才发展起来的,并且应用比较普遍的一种路径规划算法。它在处理非完整约束的路径规划问题时具有相当大的优势,因为它可以将各种约束集成到算法本身之中,因此对环境要求较低。而且该算法概率完备,在理论上肯定能找到可行路径。但其缺点是搜索过于平均,算法效率较低,而且规划出的路径往往偏离最短路径。本文针对RRT算法存在的缺陷,提出了一种改进的偏向目标型的RRT算法,该算法有效的解决了搜索过于平均的问题,提高了算法效率,而且规划出的路径是更接近于最短路径的次优路径。RRT算法的基本原理RRT算法在路径规划时以状态空间中的一个初始点作为根节点,通过随机采样逐渐增加叶节点的方式,生成一个随机扩展树。当随机树中的叶节点中包含了目标点或目标区域时,便可在随机树中找到一条从根节点到目标点的路径。RRT的扩展方式如下图1所示。图1RRT算法扩展过程图1中T表示当前存在的扩展树,表示随机点,表示离随机点最近的一个树节点,然后在和的连线上以步长step为单位截取一个新节点,如果没碰到障碍物,则将加入到扩展树T中。重复以上步骤直到到达目标区域则算法结束,此时可在树T中找到一条起点到目标点的路径。为了便于计算机编程实现,我们将RRT的构建过程归纳为以下两个表格。其中表1为各参数意义,表2为RRT构建流程。表1RRT算法中的各参数意义S所有空间无障碍空间有k个节点的随机树起始点目标点step步长Dis(q1,q2)S中两点之间的距离表2RRT算法构建流程1=2判断|-|≤step,若是,转到步骤8,不是,转到步骤33生成随机点4找出使Dis(,)≤Dis(q,)5在和的连线上求使Dis(,)=step,并且∈,若存在这样的,转到步骤6,若不存在,转到步骤36在扩展树上增加节点,7判断|-|≤step,若是,转到步骤8,不是,转到步骤38结束改进的RRT算法虽然RRT算法概率完备,在理论上总能找出一条可行路径。但是由于其扩展新节点的方式是在全空间随机产生的,一方面造成扩展树在全空间分布过于平均,算法效率较低;另一方面规划的路径质量不高,通常偏离最短路径较大。针对以上缺陷,我们希望对基本的RRT算法进行改进。经过分析我们得知造成RRT算法上述缺陷的根源是在扩展新节点时,随机点是在全空间随机产生的。借鉴启发式算法的灵感,我们可以在确定随机点时让随机点以一定的概率等于目标点。这样树的扩展就有一个趋于目标点的趋势,而不是在全空间随机分布,从而提高了算法的搜索效率,而且由于树节点的扩展是趋向于目标点的,理论上规划出来的路径也会更加接近于最短路径。还应注意的是改进后的算法在概率上依然是完备的。通过以上分析,我们知道改进的RRT算法流程和基本的RRT算法流程大致相同,只要把第二节中表2的第3个步骤进行如下的改写即可。生成随机点;给定一个0到1的偏置变量Bias,生成一个0到1的随机数rand;如果rand<Bias,则=;否则,不变。,将整个平面划分为了有障碍部分和无障碍物部分,如下