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

Introduction

Building speech understanding sys tems or other expert problem solving systems can be likened to medieval ca thedral building: it can be done but it is by no means easy to do so. This paper attempts to show how some performance measurement experiments with the 8-puzzle and some mathematics of tree search can hope to ease the burden a little, as civ il engineering has done for cathedral builders.

Some of the difficulties in building such sys tems arise from an inability to predict performance a priori, to "calculate the stresses", so to speal~. Suppose it's design decision time for such a system: Which will give better performance, heuristic A or heuristic . B? Debate . is sometimes avoided by using both in a multHerm evaluation function, if this system uses an evaluation function of some sort to guide behavior. But performance depends on how much weight each term is given. The choice of the scalar It is a certainty that in the future we will understand more of AI more mathematically than today. But if we somehow succeed in developing an exact mathem.ltical model of the HEAR.SAY-Il system [Hayes-Roth & Lesser 77], say, complete with formulas to predict perform;.nce qu<~n tit atively under the most diverse parameter settings, will such a theory say anything at all about the HWIM speech understanding system [Woods 7~], or about the F·SJ program synthesis system [Barstow 77, Barstow & Kant 77], or about a chemistry synthesis program [Powers 75]? This will be possible only if the theory captures a common denominator of these systems. The four systems mentioned use best-first schedulers to decide what to do next.

1 This research was supported by the Defense Advanced Research Projects Agency under Contract no. F4462073-C-0074 and monitored by the Air Force Office of Scientific Research,

The A* algorithm [Hart et.al. 68, Nilsson 71] embodies the idea of a best-first search. In basic terms, you have a finite set of discrete opt ions of what to do next, and each time you ·choose an action and do it, you· get a new set of options : the still unchosen ones plus new ones generated by performing the chosen action. If 1here is no obv ious way to totally order these actions in advance (and remember that some don't exist until you perform others), then one approach is to assign a number to each action as it appears, according to · how good you think it is lo do that one, independently of any you may have done already. Then iteratively choose the action that has the smallest value (smallest is best). The M algorithm [Hart et.al. 68, Nilsson 71] operates on this .principle, using an <~rbitrary ordering function F(s) to solve· problems like the 8-puzzle. The Graph Traverser and the HPA algorithm are essentially the same as A* [Doran & Michie 66, Pohl 69].

The 8-puzzle [Schofield 67] is a one-person game the objecti ve of which is to rearrange a given configuration of 8 tiles on a 3x3 board into another given configuration by iteratively sliding a tile into the orthogonally adjacent empty location, like so:

This problem can be modeled exactly as a collection of points (configurations) and lines connecting them (moves), i.e., as a graph. Since some problems differ only in that they are defined by different graphs, we define a J;!roblem to be a finite, strongjy connected ~ with no · se lf - loops and no . multiple edges. (Throughout, underlini~­ indicates a formal definition.) Actually, the 8-puzzle graph is not strongly connected, but rather consists of two disconnected components ("can't get there from here';); for our purposes w.e consider. one such component. The 8puzzle is an undirected gr.aph since every move has an inverse.

The 8-puzzle is to this work as the fruit fly is to the geneti cis t : simple, convenient to manipulate, yet exhibiting interesting phenomena that hypothetically hold for a broader class of subjects. To approach a predictive theory of heuristic search experimentally, we define search performance functions (e.g., number of nodes expanded and length of solution path found), measure their values experimentally over a range of realistic parameter values (e.g., as a function of N, the distance to the goal, and of W, a weighting coefficient in the evaluation function), look for patterns in the data (e.g., cost grows (sub-)exponentially with N under certain conditions), and conjecture certain general relations to hold (e.g., increasing W changes an exponential cost heuristic into sub-exponential).

Cost, Quality and Error for 8-puzzle Heuristics

Heuristic search is supposed to be better than breadth-first search, but . how much better? Do heuristics beat the "exponential explosion" that besets breadth-first search? Figure 1 S!hOws the number of nodes expanded as a function of the depth of the goal for three particular heurist ics for the 8-puzzle. The qualitative· di·fference between K3 and the other two is of particular interest : could this have been predicted a priori? This work differs from previ ous experiments [Doran & Michie 66, Michie 67, Doran 68, Michie & Ross 70) in: a) volume of data collected, g ivi ng statistical significance over a large -range of parameter values; b) measures ·of the error in the heuri stics themselves; c) different measures of internal behav ior. A few definitions are required to .make Figure 1

