Iterative Budgeted Exponential Search
Full Text: 0174.pdf
We tackle two long-standing problems related to re-expansions in heuristic search algorithms. For graph search, A* can require Ω(2ⁿ) expansions, where n is the number of states within the final f bound. Existing algorithms that address this problem like B and B’ improve this bound to Ω(n²). For tree search, IDA* can also require Ω(n²) expansions. We describe a new algorithmic framework that iteratively controls an expansion budget and solution cost limit, giving rise to new graph and tree search algorithms for which the number of expansions is O(n log C*), where C* is the optimal solution cost. Our experiments show that the new algorithms are robust in scenarios where existing algorithms fail. In the case of tree search, our new algorithms have no overhead over IDA* in scenarios to which IDA* is well suited and can therefore be recommended as a general replacement for IDA*.
Citation
M. Helmert, T. Lattimore, L. Lelis, L. Orseau, N. Sturtevant. "Iterative Budgeted Exponential Search". International Joint Conference on Artificial Intelligence (IJCAI), (ed: Sarit Kraus), pp 1249-1257, August 2019.| Keywords: | Heuristic Search and Game Playing: Heuristic Search, Heuristic Search and Game Playing: Combinatorial Search and Optimisation |
| Category: | In Conference |
| Web Links: | IJCAI |
| doi |
BibTeX
@incollection{Helmert+al:IJCAI19,
author = {Malte Helmert and Tor Lattimore and Levi H. S. Lelis and Laurent
Orseau and Nathan R. Sturtevant},
title = {Iterative Budgeted Exponential Search},
Editor = {Sarit Kraus},
Pages = {1249-1257},
booktitle = {International Joint Conference on Artificial Intelligence
(IJCAI)},
year = 2019,
}Last Updated: July 03, 2020Submitted by Sabina P
