基于采样的路径规划算法——RRT

基于采样的路径规划算法——RRT*

在上一篇博客中简介了基于搜索的路径规划算法A*的原理，这篇博客则会从另外一个角度去解决路径规划的问题。首先我们要从RRT算法说起，然后再探讨其优势和缺点然后给出一些改进的方法并介绍RRT*的改进之处。

以RRT为代表的路径规划算法基于以下的思路：一个一个的栅格去找非常的费劲，若能找到一些点构成图代表这个地图，在这个图上再去搜索路径则会十分的快速。

基于采样的路径规划算法——RRT

如图所示，可以看到仅仅用很少的几个点构成的图就能代表这个地图信息，从而找到一条路径。可以极大的降低搜索复杂度从而降低运行时间。这种方法最早被提出来称为概率路图 （Probabilistic Road Map ），可以很容易的想到这种搜索路径的方法分为两个部分：

学习阶段

随机在地图中生成一些点
去掉在障碍物中的点
将临近的点连接起来，并把经过障碍物的连线去掉
将所有的点和边生成一个图结构

过程可以从这个动图中看出

搜索阶段

通过A*或者其他算法在生成图上搜索得到一条可行路径

这样一种方法带来的优势是很明显的，它可以减少对很多点的查询次数，不需要再非常小的栅格中工作。但是它带来的缺点也有很多，有的缺点比较容易解决许多学者便提出一些方法进行一些小修小改，但是有一些缺点却是由其原理决定的，另外一些学者于是提出了许多的改进算法。

易于解决的缺点
- 两个点的连线是否通过障碍物的判断耗时较长。
  
  解决方法：
  
  1、无需对所有的点和连线进行判断是否通过障碍物
  
  2、采用A*找到一条可行路径，判断路径中的连线和节点是否通过障碍物，若通过则把通过的连线和节点从图结构中去掉。
  
  3、重新寻找一条可行路径并判断碰撞，直至找到一条无碰撞的路径。
难以解决的缺点
- 效率低下，需要分成两步操作。
- 无法保证路径是最优的。
- 对于一些狭小的区域，采样点只有很小概率落在里面。导致搜索效率低。
- …

基于以上的分析，有人就提出了很多的改进方法，接下来就根据这些缺点的改进介绍一些经典的算法。、

快速扩展随机树（Rapidly-exploring Random Trees ）

为了提高效率，将之前分成两步的操作合并。有人提出快速扩展随机树的概念，它的步骤如下：

随机生成一个点
在随机生成的点和离它最近的节点的方向上取一定步长，得到新的扩展点
判断新的扩展点是否经过障碍物，没有通过则添加到图结构中
一直扩展直到找到目标点
从目标点反推回来便能得到路径，无需搜索

可以看到这种方法不再需要搜索的步骤，使得效率有一定的提升。但是解决了所有的问题呢？显然不是的，首先它找到的路径依旧是随机的可行路径而非最优的路径。其次在全地图内搜索会导致效率不够高，没有目的性的去搜索肯定的效率低下的，同样对于狭小的、采样概率较小区域的搜索也没有得到解决。因此许多学者又在这个基础上提出了接下来的一些改进方法。

生成两条搜索树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AuoCWzVN-1582531209679)(C:\Users\lyc\AppData\Roaming\Typora\typora-user-images\image-20200224143901716.png)]

可以看到目标点在狭小路径中也生长出一条路径则会大大提高搜索的效率。

RRT（Rapidly-exploring Random Tree ）

为了解决路径最优的问题，学者提出了RRT*算法，和RRT不同的是在拓展图结构的同时，RRT*算法会同时调整自己的图结构，使得当前的结构是最优的，不断迭代下去寻找到的路径自然也会是最优的。

在RRT的基础上，算法流程做出如下改进：

1、得到一个随机点
基于采样的路径规划算法——RRT
2、找到和随机点较近的几个点

3、选择从起点到随机点最短路径，并将随机点添加到图中，父节点为其中一个节点

4、对于未被选中的节点，也和新节点连接起来，形成新的路径，比较新旧路径长度。
基于采样的路径规划算法——RRT
5、若新路径较短，则重组图结构，删除旧路径