Improved Prediction of IDA*'s Performance via -Truncation
Levi H. S. Lelis, Sandra Zilles, Robert C. Holte · 2011
Korf, Reid, and Edelkamp launched a line of research aimed at predicting how many nodes IDA* will expand with a given cost bound. This paper advances this line of research in three ways. First, we identify a source of prediction error that has hitherto been overlooked. We call it the “discretization effect”. Second, we disprove the intuitively appealing idea that a “more informed” prediction system cannot make worse predictions than a “less informed” one. More informed systems are more susceptible to the discretization effect, and in several of our experiments the more informed system makes poorer predictions. Our third contribution is a method, called “� truncation”, which makes a prediction system less informed, in a carefully chosen way, so as to improve its predictions by reducing the discretization effect. In our experiments � truncation rarely degraded predictions; in the vast majority of cases it improved predictions, often substantially.