Policy-Guided Heuristic Search with Guarantees
Policy-Guided Heuristic Search with Guarantees
复制标题
有保证的策略引导启发式搜索
DOI：
10.1609/aaai.v35i14.17469
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Levi H. S. Lelis
中科院分区：
文献类型：
--
作者：
Laurent Orseau;Levi H. S. Lelis
使用策略和启发式函数来指导搜索在对抗性问题中是非常有效的，正如AlphaGo及其继任者所证明的那样，它们基于PUCT搜索算法。虽然PUCT也可以用于解决单智能体确定性问题，但它缺乏对其搜索效果的保证，并且在实践中可能计算效率低下。将A*算法与学习的启发式函数相结合往往在这些领域中工作得更好，但A*及其变体不使用策略。此外，使用A*的目的是寻找成本最小的解，而我们寻求的是最小化搜索损失（例如，搜索步数）。LevinTS由策略指导，并提供与策略质量相关的搜索步骤数的保证，但它不使用启发式函数。在这项工作中，我们引入了策略导向启发式搜索（PHS），这是一种既使用启发式函数又使用策略的新型搜索算法，并且对启发式和策略质量相关的搜索损失具有理论保证。我们从滑块拼图、Sokoban和商业游戏“the Witness”中的一个拼图中实证地表明，PHS能够快速学习策略和启发式函数，并且在所有三个测试领域中，就解决的问题数量和搜索时间而言，PHS与a *、加权a *、贪婪最佳优先搜索、LevinTS和PUCT相比都具有优势。
The use of a policy and a heuristic function for guiding search can be quite effective in adversarial problems, as demonstrated by AlphaGo and its successors, which are based on the PUCT search algorithm. While PUCT can also be used to solve single-agent deterministic problems, it lacks guarantees on its search effort and it can be computationally inefficient in practice. Combining the A* algorithm with a learned heuristic function tends to work better in these domains, but A* and its variants do not use a policy. Moreover, the purpose of using A* is to find solutions of minimum cost, while we seek instead to minimize the search loss (e.g., the number of search steps). LevinTS is guided by a policy and provides guarantees on the number of search steps that relate to the quality of the policy, but it does not make use of a heuristic function. In this work we introduce Policy-guided Heuristic Search (PHS), a novel search algorithm that uses both a heuristic function and a policy and has theoretical guarantees on the search loss that relates to both the quality of the heuristic and of the policy. We show empirically on the sliding-tile puzzle, Sokoban, and a puzzle from the commercial game `The Witness' that PHS enables the rapid learning of both a policy and a heuristic function and compares favorably with A*, Weighted A*, Greedy Best-First Search, LevinTS, and PUCT in terms of number of problems solved and search time in all three domains tested.
DOI：
--
发表时间：
2018-09
期刊：
--
影响因子：
--
作者：
S. McAleer;Forest Agostinelli;A. Shmakov;P. Baldi
通讯作者：
S. McAleer;Forest Agostinelli;A. Shmakov;P. Baldi