论文标题
高维机器人运动计划的稀疏多级路线图
Sparse Multilevel Roadmaps for High-Dimensional Robot Motion Planning
论文作者
论文摘要
稀疏的路线图对于紧凑的状态空间很重要，以确定不可行的问题并在有限的时间内终止。但是，稀疏路线图不能很好地扩展到高维计划问题。在先前的工作中，我们通过使用多级抽象来简化状态空间，在高维计划问题上表现出了改进的计划绩效。在这项工作中，我们通过开发一种新颖的算法，即稀疏的多级路线图计划器（SMLR），将稀疏路线图概括为多级抽象。为此，我们使用光纤束的语言表示多级抽象，并通过使用可见性区域的限制抽样概念来概括稀疏的路线图计划者。我们认为SMLR是通过稀疏路线图计划者的继承而在近乎最佳的近乎最佳范围内完成的。在评估中，我们在挑战性计划问题方面的稀疏路线图计划者，特别是高维问题，包含狭窄的段落或不可行的问题。因此，我们展示了稀疏的多级路线图作为可行且不可行的高维计划问题的有效工具。
Sparse roadmaps are important to compactly represent state spaces, to determine problems to be infeasible and to terminate in finite time. However, sparse roadmaps do not scale well to high-dimensional planning problems. In prior work, we showed improved planning performance on high-dimensional planning problems by using multilevel abstractions to simplify state spaces. In this work, we generalize sparse roadmaps to multilevel abstractions by developing a novel algorithm, the sparse multilevel roadmap planner (SMLR). To this end, we represent multilevel abstractions using the language of fiber bundles, and generalize sparse roadmap planners by using the concept of restriction sampling with visibility regions. We argue SMLR to be probabilistically complete and asymptotically near-optimal by inheritance from sparse roadmap planners. In evaluations, we outperform sparse roadmap planners on challenging planning problems, in particular problems which are high-dimensional, contain narrow passages or are infeasible. We thereby demonstrate sparse multilevel roadmaps as an efficient tool for feasible and infeasible high-dimensional planning problems.
