有人能用简单易懂的话解释一下RRT是如何工作的吗？我已经在该网站和维基百科上看了详细描述。
我希望看到一个简短的RRT实现或对以下内容进行深入解释：
RRT为什么向外扩展而不是只在中心附近密集生长？它与简单的随机树有何不同？
下一个要尝试到达的新顶点是如何选择的？
我知道有一个可以下载的运动策略库，但我更愿意在深入代码之前先理解这个想法，而不是另一种方式。
1个回答
18
"The simplest RRT algorithm has been successful because it is easy to implement. However, things can become complicated when:
- visualizing planning concepts in more than two dimensions - being unfamiliar with the terminology associated with planning - dealing with the numerous variants of RRT described in literature.
Here is the basic algorithm in pseudo code:
1. Start with an empty search tree. 2. Add your initial location (configuration) to the search tree. 3. While your search tree has not reached the goal (and you haven't run out of time): 3.1. Pick a location (configuration), q_r, using a sampling strategy. 3.2. Find the vertex in the search tree closest to that random point, q_n. 3.3. Try to add an edge (path) in the tree between q_n and q_r, if you can link them without a collision occurring."
- visualizing planning concepts in more than two dimensions - being unfamiliar with the terminology associated with planning - dealing with the numerous variants of RRT described in literature.
Here is the basic algorithm in pseudo code:
1. Start with an empty search tree. 2. Add your initial location (configuration) to the search tree. 3. While your search tree has not reached the goal (and you haven't run out of time): 3.1. Pick a location (configuration), q_r, using a sampling strategy. 3.2. Find the vertex in the search tree closest to that random point, q_n. 3.3. Try to add an edge (path) in the tree between q_n and q_r, if you can link them without a collision occurring."
虽然该描述足够详细，但在这个领域工作一段时间后，我更喜欢 Steven LaValle 的书 "Planning Algorithms" 中 图5.16中RRT/RDT的伪代码。
树结构
树最终覆盖整个搜索空间（在大多数情况下）的原因是采样策略和始终从树中最近的点尝试连接的组合。这种效果被描述为减少 Voronoi偏差。
采样策略
下一个要尝试连接的顶点放置在哪里是采样问题。在简单的情况下，搜索维度较低时，均匀随机放置（或朝向目标的均匀随机放置）就足够了。在高维问题或运动非常复杂（关节具有位置、速度和加速度）或配置难以控制时，RRT的采样策略仍然是一个开放的研究领域。
库
如果你在实现中遇到了困难，MSL library 是一个很好的起点，但它自2003年以来就没有得到积极维护。更为更新的库是 Open Motion Planning Library (OMPL)。您还需要一个良好的碰撞检测库。
规划术语和建议
从术语角度来看，难点在于要认识到尽管在 RRT 的出版物（早期）中看到的许多图表都是二维的（连接 2D 点的树），但这是绝对最简单的情况。
通常，需要一种数学严谨的方法来描述复杂的物理情况。一个很好的例子是为具有 n 个连杆的机器人手臂进行规划。描述这样一个臂端需要至少 n 个关节角度。描述位置的最小参数集称为配置（或某些出版物中的状态）。单个配置通常表示为 q。
- Andrew Walker
6
1所以基本上你的意思是（在二维空间中），1.选择一个起始顶点和一个目标顶点。2.随机选择一个位置（p）在二维空间中。3.找到树边缘上距离位置（p）最近的点（q）。4.检查是否可以从（q）移动到（p），如果可以，则添加新的边缘{(p)，(q)}，就这样？5.回到第2步。 - AturSams
谢谢，我真的很喜欢阅读你的回答，并意识到它只是一个随机挑选新“叶子”的树（或采用抽样策略）。有没有常用且简单的抽样策略？ - AturSams
...南希·阿马托（Nancy Amato）小组的出版物，尤其是关于障碍物PRM（OB-PRM）和中轴PRM（MAPRM）。最近，在麻省理工学院的课程欠驱动机器人技术中展示了一些适用于实际机器人和系统的新采样技术。 - Andrew Walker
哇，非常感谢你帮助我迈出第一步。 - AturSams
@AndrewWalker 你好，这个是否依赖于2D矩阵数据结构？或者我可以在随机位置生成随机节点对象吗？ - user3871
RRTs 可以在任何类型的配置/状态空间中工作，不仅限于 2D 空间。2、3 或甚至更高维度都可以正常工作。当您拥有超过约 10 个维度时（例如机器蛇、具有许多连杆的机器臂或蛋白质折叠），您需要仔细考虑如何进行采样。为了达到概率上的完整性，您需要证明采样算法最终会在每个配置的邻域中进行采样的概率为 1 - 在 n 维空间中进行均匀采样是有效的。 - Andrew Walker
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接