http://msl.cs.uiuc.edu/rrt/
谁能用易于理解的简单措辞解释rrt的工作原理？我阅读了网站和维基百科中的描述。
我希望看到的是rrt的简短实现或对以下内容的彻底解释：
为什么RRT向外生长，而不仅仅是在中心周围非常密集地生长？它与天真的随机树有何不同？
如何选择我们尝试到达的下一个新顶点？
我知道我可以下载一个运动策略库，但我宁愿在深入研究代码之前理解这个想法，而不是相反。
最简单的RRT算法之所以如此成功，是因为它很容易实现。当您执行以下操作时，事情往往会变得复杂：
- 需要在两个以上的维度上可视化规划概念
- 不熟悉与规划相关的术语;
- 在文献中描述的大量RRT变体中。
伪代码
基本算法如下所示：
-
从空搜索树开始
-
将初始位置（配置）添加到搜索树
-
当您的搜索树尚未达到目标时（并且您没有用完时间）
3.1. 选择一个位置（配置），
q_r，（有一些采样策略）3.2. 在搜索树中找到最接近该随机点的顶点，
q_n3.3. 尝试在树
q_n和q_r之间添加一条边（路径），如果可以链接它们而不会发生冲突。
虽然这个描述是足够的，但在这个领域工作了一段时间后，我确实更喜欢Steven LaValle的书"规划算法"中RRT/RDT上图5.16的伪代码。
树结构
树最终覆盖整个搜索空间（在大多数情况下）的原因是因为采样策略的组合，并且始终希望从树中最近的点进行连接。这种效应被描述为减少Voronoi偏差。
抽样策略
选择放置您将尝试连接到的下一个折点的位置是采样问题。在简单的情况下，搜索是低维的，均匀随机放置（或偏向目标的统一随机放置）可以充分工作。在高维问题中，或者当运动非常复杂（当关节具有位置、速度和加速度时），或者配置难以控制时，RRT的采样策略仍然是一个开放的研究领域。
图书馆
如果您真的坚持实现，MSL 库是一个很好的起点，但它自 2003 年以来就没有被积极维护过。 一个更新的库是开放运动规划库（OMPL）。您还需要一个良好的碰撞检测库。
规划术语和建议
从术语的角度来看，困难的是要意识到，尽管您在RRT的（早期）出版物中看到的许多图表都是二维的（链接2d点的树），但这绝对是最简单的情况。
通常，需要一种数学上严格的方法来描述复杂的物理情况。 一个很好的例子是规划具有n-连杆的机器人手臂。描述这种手臂的末端至少需要n关节角度。 这组描述职位的最小参数是一种配置（或某些发布状态）。单个配置通常表示为q
可以实现的所有可能配置（或其子集）的组合构成了配置空间（或状态空间）。这可以像平面中某个点的无界 2D 平面一样简单，也可以像其他参数范围的极其复杂的组合一样简单。