Direction-Optimizing Breadth-First Search with External Memory Storage
Full Text: 0175.pdf
While computing resources have continued to grow, methods for building and using large heuristics have not seen significant advances in recent years. We have observed that direction-optimizing breadth-first search, developed for and used broadly in the Graph 500 competition, can also be applied for building heuristics. But, the algorithm cannot run efficiently using external memory -- when the heuristics being built are larger than RAM. This paper shows how to modify direction-optimizing breadth-first search to build external-memory heuristics. We show that the new approach is not effective in state spaces with low asymptotic branching factors, but in other domains we are able to achieve up to a 3x reducing in runtime when building an external-memory heuristic. The approach is then used to build a 2.6TiB Rubik's Cube heuristic with 5.8 trillion entries, the largest pattern database heuristic ever built.
Citation
S. Hu, N. Sturtevant. "Direction-Optimizing Breadth-First Search with External Memory Storage". International Joint Conference on Artificial Intelligence (IJCAI), (ed: Sarit Kraus), pp 1258-1264, August 2019.| Keywords: | Heuristic Search and Game Playing: Heuristic Search, Combinatorial Search and Optimisation |
| Category: | In Conference |
| Web Links: | IJCAI |
| doi |
BibTeX
@incollection{Hu+Sturtevant:IJCAI19,
author = {Shuli Hu and Nathan R. Sturtevant},
title = {Direction-Optimizing Breadth-First Search with External Memory
Storage},
Editor = {Sarit Kraus},
Pages = {1258-1264},
booktitle = {International Joint Conference on Artificial Intelligence
(IJCAI)},
year = 2019,
}Last Updated: July 03, 2020Submitted by Sabina P
