7

http://msl.cs.uiuc.edu/rrt/

谁能用易于理解的简单措辞解释 rrt 如何工作？我阅读了网站和维基百科中的描述。

我希望看到的是 rrt 的简短实现或对以下内容的彻底解释：

为什么 rrt 向外增长，而不是在中心周围变得非常密集？它与天真的随机树有什么不同？

我们尝试到达的下一个新顶点是如何选择的？

我知道我可以下载一个运动策略库，但我更愿意在深入研究代码之前理解这个想法，而不是反过来。

4

1 回答 1

18

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

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

伪代码

基本算法如下所示：

  1. 从一个空的搜索树开始

  2. 将您的初始位置（配置）添加到搜索树

  3. 而你的搜索树还没有达到目标（你还没有用完时间）

    3.1。选择一个位置（配置），，q_r（使用一些采样策略）

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

    3.3. 尝试在q_n和之间的树中添加一条边（路径） q_r，如果您可以链接它们而不会发生冲突。

虽然这个描述已经足够了，但在这个领域工作了一段时间之后，我真的更喜欢Steven LaValle 的“规划算法”一书中关于 RRT/RDT 的图 5.16 的伪代码。

树形结构

树最终覆盖整个搜索空间（在大多数情况下）的原因是采样策略的组合，并且总是从树中最近的点开始连接。这种效果被描述为减少Voronoi 偏差。

抽样策略

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

图书馆

如果您真的坚持执行，MSL 库是一个很好的起点，但它自 2003 年以来一直没有得到积极维护。更新的库是Open Motion Planning Library (OMPL)。您还需要一个好的碰撞检测库。

规划术语和建议

从术语的角度来看，很难意识到尽管您在 RRT（早期）出版物中看到的许多图表都是二维的（链接 2d 点的树），但这绝对是最简单的情况.

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

The combination of all possible configurations (or a subset thereof) that can be achieved make up a configuration space (or state space). This can be as simple as an unbounded 2d plane for a point in the plane, or incredibly complex combinations of ranges of other parameters.

于 2012-08-28T12:44:52.323 回答