Predicting the Performance of IDA* using Conditional Distributions
  Korf, Reid, and Edelkamp introduced a formula to predict the number of nodes
IDA* will expand on a single iteration for a given consistent heuristic, and
experimentally demonstrated that it could make very accurate predictions. In
this paper we show that, in addition to requiring the heuristic to be
consistent, their formulas predictions are accurate only at levels of the
brute-force search tree where the heuristic values obey the unconditional
distribution that they defined and then used in their formula. We then propose
a new formula that works well without these requirements, i.e., it can make
accurate predictions of IDA*s performance for inconsistent heuristics and if
the heuristic values in any level do not obey the unconditional distribution.
In order to achieve this we introduce the conditional distribution of heuristic
values which is a generalization of their unconditional heuristic distribution.
We also provide extensions of our formula that handle individual start states
and the augmentation of IDA* with bidirectional pathmax (BPMX), a technique for
propagating heuristic values when inconsistent heuristics are used.
Experimental results demonstrate the accuracy of our new method and all its
variations.
