基于采样的运动规划算法-RRT(Rapidly-exploring Random Trees)

RRT是Steven M. LaValle和James J. Kuffner Jr.提出的一种通过随机构建Space Filling Tree实现对非凸高维空间快速搜索的算法。该算法可以很容易的处理包含障碍物和差分运动约束的场景，因而广泛的被应用在各种机器人的运动规划场景中。

图片来源: https://en.wikipedia.org/wiki/Rapidly-exploring_random_tree

1、 Basic RRT算法

原始的RRT算法中将搜索的起点位置作为根节点，然后通过随机采样增加叶子节点的方式，生成一个随机扩展树，当随机树的叶子节点进入目标区域，就得到了从起点位置到目标位置的路径。

伪代码如下：

Basic RRT算法伪代码。图片来源:https://blog.csdn.net/gophae/article/details/103231053

Basic RRT算法扩展过程图片来源:https://www.researchgate.net/profile/Burak_Boyacioglu/publication/306404973/figure/fig1/AS:398553223581697@1472033901892/Basic-RRT-algorithm.png

基于概率的RRT算法伪代码

3、RRT Connect算法

RRT Connect算法从初始状态点和目标状态点同时扩展随机树从而实现对状态空间的快速搜索。

RRT Connect算法图片来源:https://www.cs.cmu.edu/~motionplanning/lecture/lec20.pdf

4、RRT*算法

RRT*算法的目标在于解决RRT算法难以求解最优的可行路径的问题，它在路径查找的过程中持续的优化路径，随着迭代次数和采样点的增加，得到的路径越来越优化。迭代的时间越久，就越可以得到相对满意的规划路径。

RRT Star算法伪代码图片来源：https://blog.csdn.net/gophae/article/details/103231053

图片来源：https://blog.csdn.net/weixin_43795921/article/details/88557317

图片来源：https://blog.csdn.net/weixin_43795921/article/details/88557317

图片来源：https://blog.csdn.net/weixin_43795921/article/details/88557317

图片来源：https://blog.csdn.net/weixin_43795921/article/details/88557317

至此我们就完成了一次Rewrite的过程，新生成的随机树如下。

图片来源：https://blog.csdn.net/weixin_43795921/article/details/88557317

4.2 随机树重布线的过程

随机数重布线过程图片来源：https://blog.csdn.net/weixin_43795921/article/details/88557317

重布线后的随机树如上右图所示。

4.3 RRT*算法效果

从RRT与RRT*的效果可以看出，RRT*的路径规划的结果优于RRT算法。

VS RRT图片来源：https://www.cc.gatech.edu/~dellaert/11S-AI/Topics/Entries/2011/2/21_PRM,_RRT,_and_RRT__files/06-RRT.pdf

VS RRT With Obstacles图片来源：https://www.cc.gatech.edu/~dellaert/11S-AI/Topics/Entries/2011/2/21_PRM,_RRT,_and_RRT__files/06-RRT.pdf

算法+赛车动力学实现车辆180度转弯图片来源：https://www.youtube.com/watch?v=KSB_9KE6fWI