ARA : formal analysis
ARA : formal analysis
复制标题
ARA：形式分析
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
S. Thrun
中科院分区：
文献类型：
--
作者：
Maxim Likhachev;G. Gordon;S. Thrun
在现实世界的问题中，思考的时间往往是有限的。 Anytime 算法在这些条件下是有益的，因为它们通常会非常快地找到第一个可能非常次优的解决方案，然后不断改进该解决方案，直到分配的时间到期。虽然随时算法很流行，但现有的随时搜索方法无法提供对其结果优劣的衡量标准。在本文中，我们提出了 ARA* 算法。 ARA* 是一种随时启发式搜索，它根据可用搜索时间调整其性能范围。它首先使用松散边界快速找到次优解决方案，然后在时间允许的情况下逐渐收紧边界。如果有足够的时间，它会找到一个可证明的最佳解决方案。除了理论分析之外，我们还通过模拟机器人运动臂和室外流动站动态路径规划问题的实验证明了 ARA* 的实用性。
In real world problems, time for deliberation is often limited. Anytime algorithms are beneficial in these conditions as they usually find a first, possibly highly suboptimal, solution very fast and then continually work on improving the solution until allocated time expires. While anytime algorithms are popular, existing anytime search methods are unable to provide a measure of goodness of their results. In this paper we propose the ARA* algorithm. ARA* is an anytime heuristic search which tunes its performance bound based on available search time. It starts by finding a suboptimal solution quickly using a loose bound, then tightens the bound progressively as time allows. Given enough time it finds a provably optimal solution. In addition to the theoretical analysis we demonstrate the practical utility of ARA* with experiments on a simulated robot kinematic arm and dynamic path planning problem for an outdoor rover.