Python实现-RRT-Rapidly-exploring Random Tree-快速搜索随机树

- 日理万妓 2022-05-15 02:37 230阅读 0赞

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

![这里写图片描述][70]  
主体部分是**节点扩展**过程：

![这里写图片描述][70 1]

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

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

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

**它的优势：**

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

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

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

**它的不足：**

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

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

![这里写图片描述][70 2]

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

![这里写图片描述][70 3]

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

[RRT_and_Pruning]: https://github.com/hichenway/sampling-based-path-planning
[70]: /images/20220515/6be844255a954d75a6c9c55cf6ff0be4.png
[70 1]: /images/20220515/61495f52bd2847e983e7b49e4e83db3d.png
[70 2]: /images/20220515/14af7de5788b4f1a9cf11fe72957ee16.png
[70 3]: /images/20220515/611b0932379d4c31aa439a4ec87692ec.png