Improved Prediction of IDA*’s Performance via Epsilon-Truncation

Proceedings of the International Symposium on Combinatorial Search, 4

Volume

Vol. 4 No. 1 (2011): Fourth Annual Symposium on Combinatorial Search

Full Papers

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 ``$epsilon$-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 $epsilon$-truncation rarely degraded predictions; in the vast majority of cases it improved predictions, often substantially.

10.1609/socs.v2i1.18198