Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem
Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 2324-2328.
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.
@inproceedings{ijcai2007p374,
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 = {Proceedings of the Twentieth International Joint Conference on
Artificial Intelligence, {IJCAI-07}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ramon López de Mántaras},
pages = {2324--2328},
year = {2007},
url = {https://ijcai.org/proceedings/2007/374},
}
TY - CPAPER TI - Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem AU - Korf, Richard E. AU - Felner, Ariel T2 - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07 PB - International Joint Conferences on Artificial Intelligence PY - 2007 SP - 2324 EP - 2328 UR - https://ijcai.org/proceedings/2007/374 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
