AAAI Publications, Tenth Symposium of Abstraction, Reformulation, and Approximation

Font Size: 
Korf's Conjecture and the Future of Abstraction-Based Heuristics
Robert C. Holte

Last modified: 2013-06-19


In his 1997 paper on solving Rubik's Cube optimally using IDA* and pattern database heuristics (PDBs), Rich Korf conjectured that there was an inverse relationship between the size of a PDB and the amount of time required for IDA* to solve a problem instance on average. In the current paper, I examine the implications of this relationship, in particular how it limits the ability of abstraction-based heuristic methods, such as PDBs, to scale to larger problems. My overall conclusion is that abstraction will play an important, but auxiliary role in heuristic search systems of the future, in contrast to the primary role it played in Korf's Rubik's Cube work and in much work since.

Full Text: PDF