快速搜寻随机树(RRT)算法是一个增量式采样的搜寻技术,这个算法在实际使用中并不要求将任何参数整定,因此具有极好的使用性能。它可以通过增量式方法构造搜寻树,并逐渐增加分辨时间,而不需设定任何高解析度参数。在极端环境情况下,该搜寻树将稠密的充满全部空间,此时搜寻树由许多较小曲线或路经组成,以达到填满全部空间的目的。增量式运算中,所建立的速率搜寻树其方向通常都是稠密采样次序,但一旦该顺序是绝对随意的时,那么这种速率搜寻树就叫做速度搜寻绝对随机树(Rapidly Exploring Random Tree,RRT)[5],而不管该次序为绝对随意的或是确定性次序,都被称之为速率搜寻稠密树(Rapidly Exploring Dense Trees,RDTs),而利用这些计算方式则需考虑微分的各种约束。

算法步骤

考虑二维和三维的操作空间,当环境条件中存在静止障碍物。且当首先初始化速度是随机搜索的状态树T时,并不存在根结点,即为初始状态的树S。然后,先从自由空间中随机选择下一个新的状态结点xrand,然后再以遍过当前的速度随机寻找新状态树T,并寻找在T上离xrand最近的新状态结点xnear,在充分考虑机器人的动力学约束之后,在限制注入集U中选择限制注入U∈U,从最近新状况xnear开始作用,并使用下一次限制时间T到最近新的状态xnew。符合状况xnew和xrand中的限制注入U的最佳控制量之后。把新状况xnew加载在速度随机搜索树T中。然后根据这样的获取方式继续创造新状态,直至达到目标状态G。完成搜索树构造之后,再从目标节点入手,逐渐查找父节点直至达到初始状态,即开始查找下一棵树的根结点,如图所示。

 

因为在寻找流程中充分考虑了机器人的动力学制约,所以形成的路线的可能性非常好。但由于计算的高度随机性,造成了它只具有机率的完全性质。

改进算法

在采集策略方面,RRTGoalBiaS方式在监控机器人随机运动的时候,也以特定几率向最终目标运动;而RRTGoalZoom方式则需要从整体空域,以及在目标地点附近的小空域中完成采集;RRTCon方法则由于增加随机步长提高了计划速率。同样双向规划思想也被引入,从而产生出了RRTExtExt,RRTExtCon,RRTConCon等多个算法。

基本RRT方法,在收敛到终点位置上运行的速率稍许缓慢。为进一步提高计算的质量与稳定性,应进一步对方法加以完善。如进一步提高搜寻工作效率,引入了双向随机搜索树(Bi~RRT),在初始节点上与目标节点之间并行产生二棵RRT,直到最后二棵树相遇,计算才收敛。因此这个计算方法,相对于原始RRT树而言具有相当高的收敛性,而且对于目前路径算法中也是较为普遍的。而由NikAMelchior所提出的粒子RRT树算法中,也考虑了地形的高度不确定性,并因此实现了在较低不确定性条件下搜索树的拓展。但Kuffner和Lavane后来又给出了RRT-connectlv,使节点的扩散与利用率大幅度地增加。在运动计划中,基于距离的概念非常复杂,而且Pengcheng还深入研究了在RRT生长进程中距离函数通过持续学习适应环境改变的方法,以降低间距函数对环境改变的影响敏感。充分思考到从最基本RRT计算器上获得的路径宽度,通常为最佳路径的1.3~1.5倍,因此加拿大的J.Desmithl还开发出了变分法技术,并使之得以实现。AmnA A通过引入KD树,可为二级数据结构加速找到距在实际环境中得到的随机节点数量最近的叶节点,从而减少了搜寻成本。该方法在移动车辆、多维状态空间结构,以及在具有运行学、动力学等微分约束的复杂环境中的运动规划上也已获得了普遍的运用,如图所示。