pep*_*dip 7 path-finding motion-planning
任何人都可以解释rrt如何使用易于理解的简单措辞？我在网站和维基百科中阅读了这些描述.
我想看到的是对rrt的简短实现或对以下内容的彻底解释:
为什么rrt向外生长而不是仅仅围绕中心生长非常密集？它与天真的随机树有什么不同？
我们试图接下来的下一个新顶点如何被选中？
我知道有一个我可以下载的运动策略库,但在深入研究代码之前我宁愿理解这个想法,而不是相反.
And*_*ker 18
最简单的RRT算法非常成功,因为它很容易实现.当你:时,事情往往变得复杂:
伪代码
基本算法看起来像这样:
从空搜索树开始
将初始位置(配置)添加到搜索树
而你的搜索树还没有达到目标(你没有时间用完)
3.1.选择一个位置(配置)q_r,(带一些采样策略)
3.2.找到最接近该随机点的搜索树中的顶点,q_n
3.3.尝试添加之间的树边(路径)q_n和q_r,如果你能不碰撞发生联系他们.
虽然这个描述已经足够了,但是在这个领域工作了一段时间之后,我确实更喜欢Steven LaValle的书"规划算法"中关于RRT/RDT的图5.16的伪代码.
树结构
树最终覆盖整个搜索空间(在大多数情况下)的原因是由于采样策略的组合,并且总是希望从树中的最近点连接.该效果被描述为降低Voronoi偏差.
抽样策略
选择放置下一个要尝试连接的顶点的位置是采样问题.在简单的情况下,搜索是低维的,均匀的随机放置(或偏向目标的均匀随机放置)可以充分发挥作用.在高维问题中,或当运动非常复杂时(当关节具有位置,速度和加速度时)或配置难以控制时,RRT的采样策略仍然是一个开放的研究领域.
图书馆
该MSL磁带库是如果你真的被困在实施是一个很好的起点,但它并没有被积极维护自2003年以来更先进最新的图书馆是开放式运动规划库(OMPL) .您还需要一个好的碰撞检测库.
规划术语和建议
从术语的角度来看,难以理解的是,尽管您在RRT(早期)出版物中看到的许多图表都是二维的(连接2d点的树木),但这是绝对最简单的情况.
通常,需要用数学上严格的方式来描述复杂的物理情况.一个很好的例子就是规划一个带有n连杆的机器人手臂.描述这种臂的末端需要最小的n关节角度.描述位置的这组最小参数是配置(或一些出版物状态).通常表示单个配置q
可以实现的所有可能配置(或其子集)的组合构成配置空间(或状态空间).这可以像平面中的点的无界2d平面一样简单,或者是其他参数范围的非常复杂的组合.