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

(Korf, Reid, and Edelkamp 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. 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 (Zahavi et al. 2007) 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:* Apr 12, 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.