A*-Connect: Bounded suboptimal bidirectional heuristic search
A*-Connect: Bounded suboptimal bidirectional heuristic search
复制标题
A*-Connect：有界次优双向启发式搜索
DOI：
10.1109/icra.2016.7487437
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
M. Likhachev
中科院分区：
文献类型：
--
作者：
Fahad Islam;V. Narayanan;M. Likhachev
双向规划优于单向规划的优点在高维配置空间中的运动规划中得到了很好的证实。虽然双向方法已经在基于采样的规划器（如RRT-Connect）的背景下取得了巨大成功，但它们在基于搜索的方法（如A*）中并不流行。基于搜索的算法的系统性通常会导致一致和高质量的路径，也会对前向和后向搜索的连接施加严格的条件。已经开发了用于连接向前和向后搜索的可接受的算法，但是它们的计算复杂性是一个障碍。在这项工作中，我们利用最近在搜索方面取得的进展，开发了一种名为A*-Connect的算法，这与RRT-Connect的精神非常相似。A*-Connect使用文献中经典的前到前启发式的快速近似来引导向前和向后搜索，同时保留对完整性和有界次优性的理论保证。我们验证了A*-连接操作以及导航域，比较流行的基于采样的方法，以及最先进的双向搜索算法。我们的研究结果表明，A*-连接可以提供几倍的加速比单向搜索，同时保持高的解决方案的质量。
The benefits of bidirectional planning over the unidirectional version are well established for motion planning in high-dimensional configuration spaces. While bidirectional approaches have been employed with great success in the context of sampling-based planners such as in RRT-Connect, they have not enjoyed popularity amongst search-based methods such as A*. The systematic nature of search-based algorithms, which often leads to consistent and high-quality paths, also enforces strict conditions for the connection of forward and backward searches. Admissible heuristics for the connection of forward and backward searches have been developed, but their computational complexity is a deterrent. In this work, we leverage recent advances in search with inadmissible heuristics to develop an algorithm called A*-Connect, much in the spirit of RRT-Connect. A*-Connect uses a fast approximation of the classic front-to-front heuristic from literature to lead the forward and backward searches towards each other, while retaining theoretical guarantees on completeness and bounded suboptimality. We validate A*-Connect on manipulation as well as navigation domains, comparing with popular sampling-based methods as well as state-of-the-art bidirectional search algorithms. Our results indicate that A*-Connect can provide several times speedup over unidirectional search while maintaining high solution quality.