Exactly How Good Are Heuristics?: Toward a Realistic Predictive Theory of Best-First Search

Abstract

We seek here to determine the exact quantit.ative dependence of performance of best-first search (i.e.,, ~* algorithm) on the amount of error in the heur1~t1c function's estimates of d.istance to the goal. Comparaltve performance measurements for three families of heuris tics for the 8-puzzle suggest general conjectures that may also · hold for more complex best-f irs t search sys tems. As an ex<~m ple, the conjectures are applied to the coding pnase of the PSI program synthesis system. A new worst c.ase co st analysis of uniform trees re ve als an exceedingl y s imple general formula relating cost to relati ve .error . The analytic model is realistic enough to permit r eason.ab.ly accurate performance predictions for an 8-puzzle heunst1c. The analytic results also sharpen the distinctio.n between "knowledge itself" and the "knowledge engine itself". One has the sen se that the men who conceived the se high buildings [Gothic cathedrals] were intoxicated by their new-found command of the force in the stone. How else could they have proposed to build v aults of 125 feet and 150 feet at a time when they could not calculate any of the stresses? J. Bronowski, The Ascent of Man