Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem
Abstract
We integrate a number of new and recent advances in heuristic search, and apply them to the four-peg Towers of Hanoi problem. These include frontier search, disk-based search, parallel processing, multiple, compressed, disjoint, and additive pattern database heuristics, and breadth-first heuristic search. New ideas include pattern database heuristics based on multiple goal states, a method to reduce coordination among multiple parallel threads, and a method for reducing the number of heuristic calculations. We perform the first complete breadth-first searches of the 21 and 22-disc four-peg Towers of Hanoi problems, and extend the verification of "presumed optimal solutions" to this problem from 24 to 30 discs. Verification of the 31-disc problem is in progress.
Cite
Text
Korf and Felner. "Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem." International Joint Conference on Artificial Intelligence, 2007.Markdown
[Korf and Felner. "Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem." International Joint Conference on Artificial Intelligence, 2007.](https://mlanthology.org/ijcai/2007/korf2007ijcai-recent/)BibTeX
@inproceedings{korf2007ijcai-recent,
title = {{Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem}},
author = {Korf, Richard E. and Felner, Ariel},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2007},
pages = {2324-2329},
url = {https://mlanthology.org/ijcai/2007/korf2007ijcai-recent/}
}