基于采样的规划算法之RRT家族（一）：快速探索随机树（RRT）

随机路图（PRM）方法中介绍了一种新的产生规划问题图(graph)的方式——随机采样。 严格来说PRM方法只是一种规划问题图构建方法，在构建完规划问题图后，它需要图搜索算法与之配合一起实现对规划问题的求解。相比PRM，本章介绍的快速探索随机树——RRT则是一个完整的规划算法。事实上，RRT算法从起点出发，一边随机采样，一边增量式构建一路径树。

一、背景：从回顾 A* 算法开始

对于下面的栅格路径规划问题（黑色栅格为障碍物、白色栅格为自由区域、绿色栅格为起点，红色栅格为终点），A* 算法是一个非常合适的解决方法。

A* 算法（包括Dijkstra算法和其它 A* 家族算法）这类图搜索算法对规划问题搜索的过程本质上是在构建一棵树，是一个 规划问题图(graph)$\to$