RRT 由Steven M. LaValle和James J. Kuffner 于 1998年 在论文《Rapidly-exploring random trees: A new tool for path planning》中提出。
RRT是一种通过构建随机树来有效搜索非凸高维空间的算法。该树是通过从搜索空间中随机抽取的样本点逐步构建的，并且本质上倾向于向问题中未搜索的大片区域生长。虽然存在效率低、路径不平滑等问题，但因其无需预先处理环境信息和适应复杂环境而被广泛应用于无人机等领域。
将搜索的起点位置作为根节点，然后通过随机采样增加叶子节点的方式，生成一个随机扩展树，当随机树的叶子节点进入目标区域，就得到了从起点位置到目标位置的路径。
算法基本步骤(参考：自动驾驶规划算法 - RRT、GoalRRT、RRTStar 等基本原理)
- 以初始点
$P_{init}$ 作为随机树的根节点 - 在构型空间内随机(一般使用均匀分布)生成一个节点
$P_{rand}$ - 然后在随机树中找到和
$P_{rand}$ 距离最近的节点$P_{near}$ - 以点
$P_{near}$ 为端点，如果$P_{near}$ 和$P_{rand}$ 之间的距离大于 步长参数$\rho$ ，则沿着$P_{near} - P_{rand}$ 方向扩展一定的步长$\rho$ ，将另一端点记为$P_{new}$ ；如果$P_{near}$ 和$P_{rand}$ 之间的距离小于等于$\rho$ ，则将$P_{rand}$ 作为$P_{new}$ - 若
$P_{near}$ 与$P_{new}$ 的连线并未与环境障碍发生交叉，则将点$P_{new}$ 和线段$P_{near} - P_{rand}$ 加入到随机树中，成为新的子节点和新的边
若线段$P_{near} - P_{rand}$ 和障碍发生交叉碰撞，则舍弃点$P_{new}$ ，重复上述2-5步骤，直到路径上最后一个节点距离目标位置在一定阈值范围内，则找到了最终路径。(并不能保证最后一次延伸能够刚好到达终点的位置，因此需要设置阈值范围)
- RRT 是一种可以对非凸高维空间快速搜索的算法，可以很容易的处理包含障碍物和差分运动约束的场景
- PRM 算法在一开始就通过抽样在地图上构建出完整的无向图，再进行图搜索，而 RRT 算法则是从某个点出发一边搜索，一边采样
优点：
- RRT 算法不需要启发式函数，可以在存在复杂障碍物的环境里快速规划出一条安全路径，且更适合实际应用，目前常被用于无人机的运动规划中。
- RRT 的快速迭代生长方式决定了其在高维非凸空间的搜索优势。
缺点：
- 稳定性不佳，且内存消耗较大。扩展树生长方向随机，重复规划结果却有很大差异。
- 随机性采样导致相对效率较低。由于快速扩展随机树有随机采样性，没有目标启发导向，因此在采样过程中有很多无效采样节点，致使效率相对变低。
- 路径曲折冗余点较多，光滑性不佳。在 RRT 生成的路径中有许多无用的点，这些冗余点使得路径长度增加。最常用也是最简单的优化方法就是剪枝，裁剪掉不必要的节点。
- 无法在动态障碍物中有效检测路径，不适合于动态环境规划与避障。
步长的设置会影响树的形状
- 当步长太大时，可能由于太过笨拙而无法成功绕过障碍物，且在终点附近来回跳动
- 当步长过小时，生长的速度显然会有所减慢（因为同样的距离要生长更多次），且采样点非常密集
一般来说，空间越复杂，步长越小
生长步长一定要比判断是否为同一个采样点的阈值要大
- 如果步长小于采样点阈值，则采样出来的新节点与最近的节点距离太近（小于设定的阈值），就被认为是相同节点，这就导致采样失败了
Algorithm: RRT Algorithm
--------------------------------------------------
Input: X, x_init, x_goal, n, step_size
Output: A path connecting x_start to x_goal
T.init(x_start)
for i = 1 to n do
x_rand <- sample_state(X);
x_nearest <- nearest_neighbor(T, x_rand);
x_new <- extend(x_nearest, x_rand, step_size);
if CollisionFree(x_nearest, x_new) then
T.add_vertex(x_new);
T.add_edge(x_nearest, x_new);
end
if x_new == x_goal then
success();
end
end随机采样的 RRT 路径规划算法适用于高维度空间，它们以概率完备性(当时间接近无限时一定有解)来代替完备性，从而提高搜索效率
RRT 算法是概率完备的，只要路径存在且规划的时间足够长，就一定能确保找到一条路径解.
注意「且规划的时间足够长」这一前提条件，说明了如果规划器的参数设置不合理（如搜索次数限制太少、采样点过少等）导致算法很快终止，就可能找不到解
-
完备性：是指如果在起始点和目标点间有路径解存在，那么一定可以得到解，如果得不到解那么一定说明没有解存在；
-
概率完备性：是指如果在起始点和目标点间有路径解存在，只要规划或搜索的时间足够长，就一定能确保找到一条路径解；
-
最优性：是指规划得到的路径在某个评价指标上是最优的（评价指标一般为路径的长度）；
-
渐进最优性：是指经过有限次规划迭代后得到的路径是接近最优的次优路径，且每次迭代后都与最优路径更加接近，是一个逐渐收敛的过程
算法类型 算法名称 是否完备 是否最优 基于搜索 A*，Dijkstra 完备 最优 基于采样 RRT,PRM 概率完备 非最优/渐进最优 基于启发 遗传算法，蚁群算法 完备 非最优 普通的RRT算法，包括：RRT，RRT-connect，RRG都是非最优的，而RRT*是渐进最优的
- 基于目标/概率的快速 RRT(Goal-bias RRT):产生随机点
$P_{rand}$ 时，以一定的概率 P 选取目标点$P_{goal}$ 作为$P_{rand}$ - RRT Connect:从初始状态点和目标状态点同时扩展随机树从而实现对状态空间的快速搜索
- RRT*:解决了RRT无法得出最优路径的问题，只要RRT*算法迭代的次数足够多，就一定能找出最优的路径，但是随之而来的就是规划需要的时间变长。