Exactly how good are heuristics? Toward a realistic predictive theory of best-first search

We seek here to determine the exact quantitative dependence of performance of best-first search (i.e., A* algorithm) on the amount of error in the heuristic function's estimates of distance to the goal. Comparative performance measurements for three families of heuristics for the 8-puzzle suggest general conjectures that may also hold for more complex best-first search systems. As an example, the conjectures are applied to the coding pnase of the PSI program synthesis system. A new worst case cost analysis of uniform trees reveals an exceedingly simple general formula relating cost to relative error. The analytic model is realistic enough to permit reasonably accurate performance predictions for an 8-puzzle heuristic. The analytic results also sharpen the distinction between "Knowledge itself" and the "Knowledge engine itself". One has the sense that the men who conceived these high buildings [Gothic cathedrals] were intoxicated by their newfound command of the force in the stone. How else could they have proposed to build vaults of 125 feet and 150 feet at a time when they could not calculate any of the stresses?