问快速探索随机树

EN

最简单的RRT算法之所以如此成功，是因为它很容易实现。当你遇到以下情况时，事情往往会变得复杂：

• 需要在超过两个维度上可视化规划概念
• 不熟悉与规划相关的术语，并且；
• 在文献中描述的大量RRT变体中。

伪码

基本算法如下所示：

1. 从空的搜索树开始
2. 在搜索树未达到目标(且未超时)时，将初始位置(配置)添加到搜索树

3.1。选择一个位置(配置)，q_r，(使用一些抽样策略)

3.2。在搜索树中找到离该随机点最近的顶点，q_n

3.3。尝试在树中q_n和q_r之间添加一条边(路径)，前提是可以在不发生冲突的情况下将它们链接起来。

虽然这个描述足够了，但在这个领域工作了一段时间后，我真的更喜欢Steven LaValle的书“规划算法”中的pseudocode of figure 5.16 on RRT/RDT。

树结构

树最终覆盖整个搜索空间(在大多数情况下)的原因是采样策略的组合，并始终从树中最近的点进行连接。这种效果被描述为降低Voronoi bias。

采样策略

选择放置将尝试连接到的下一个顶点的位置是采样问题。在搜索是低维的简单情况下，均匀随机放置(或偏向于目标的均匀随机放置)可以充分发挥作用。在高维问题中，或者当运动非常复杂时(当关节具有位置、速度和加速度时)，或者当配置难以控制时，RRT的采样策略仍然是一个开放的研究领域。

库

如果你真的被困在实现上，MSL library是一个很好的起点，但自2003年以来它一直没有得到积极的维护。一个更新的库是Open Motion Planning Library (OMPL)。你还需要一个好的碰撞检测库。

规划术语和建议

从术语的角度来看，困难的一点是要认识到，尽管您在RRT (早期)出版物中看到的许多图表是二维的(连接2d点的树)，但这是绝对最简单的情况。

通常，需要一种严格的数学方法来描述复杂的物理情况。一个很好的例子是规划具有n连杆的机器人手臂。描述此类手臂的末端需要最小的n关节角度。描述职位的这组最小参数是状态(或某些出版物状态)。单个配置通常表示为q

可以实现的所有可能的配置(或其子集)的组合构成了状态配置空间(或状态空间)。这可以像平面中的点的无界2d平面一样简单，也可以是其他参数范围的令人难以置信的复杂组合。