python代码地址：RRT_and_Pruning

RRT是Rapidly-exploring Random Tree的简写，是基于随机采样的一种路径规划方法，它能够快速地搜索整个状态空间，并偏向于还未探索的空间。

主体部分是节点扩展过程：

**前提：**已知起点、终点和地图。

**步骤：**首先，在空间中随机采样一个节点q r a n d ，然后在当前的树中找到距离该随机点最近的节点q n e a r ，以固定的步长从节点q n e a r  向q r a n d  的方向拓展一步，得到新节点q n e w ，接下来判断扩展边q n e a r q n e w  是否会和障碍物发生碰撞，如果不会，则新节点被添加到树中，如果会发生碰撞，则该节点会被舍弃。

重复上述步骤，直到搜索到终点。则从起点到终点的一条路径就得到了。

它的优势：

快。因为它是随机采样，不需要对空间中所有的点都进行搜索。

不需要对障碍物空间进行精确建模。因为在碰撞检测时它只需要知道给定节点是否为障碍物就可以，而不需要知道障碍物的范围、形状、大小和精确的模型表示。

在多维空间中更具优势。维数越高，节点状态就越多，对于传统路径规划方法，很容易导致维数灾难，而RRT为随机采样，只需要随机更多的维数，而不需要采样空间中的每一个状态，因此维数的升高对RRT的效率并不会有太大的影响。

它的不足：

最显著的一点就是，因为RRT采样的随机性，其得到的路径有很多冗余的节点，增加了路径的长度。当然，现在也有许多的优化方法去得到次优和最优的路径。

最常用也是最简单的优化方法就是剪枝，裁剪掉不必要的节点。如下图所示，a,b两段就可以用c来替换，由三角不等式可知，替换后的路径更短且中间的冗余节点可以被裁剪。

剪枝的方法非常实用，虽然已经有很多对RRT的改进方法，但在实时性上，这个简单的优化方法无疑是最快的，这里给出一个示意图。

对应的python代码托管在GitHub上，包括RRT的生成和剪枝过程：RRT_and_Pruning