The Joy of Forgetting: Faster Anytime Search via Restarting
The Joy of Forgetting: Faster Anytime Search via Restarting
复制标题
遗忘的乐趣：通过重新启动更快地随时搜索
DOI：
10.1609/icaps.v20i1.13412
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Wheeler Ruml
中科院分区：
文献类型：
--
作者：
Silvia Richter;J. Thayer;Wheeler Ruml
随时搜索算法通过快速找到第一个（通常是次优的）解决方案来解决优化问题，然后在给定额外时间时找到改进的解决方案。为了快速交付初始解决方案，他们通常对启发式成本估计h很贪婪。在本文中，我们表明，这种低h的偏见可能会导致性能不佳，如果贪婪的搜索早期错误。在此基础上，我们提出了一种新的随时从初始状态重新开始搜索的方法，每次一个新的解决方案是found.We证明了我们的方法的效用，通过实验在PDDL规划以及其他领域，并表明，它是特别有用的启发式有系统误差的问题。
Anytime search algorithms solve optimisation problems by quickly finding a (usually suboptimal) first solution and then finding improved solutions when given additional time. To deliver an initial solution quickly, they are typically greedy with respect to the heuristic cost-to-go estimate h. In this paper, we show that this low-h bias can cause poor performance if the greedy search makes early mistakes. Building on this observation, we present a new anytime approach that restarts the search from the initial state every time a new solution is found. We demonstrate the utility of our method via experiments in PDDL planning as well as other domains, and show that it is particularly useful for problems where the heuristic has systematic errors.