Learning Inadmissible Heuristics During Search
Learning Inadmissible Heuristics During Search
复制标题
在搜索过程中学习不允许的启发式方法
DOI：
10.1609/icaps.v21i1.13474
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Wheeler Ruml
中科院分区：
文献类型：
--
作者：
J. Thayer;Austin J. Dionne;Wheeler Ruml
次优搜索算法通过牺牲保证解决方案最佳性来提供较短的解决时间。虽然*和IDA*（例如*和IDA*）的最佳搜索词需要可允许的启发式方法，但Suboptimalsearch算法不需要以这种方式限制其指导。以前的工作已经使用离线培训来将可接受的启发式方法转变为更有效的不可接受的启发式方法。在本文中，我们证明可以在搜索期间在线执行此转换。除了不需要培训实例和广泛的预计入外，在线方法还可以针对特定的问题实例量身定制学习的启发式方法。我们使用贪婪的最佳优点搜索和有限的次优搜索在四个不同的基准域中评估我们的技术。我们发现，在线学习的启发式方法既可以更快地进行搜索，又可以依靠任何最佳搜索中可用的信息。
Suboptimal search algorithms offer shorter solving times by sacrificing guaranteed solution optimality. While optimal searchalgorithms like A* and IDA* require admissible heuristics, suboptimalsearch algorithms need not constrain their guidance in this way. Previous work has explored using off-line training to transform admissible heuristics into more effective inadmissible ones. In this paper we demonstrate that this transformation can be performed on-line, during search. In addition to not requiring training instances and extensive pre-computation, an on-line approach allows the learned heuristic to be tailored to a specific problem instance. We evaluate our techniques in four different benchmark domains using both greedy best-first search and bounded suboptimal search. We find that heuristics learned on-line result in both faster search andbetter solutions while relying only on information readily available in any best-first search.