Iterative Budgeted Exponential Search

Helmert, Malte and Lattimore, Tor and Lelis, Levi H. S. and Orseau, Laurent and Sturtevant, Nathan R.. (2019) Iterative Budgeted Exponential Search. In: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. pp. 1249-1257.

PDF - Published Version

Official URL: https://edoc.unibas.ch/75244/

Downloads: Statistics Overview


We tackle two long-standing problems related to re-expansions in heuristic search algorithms. For graph search, A* can require Ω(2^n) 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^2). For tree search, IDA* can also require Ω(n^2) 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*.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Helmert, Malte
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:International Joint Conferences on Artificial Intelligence
Note:Publication type according to Uni Basel Research Database: Conference paper
Related URLs:
Identification Number:
edoc DOI:
Last Modified:29 Jan 2020 16:12
Deposited On:29 Jan 2020 16:12

Repository Staff Only: item control page