meaningful. (Note: what we call K, [Hart et.al. 68) call~.) Each possible choice of initial node §.r and ~ node §.g of a problem graph defines a distinct PIQ..I;l]gm !n~~rrce {ip..§.g~ hence a graph G having V nodes induces a set U(G) of V problem instances. The minimum distance in the &rAI2h between ~ two ~ ~i and §.j is -alwa~s d;lined s1nce the graph 1s strongly connected, and is denoted !ili.i .2.j ~- .

This section assumes that the A* evaluation fundion t akes the form F(s) = g(s) + K(s), where g(s) is 1he distance of node s from the root node of the search tree. Note that K is a funct·ion of two nodes of G (i.e., current' and goal), but for simplicity we write K(s) instead of K(s, s ) when goal node sg is implicit. A K function estirr·a1es the distance in the graph from s to the goal node; informally, K contains the knowledge or information about the graph G available to guide the search.

For a given G, K, and (sr· sg), the cost of search and the goodness of the solution found can be defined, respectively by: X(G, K, Sr.2.gb the number Qf. nodes ·

~anded before search terminates, excluding the &Q£1 node; and P(G, K, sr.2.gb the length Qf. the solut ion path found. L(G, K, sr~g) =· P(G, K, sr9L.L...bi§.r~) expresses solution quality as a fraction Qf. tile minimal length Qf. 1! ?.Qlilll.on path for an instance. So L ~ 1, with equality iff a minimal length solution is found. (We will conveniently drop arguments from formulas when the argument is known implici tly.)

We will consider three K functions for the 8-puzzle t aken from the literature [Doran & Michie 66, Nilsson 71].

K 1 (s) = the number of t iles that occupy a board location in s different from the location occupied by that tile in the goal node

Sg. K2(s) = the sum, over all 8 t iles in s, of the minimum number of moves required to move the tile from its location in s to its desired location in sg, assuming that no other tiles were blocking the. way.

K3(s) = K 2 (s) + 3 · seq(s),

where seq(s) counts 0 if the non-central squares in s match those in s up to rotation about the. board per ime!fer, and counts 2 for each tile not forlowed by the same tile as in the ·goal node.

For comparison purposes we also measure the performance of K 0 (s) = 0, which gi ves breadth-first search.

Wha-t can be predicted about the . performances of these three K functions for arbit r ary problem instances? Little, beyond that L = 1 for K 1 and K 2 (by the A* admissibility theorem fHart el.al. 68], since Kl(si, sj) !> h(si, sj) for all (si, s/·) and similarly for K2). Regardmg the X measure, formal heory [Hart el.al. 68, Pohl 69, Pohl 70, Nilsson 71, Harris 74, Vanderbrug 76] tells us nothing about these particular heuristi cs for this particular problem, not even that X(K 2 ) is always less . than X(K 1 ). Intuitively, K3 may seem to be better than K2 [Nilsson 71, p . 661, but is this true always, sometimes, or never? Two example problem instances suffice to suggest that Lt is risky to guess on the basis of limited data (ex<~mple on left from [Doran & Michie 66)): ·

(sr, sg) = .

(216.408.753, 123.804.765) c (485.163.702, 368.405.172)

Figure 1 shows the result of measuring X (by executing the search) for a set of 875 randomly chosen problem instances of the 8-puzzle (of 108 possible instances). The instances are grouped on the abscissa according to the actual minimum distance h(sr, sg) between initial node and goal node. For example, for N = 10 there are random 40 problem instances such that h(sro sg) = 10, and hence 40 measurements of values of . X<K 2 , sr, sg). The mean of these 40 experimentally measured values is plotted as XMEAN(K 2 , 10). ln general, the true value of XMEAN(G, K. N) is defined to "be the 1]~.1!!:! !1!,!.1!\lJ~ 9f IJ.Osi~ ~anded using heuristic !$_ over · 1!!1 ~9l !n U(G) such that !ili.rJgl = N. The vertical bar measures twice the standard deviation of the sample XMEAN --- a statistical measure of how accurately the experimentally meas·ured value of XMEAN approximates the true value of XMEAN.

The lower dashed line in figure. 1 shows perfect search: XMEAN(N) = N, if only. solution path nodes are expanded. The same set of random problem instances is used for K1, K 2 , and K 3 , in this and .all subsequent experiments. Details . and additional experimental results are given in [Gaschnig 77b).

In the above experiments, K 3 always found minimal length solution paths (i.e., L = 1) for N $ 9, with LMEAN(K 3 , N) s 1.3 for targer .N. (LMEAN is· defined in terms of L as XMEAN is defined in terms of X.) For human subjects, 1.1 s LMEAN s 3.3 has been r.eported [Hayes et.al. 65, Doran & Michie 66].

The differences in performance among the heuristic functions result from the differences in the values they compute, but what is the dependency? What in fact are the values? Figures 2, 3, and 4 plot the range in a heuristic's estimates of distance to the goal vs. the actual distance to the goal. . KMIN(G, K, i) is defined to be the !l1J.D.Lmum value of llij12gl over 2]! node pairs {?_j~l L!J. hl<m such that bi~:.2 ) = i. For example, KM!N(K 2 , 10) = 4 s K 2 (s) $ KMAXJfK 2 , 10) = 10 for all s whose distance to the goal is 10. Each figure represents 11,448 distinct observations of K(sj, sg) vs. h(sl·, sg), recorded dunng the same expenments as for f1gure : the sg nodes are the goal nodes in the sample set and the sj are the nodes along the solution path.

Behavior Measures

It is not obvious exactly how XMEAN and LMEAN depend on KMIN and KMAX, but the clear superiority of K 3 is compelling: what is A* doing differently in this case? The following experiments (Figures 5-7) show interesting relations between external performance and two measures of behavior during search: LEV(G, K, Sr.2g.l1 the number Q.i nodes occurring ~ level l L!J. the final search Ire~ and RUN(G, K, Sra2gl.. the mean "run length" Q.i the search, i.e., the number of nodes expanded, di vided by one plus the number of "hops" that occur when the next node expanded is not a son of the last node expanded. RUN = N for optimal search (no mistakes), and equals about 1 for breadth- first search.

Figure 5 shows LEVMEAN(Kj, N, i) for j = 1, 2, 3, and a representative case N = 20. Note that the maximum value of LEVMEAN(i) occurs at about i = Nl2 = 10 for each Kj, and that LEVMEAN(i) is approximately symmetric about thi s value of i. (A portion of the K 3 curve· is cut off the bottom of this semi-log plot.) Observe for K 1 and K2 that LEVMEAN(i) increases (and then decreases) approximately exponentially with i. In contrast, LEVMEAN(i) for K3 is distributed more uniformly with i, suggesting that uniform distribution of LEVMEAN(i) is correlated . with sub­ exponential XMEAN.

We refer to exponentially distributed LEVMEAN(i) as "mid-depth bulge", quantified as follows. For K1, the sum of LEVMEAN(i) for i - 11, 12, and 13 is half the sum of LEVMEAN(i) for all i. (Note. that the latter value equals the ~alue of XMEAN.) We say then that the 501. LEVMEAN­ interval for K 1 is [11,13j. Similarly, the 901. LEVMEAN­ interval for K 1 is [8,15]. Since [1,20) is the entire interval (i .e., N = 20), we define the 501. LEVMEAN-inl"erval fraction to be (13- 11 + 1) I (20- 1 + 1) = .15. Similarly, the 901.

LEVMEAN-interval fraction is (15- 8 + 1) I 20 = ,ll. In general let IF(p·) denote the value of thC: p LEVMEAN­ interval fraction. If LEVMEAN(i) were uniformly distributed with i then IF(p) = p. Figure 6 plots IF(p) vs. p for p = .25, .5, .75, and .9, for K 1 , K 2 , and K 3 . Mid-depth bulge may be measured by IF(p) - p, by which K 1 and K2 are easily distinguished from K 3 . A possible scalar measure of mid­ depth bulge <MPS) is the ['(l~_<m \f.a. LLI~ pj_ !~(p) :: p_. For the four values plotted for e·ach K function in Figure 6 we have MDB(K 1> = (.25 - .05 + .5 - .15 + .75- .25 + .9 - .4) I 4.39 and M08(K 2 ) = .29 and MDB(K 3 ) = .06 Pendi11g further experiment and mathematical. analysis, we tentatively conjecture that XMEAN(G, K, N). is subexponential in N iff MDB(K) < .15. .

Figure 7 shows RUNMEAN(Ki, N) for i = 1, 2, 3. RUNMEAN(N) = N for small N because these K functions are optimal or nearly so for small N. Whereas by the MOB measure K 3 differs qualitatively from K 1 . and K 2 , by RUNMEAN the difference is only one of degree, suggesting no credible means of distinguishing subexponential from exponential cost heuristics. Is the similarity in form of the three curves coincidental? And why this particular three pha!;e "decay" form? The fact that RUNMEAN for K 1 is little more than 1 for large N, together with the mid-depth bulge data above, suggests that ordered depth-first search, using the same K function, may actually be better than best-first search for large N for "poor" heuristics.

Effects of Changing Term Weight

How does performance change if instead of F(s) = g(s) + K(s) we use F(s) = K(s) or F(s) = ( 1 - W) · g(s) + W · K(s), where 0 S W $ 1? Certain formal analyses [Pohl 69, Pohl 70, Nilsson 71, Vanderbrug 76) suggest the value of the g(s) term for "insurance", .but the results do not strictly apply to these 8-puzzle heuristics (see "Analysis" section).·

Figures 8 through 11 show how performance varies with w, . for W = .Q.O, 0.1, ... , 1.0. Note .that by definition W = .5 gives the same behavior as F(s) = g(s) + K(s), and that W = 0 gives breadth first search. Note in Figure 8. that for K 2 , as W in.creases the functional form of XMEAN becomes subexponential in N, and that for· medium-sized v alues of N, XMEAN(K 2 , N, W) increases as W increases. The same holds for K 1 and K 3 (not shown), except that K 3 has "reached its limit" at ·w = .5 (no further improvement). Figure 9 .is comparable to Figure 1, but uses W = 1.0 instead of W = .5. Note in Figures 1 and 9 that for every N, K3 is better than K 2 is better than K 1 (with statistically insignificant exception); the same is true for each value of W measured. Hence determining which heuristic is best for small N (cheap experiment) tells which is best for large N too. This may not be true generally. · Figure 10 compares the three heuristics by length of the solution path (LMEAN) for W = 1.0. Note that K 3 is now better than Kz and K1, whereas for W - .5 the opposite is true. For lar.ge N, XMEAN and LMEAN are inversely related for fixed K as W varies, but are positively related for fixed large W a~ K varies. This says that if N is large, speed can be traded for quality by changing W but not by changing K. Figure 11 shows this cost/quality tradeoff. explicitly as W varies from 0.0 to 1.0, for a "mid-sized" case N · 15: increasing W

beyond a certain value brings poorer · quality . at · greater

cost.

Implications for the PSI System

Will comparable experiments ·with more complex bes t - first search systems yield result s similar to those reported here? To · be concrete, we ·consider one such system, the program construction phase of ·the PSI program synthesis syste·m, which is being implemented as a bes t - f irst search [Barstow 77, Green 77]. We interpret the current experimental results as i.f they. applied to some extent to PSI.

The coding subsystem of PSI converts a high level program specification into a legal LISP implementation by <lppl y ing rules to refine a specification into a slightly more del ail ed specification. The rule set induces a tree ·in which the terminal nodes correspond to legal programs for the given input . These target programs can differ drastically in effi ciency, so that a goodness value may be assigned to each terminal node, comparable to the L measure here~ Sear ch of the entire tree to find the most efficient implementation (program with smallest L) may incur prohi bitive expense (i.e., X = number of nodes expanded in re f inement tree). Hence an "efficiency expert" (comparable to a K function) guides the search in an attempt to keep both L and X acceptably small [Barstow & Kant 76]. The var iable N, the number of refinement steps, might refer to the length of the shortest terminating path, or to the leng th of the path to ·the most efficient program.

The 8 - puzzle experimental results support the following conjectures .about the performance of this phase of PSI, assuming best-first search with an evaluation f unction comparable to F(s) = (1 - W) · g(s) + W · K(s) ..

1. For W = .5, unless the e(ficiency expert (EE) is very good, it will not be feasible to synthesize programs that require very many refinement steps (i.e. large N), because the number oL oodes· expaAEled (i.e., XMEAN(N)) will grow exponentially with N. (See Figure 1)
2. By simply choosing W = 1.0 instead of W = .5, XMEAN(N) becomes sub-exponential: it will cost somewhat more to synthesize medium-sized prograr;ns, but far less to synthesize large programs (Figures 8, 9). However, the synthesized programs may be less efficient than if W = .5 is used (Figures 10, 11 ).
3. If EE is improved so as to reduce XMEAN, then the improvement will be observed for every value of W (Figure.s 1, 9; ·compare K 1 to K2, or K2 to K3). Furthermore, for large W, the· improvement in speed will al so cau!;e an improvement in the efficiency of the synthesized programs: faster heuristics find better solutions (Figure 10).
4. The XMEAN performance of a version of EE for large N can be ·predicted · by measuring mid-depth bulge for medium-sized N (Figures 5, 6).
5. The program will hop around the search tree quite a lot unless N is small (Figure 7). Mean run length <· 2

indicates poor EE. In this case; ordered depth-first search may be better than best-first search.

Worst Case Cost Analysis

The objectives of analysis of A* are both practical and theoretical. A practical objective is to find a formula for XMEAN(G, K, W, N), say, valid for .an arbitrary problem graph G, heuristic function K, and over the range of W and N. Then to determine for a particular G 0 whether heuristic A performs better than heuristic B, simply evaluate· the formula with G = G 0 once with K = KA and once with K = KB; to find a good value of W, evaluate for different values of W. This most general objective may not be feasible, but Figure 12 illustrates an appli.cation of the general results descri bed in this section: a reasonably accurate prediction of the worst case performance of K2 for the 8-puzzle.

A principal theoretical objective of A* analysis is to det ermine the exact dependence of performance on error in the heuristic estimates. For a broad range of heuristic functions it turns out that worst case cost (number of nodes expanded) is a simple exponential function of a function 6(i) that measures the relative error in the heur istic estimates, as a function of distance from the goal, thus:

XWORST(M, KMIN, KMAX, N) "rei"

where "rei" denotes "s" if 6(i) is .weakly monotonic decreasing for i > 0, and "2:" if . 6(i) is weakly monotonic increasing for i > 0. The remainder of this section descr ibes the above results in somewhat more detail. Full detail and proofs and other results are given in [Gaschnig 77a].

Until we discover how to plug an arbitrary problem gr aph and heuristic function into a m<~thematical formula (as English text? as ALGOL source code?), we must resort to making simple models that capture only a part of what we want, but which hopefully have some limited predictive power. To simplify, here we model an arbitrary graph by a single positive integer M, the branching factor of a uniform tree. A single node at level N of the tree is di stinguished as the goal node. A K function on the uniform tree becomes simply the KMIN( i) and KMAX(i) functions that bound the estimates of that K ·function. So the heurist ic is now represented by a pair of real -valued functions on the non- negative integers (e.g., Figures 2, 3, and 4). We have thus blurred the distinction between all K functions that happen to have a particular KMIN and KMAX as bounding functions. We can't predict their performances indi v idually any longer, but can only give the best case or ave rage case or worst c1se performance. The latter can be defined as

XWORST(M, KMIN, KMAX, W, N),

which is a particular function of the form

~+ X ( Jlj 4 /R) X ( I'J 4 . ~) X [0,1) X ~ 4 ~1 where f\1 denotes the non-negative integers and ~ the non- negative reals. XWORST gives the number of .nodes expanded by A* in searching the uniform tree, using the following K function, for a given KMIN and KMAX:

KWORST(s) =rKMAX(h(s)) it node s is on the solution path l KMIN(h(s)) if s is not on the solution path

Note that KWORST returns relatively high values when i t should give low values, and vice. versa.

The above is an informal description of a standard formal worst case cost model [Pohl 69, Pohl 70, Nilsson 71). Heretofore, however, XWORST results have concentrated on KMIN and KMAX functions that take the form KMIN(i) = i - a and KMAX(i) = i + b, where a and b are. real -valued constar.1ts, i.e., straight lines with slope 1. So· really the KMIN and KMAX functions in such analyses can be represented by real numbers a and b. This simplifies the analysi s, but excludes heuristics whose KMIN and KMAX are more arbitrary, e.g., those in Figures 2, 3, and 4.

To get the general case, we note first that the objective is to determine the dependence of performance on er ror . The KMIN and KMAX functions, however, do not measure error. They bound the numerical estimates computed by a K function. To denote the re.lative error, or spread, in these estimates, we can rewrite

and solve for 8(i) and ;3(i) in terms of KMIN(i) and KMAX(i):

By this definition, (l(i) is the arithmetic mean of KMIN(i) and KMAX(i), and 8(i) is the relative error of KMIN(i) or KlviAX(i) with respe.ct to ;3(i), for example Figure 13. By definition,

0 s 8(i) s 1 for any KMIN and KMAX.

Formula (1) holds for all "well-behaved, never overestimating" K functions. The formal conditions are that W = .5; that KMAX(i) = i, as is true of K 2 for i s 21 (Figure 3). Al so, that 0 s KMIN(i) s KMAX(i) and that for all i, KMJN(i + 1) ~ KMIN(i)- 1, as is true for K 1, K2, and K3 for all i plotted in Figures 2, 3, and 4. Note that 8(i) = constant is weakly monotonic both increasing and decreasing, hence formula (1) is exact (i.e., equal ity holds). In thi s case, KMIN(i) is a straight line through the origin.

Formula (1) tells how much error in a K function can be tolerated and still achieve a given level of performance, For example, for each of the KMJN functions shown in Figure 14, the corresponding 6(i) is plugged into formula (1) and simplified, to obtain the following results:

8(KMIN, KMAX, i) XWORST(M, KMIN, KMAX, N)

This table expresses a guarantee: if a K function meets the specified condition, then its performance is no worse than that indicated above.

Figure 15 illustrates schematically the distinction between the "knowledge itself" (i.e., a lattice of heuristic functions) and the "knowledge engine itself" (i.e., XWORST

is a function on the lattice); Each point in the lattice

represents the 6 function corresponding to particular KMIN and KMAX functions. The set of all these 8 funchons Is partiall y ordered under the relation 6 1 !>L 62 iff 61 (i) !> 62(i) for all i = 1, 2, ... Associated with each 8 function is its cor responding XWORST value (depicted by a double arrow), which is itself a function of lvl and N. Formula (1) determines (or at least bounds) the " lengths" of the double arrows.

For the conditions of (1 ), KMAX is fixed and hence specif y ing · KMIN determines both 8 and ;3 . . In the unrestricted case, the XWORST mapping is like a function z = f( x, y) that describe$ a surface in 3-space above · the x-y plane. Each of the axes, however, is not a linear orde ring of integers or reals, but rather an infinite coni inuous lattice of functions on the non-negative integers.

Formula (1) only bounds XWORST, but another more compl icated expression gives XWORST exactly for all KMIN and KMAX without restriction. It is used to generate the XWORST predictions, shown in Figure 12, of the performance of K 2 for the 8-puzzle, given the KMIN and KMAX values shown in Figure 3. ln figure 12 XMAX is defined like XMEAN, but lakes the maximum instead of the mean of the experimental values. Fo1' the .8-puzzle M was estimated to be 1.715 experimentally. Note that this predict ion is a demonstration of technical feasibil ity, not of "commercial marketability".

The extent of agreement between predicted and measur ed values i'n Figure 12 is not particularly good in absolute terms, but is i.n some sense astounding, since the graph of the 8-puzzle is not a uniform tree, and the K2 function for the 8.- puzzle. does not have worst case behav ior like that of KWORST.

Conclusions and Future work

The experimental results show that some heuristics beat the exponent ial explosion and others do not. But the latter can be made to do so simply by giving more weight (W) to the distance-to-goal term (K(s)) in the evaluation function and less weigh\ to the distance-from- root term (g (s )). However, this reduction In the number of nodes expanded (XMEAN(N)) occurs only .if distance· to the goal (N) is large. For medium-sized N, XMEAN actual·ly increases with W. Why? There is a limit to what adjusting· W can do: subexponential heuristics, e.g., K 3 , do not get any better by increasing W. Also, if Ki has smaller XMEAN(N) than Kj for one value of W, then the same ordering holds for any other value of W. Increasing W also increases the lengths of the solution paths found: for large W, faster heuristics find better solutions,· whereas for smaller W the opposite can be true. How much of this is true for PSI or other complex best - first search systems? Clearly much remains to be investigated. If predicability can be exploited in practice, then perhaps our current heuristic search techniques are only "model T"s.

The new analytic results permit predictive statements for heuristic functions that occur in practice, but much remains for future work. When, if ever, is relati ve worst case performance a good predictor of relative average case performance? Are there effective ways to experimentally or analytically estimate. the KMIN and KMAX of a given heuristic?

Theoretically, the fact that performance is a function of rele~tive error rather than of absolute error would seem to merit careful thought. What makes relati ve error more special ? The "limits to growth" tabulated in the preceeding sect ion are sobering: A* must be given a very accurate heur isti c in order to guarantee good performance in the worst case. What about e~verage case?

The symbolic res.ult-- a mapping from a lattice of heuri sti c "error" functions to a lattice of performance functions-- can serve as a definition for the (worst case) per formance capability of the A* algorithm. The lattice representing heuristic functions exists independently of A*; i t he~ppens to be the domain of a particular function we have called XWORST. In words, the "knowledge itself" is di stinct frorn the "knowledge engine itself", for "knowledge" in thi s special sense. Hence a similar XWORST function can per he~ps be derived, assuming as the "knowledge engine" ordered depth-first search or the B* algorithm (Berliner 76 ] instead of A*. If you give an engine more knowledge, i.e., less errorful knowledge, then it performs better . But some engines ce~n do more than others (or do it faster) w ith the knowledge they are gi ven.

I greatfully acknowledge many fruitful . discussions w ith Herbert Simon regarding this work.