Deadline-Aware Search Using On-Line Measures of Behavior
Deadline-Aware Search Using On-Line Measures of Behavior
复制标题
使用在线行为测量的截止日期感知搜索
DOI：
10.1609/socs.v2i1.18199
复制
发表时间：
2011
影响因子：
3
通讯作者：
Wheeler Ruml
中科院分区：
文献类型：
--
作者：
Austin J. Dionne;J. Thayer;Wheeler Ruml
在启发式搜索的许多应用中，没有足够的时间来找到可证明的最优解。我们考虑合同搜索问题：在给定的时间内找到可能的最佳解决方案。解决这一问题的传统方法是使用可中断的任意时间算法。这种算法返回一系列改进的解决方案，直到被中断，并且在搜索过程中不考虑接近的截止日期。我们提出了一种新的方法，即截止日期感知搜索，它明确地考虑了截止日期，并试图利用所有可用的时间来找到一个高质量的解决方案。该算法简单且完全通用：它通过在线剪枝修改了最佳优先搜索。网格世界导航、滑动瓷砖拼图和动态机器人导航的实验结果表明，我们的方法可以在各种各样的截止日期内超越领先的任意时间算法。
In many applications of heuristic search, insufficient time isavailable to find provably optimal solutions. We consider thecontract search problem: finding the best solution possible within agiven time limit. The conventional approach to this problem is to usean interruptible anytime algorithm. Such algorithms return a sequenceof improving solutions until interuppted and do not consider theapproaching deadline during the course of the search. We propose anew approach, Deadline Aware Search, that explicitly takes the deadlineinto account and attempts to use all available time to find a singlehigh-quality solution. This algorithm is simple and fully general: itmodifies best-first search with on-line pruning. Empirical results onvariants of gridworld navigation, the sliding tile puzzle, and dynamicrobot navigation show that our method can surpass the leading anytimealgorithms across a wide variety of deadlines.