*Uzi Zahavi, Ariel Felner, Neil Burch, Robert C. Holte*

Korf, Ried and Edelkamp (AIJ 2001) introduced a formula to predict the number of nodes IDA* will expand given the static distribution of heuristic values. Their formula proved to be very accurate but it is only accurate under the following limitations: (1) the heuristic must be consistent; (2) the prediction is for a large random sample of start states (or for large thresholds). In this paper we generalize the static distribution to a conditional distribution of heuristic values. We then propose a new formula for predicting the performance of IDA* that works well for inconsistent heuristics and for any set of start states, not just a random sample. We also show how the formula can be enhanced to work well for single start states. Experimental results demonstrate the accuracy of our method in all these situations.

*Subjects:* 15.7 Search; 15.7 Search

*Submitted:* May 4, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.