Abstract
We present an anytime algorithm that generates a collision-free configuration-space path that closely follows a desired path in task space, according to the discrete Frechet distance. By leveraging tools from computational geometry, we approximate the search space using a cross-product graph. We use a variant of Dijkstra's graph-search algorithm to efficiently search for and iteratively improve the solution. We compare multiple proposed densification strategies and empirically show that our algorithm outperforms a set of state-of-the-art planners on a range of manipulation problems. Finally, we offer a proof sketch of the asymptotic optimality of our algorithm.
Abstract (translated)
我们提出了一种随时生成无碰撞配置空间路径的算法，该路径根据离散Frechet距离紧密跟随任务空间中的所需路径。通过利用计算几何中的工具，我们使用交叉产品图来近似搜索空间。我们使用Dijkstra的图搜索算法的变体来有效地搜索并迭代地改进解决方案。我们比较了多种提出的致密化策略，并凭经验证明我们的算法在一系列操作问题上优于一组最先进的规划者。最后，我们提供了算法渐近最优性的证明草图。
URL
https://arxiv.org/abs/1710.06738
