A Problem Similarity Approach to Devising Heuristics: First Results

1. Introduction*, **

·Many combinatcrially large problems cannot be solved feasibly by exhaustive case analysis or brute force search, but can be solved efficiently if a heuristic can be devised to guide the search. Finding such a heuristic for a given problem, however, usually requires an exercise of creativity on the part of the researcher.

Research to date on devising heuristics has spanned several problem-solving domains and several approaches. In <:.ome efforts, the objective has been to optimize, using some adaptation scheme over a number of trials, the values of coefficients determining the relative weighting of several preselected terms in an evaluation function, so as to maximize the overall performance (e.g., [Samuel 1959), [Samuel 1967), [Rendell .1977)). Other approaches to automatic generation of heuristics include [Ernst, et al., 1974) and [Rendell, 1976). Related efforts have focused on what might be called "disciplined creativity", enunciat ing general principles or rules of thumb that a person may C~pply to the problem at hand (e.g., [Polya 191.15), [Wickelgren 1974)).

The approach to devising heuristics proposed here di ffers in perspective from these previous efforts: instead of seeking a heuristic directly, one seeks instead a problem P2 that is easier to solve than the given problem P2 and is related to P2 in a certain way. * The function is an efficient heuristic for finding paths in a next step is to find an alnorithm for finding paths in P2, then apply this aiP,orithtn in a certain way as a heuristic for P 1. As an elementary example, the rectilinear distance "Manhattan street pattern" graph even when some (but not too many) of the streets have been blockaded (i.e., some edges are removed from the graph). Generalizing, the approach Is to consider as candidates problems P2 that are "edge subgraphs" or "edge supergraphs" of the given problem P 1. As a non-trivial application, we show that a certain restricted form of sorting problem (serving as P2) is an edge supergraph of the 8-puzzle graph (Pl). A simple algorithm for solving this sorting problem is evident, and the number of swaps executed in solving an instance thereof is taken as a heuristic estimate of distance between corresponding points in the 8-puzzle graph. Using the A* algorithm, we experimentally compare the performance of this "maxsort" heuristic for the 8-puzzle with others in the literature.

* Thie ru .. rch w .. aponeored by the Defenee Advanced R .... rch

Projecle Aaency (000), ARPA Order No. 3597, monitored by the Air Force Avionic· Laboratory Under Contract F33615- 78-C-1551.

The viewe end conclueione contained in thie document ere tho18 of the author and ehould not be interpreted .. repreeentina the official policiee, e ither e><pre .. ed or implied, of the O.fenee Advenced Rneerch Projecle Acency or the U.S. Government.

** Author'· present eddre··' Artificiol lnteltiaence Center, SRI lnternot ionol, 333 Rovenewood Ave., Menlo Perk, CA 94025

The general class of problems to · which the present approach can be applied are those state space problems that can be represented as graphs, in which the objective is to find a path from a given initial node in the graph to a given goal node. * Such problems can be solved using the A* best-first search algorithm, which iteratively grows a tree or graph of partial paths from the initial node at each step expanding the node (along the edge of this 'tree or graph) that appears to be "best".** The definition of "best" is specified by assigning a number to each node generated, whose computation typically involves the value of a heuristic function K(s, I) used to estimate the distance in the graph from an arbitrary node s in the graph to another arbitrary node I (where I is taken to be the goal node in a p~rticular instan~e of search). Devising heuristic funct1ons that estimate distance between points In a given graph is the present practical objective.

* Thie perspective ie ·omewhet akin to thet on which ere b118d the reeulle of backward error anely1i1 (u defined in the numericel an1lyeie liter·ture), in which one aeke of 1 1111tri· invereion elaorithm, for uample, not how accurate ere the 1n1were thet it compute·, but r1ther how different from the aiven problem i1 the problem for which the computed enewere ere the exact enewere.

Additional theoretical objectives motivated this work: to investigate how "similar" or "dissimilar" problems differ in structural properties, and how such structural differences relate to difference in difficulty to solve the problem. Investigations of relatively simple . problems serve this purpose well. Note that we are not Interested in the 8-puzzle (our principal example) per se, but as a concrete instance with which to investigate general principles.

Section 2 defines the notions of "edge .subgra~h" and "edge supergraph",. and . illustrates lhe1r r!'latlon to heuristic transfer usmg 1 s1mple example -- a Manhattan street pattern" graph and variants thereof. Section 3 applies the basic approach to a larger prob~em -- the 8-puzzle. Sec:tic n 4 di~cusses the generality of the results and poses futurP. tasks.

2. Problem Similarity: Edce Subcraphs and Supercraphs

The basic idea considered in this paper can be illustrated using a simple example. Consider the graphs depicted in Figures la, lb, and lc, which we shall refer to as MSUB44, M44, MSUP44, respectively. We note that these three graphs have identitll numbers of nodes, and that the edges of MSU844 comprise 1 subset of those of M44· similarly the edges of M44 comprise a subset of thos~ of MSUP44. We shall say therefore that MSUB44 is an edge subgraph of M44 and that similarly M44 is an edge subgraph of MSUP44. Likewise we also say that M44 is an edge supergraph of MSUB44 and that MSUP44 Is an edge supergraph of M44. These relations of edge subgraph and edge supergraph generalize formally. in the obvious way for the class of problem ~ wh1ch we define to be any finite, strongly connec.ted graph G - (V E) having no self-loops and no multiple edges. This d~finition includes the familiar problems cited in the preceding section. *

* Elementary e·ample1 of 1uch problem· include the B~puzzle, The Tower of Hanoi the water iut problem, miuionarie1 and cannibala problem ·nd other "to~· problem· familiar in the literature [Niluon 1971, pp. 39-41, 77-78). (.Jeck1on 1974, pp. 81-84, 110-115~ (Raphael 1978, pp. 7g-88], (Wickelsren 1974, pp. 49-57, 78-80 cf.). Somewhat Ia·· frivoloue eiCamplel include certain alttbraic manipulation problem· (Doran It Michie 1988, pp. 254-255~ (Doran 1987, pp. 114-11!5L and a 111raion of the traveNnt nle1pernn problem (Doran 1988~ (Herrit 1974).

**The Graph Travernr ·ltorithm (Doran " Michie 1988) and the HPA ·ftorithm [Pohl 1970.) "' ""nli811y the NIM a1 A·.

To illustrate how edge subgraph or edge supergraph similarity between problem graphs is related to heuristic transfer, we now consider three cases in turn: ( 1) that M44 is the given problem to be solved; (2) that MSUB44 is the given problem; and (3) that MSUP44 is the given problem. In general we wish to solve an arbitrary instance of a given problem graph P, that is to find a path from an arbitrary initial node sr in P to an arbitrary goal node s . (We denote such a problem instance I of a problem gr~h P thus: I · (sr, sl!.).) This trivial example serves as a vehicle for introaucing several general concepts.

The task of finding a path between arbitrary initial and goal nodes in the M44 graph (or in some larger version of this "Manhattan street pattern" graph) is trivial. A simple algorithm for solving instances of this problem graph is readily evident: comparing the coordinales of the current node (starting with the initial node sr), move iteratively up (or down. as the case may be) until the vertical coordinate of the goal node is reached, then move right (or left) iteratively until the goal node is reached. Call this algorithm L (for "L-shaped solution path").

If MSUB44 is taken instead of M44 as the problem to be solved, the A* approach seems more attractive than attempting to devise an algorithm like algorithm L, because of the additional cases an algorithm of the latter sort must account for: besides comparing the coordinates of the current node with those of the goal node, it must also be prepared to make detours when necessary.

To use A* to solve MSUB44, one must supply a heuristic function K(s, t) that estimates distance from node s to node t. Let hp(s, I) denote the actual distance in P from s to t, a·;suming edges have unit weight. In the case K(s, I) · h(s, I) thP tlistance estimate is exact; it is well known [Hart d at. 1968) that this case minimizes the number of nodes expanded -- the number is exactl¥ h(s , s ), the distance from initial node to goal node. * for g M44, it is evident that hM44(s, I) · lxs - Xtl + IYs - Ytl, where x and Ys are the x and y coordinates, respectively, o, node s. For MSUB44 a symbolic formula for h(s, t) Is not so compact, since it must distinguish more cases. An alternative to enunciating h(s, I) for MSUB44 is to use K(s, t) · hM 44 <s, t), i.e., use the distance function of M44 to apprOximate the distance function of MSUB44.

It Is easy to show, as follows, that solution paths found for an arbitrary problem instance of MSUB44 using

* Note that the 8-punle traph con1i1l1 of two di1joint componenta. For pre1ent purpoee1, we con1ider aearch within one auch component. Al·o, WI IllUme that · problem craph ia ·pacified in practice by · ·ucce11ore func lion: SI.IC(1) denot .. , for eny node a in the traph, the 1el of nocle· v 1 for which there t·i·l· an ·dt· from · to v 1 . Typically SIJC(a) I· implemented by t 11t of operatore, each of which tran1form1 a siven ·tate · into another 1tate v 1 , provided tha operator'· precondition i1 11ti·fied. In the 8-puzzte cont ... t, one 1uch operator micht hav· tha effect of movint the hole upward If it i1 not in the top row of tha board.

** To achieve thi1 bound, one mu1t be careful in .. lectins a atraten for re·olvint fie· amont nocle1 for which equtl value· ware nalsned.

'<(s, t) · hM 44 <s, t) will be of minimal length. If P1 and P2 are any problem graphs such that P1 is an edge subgraph of P 2 (denoted P 1 ~ Pz), then the distance between arbitrary nodes s arid t in P2 is never more than the distance between the corresponding points in P 1, i.e., hp 2 (s, t) ~ hp l'(s, t). Hence using the heuristic function K(s, t) · hp 2 (s, t) for solving PI it follows that K(s, t) :S hp1(s, t). Hence by the A* admissibility theorem ([Hart, et al. I968], LGelperin I977 ]) the solution path found is always of minimum length when using K(s, t) - hp 2 (s, t) in solving Pl.*

As a third case, take MSUP44 as the problem to be solved. Now hMsup.q.q(s, t) :S hM44<s, 1), hence taking K(s, t) -= hM 4 .q(s, I) overestimates the distance from s to t in MSUP44: Instead of using A*, however, note that algorithm L can be used to find paths in MSUP44, although they will not necessarily be of minimum length. (Whether this is important depends on the application.) In general, if P2 ~ PI then an algorithm that finds paths in P2 can also be used to find paths in PI (assuming the same encoding scheme is used for identifying corresponding nodes in P1 and P2).

These simple examples illustrate a general approach: given a problem graph PI to be solved, first identify a problem graph P2 that is an edge subgraph or edge supergraph of Pl. We call PI the given problem and P2 the transfer problem. Then find a way of computing hp 2 (s, t). (In the preceding examples a simple formula for hM44 was readily evident. When a formula for hp? is not evident, we instead attempt to devise an algoriThm for computing the values of hp 2 (s, t) by finding a path in P2 from s to t and counting the number of steps in the path. See section 3.) Then use hp 2 (s, t) as a heuristic function for solving instances of PI: given a goal node s , whenever A* calls for a value to be assigned to a node'\ in P1, compute hp 2 (s,sg>·

3. Example: A Sorting Algorithm Used as Heuristic for the 8-Puzzle

Section 3.1 defines the "9MAXSWAP" graph and shows it to be an edgo! supergraph of the 8-puzzle graph. Section 3.2 defines an algorithm, called MAXSORT, for finding paths in t~e 9MAXSWAP problem graph. Section 3.3 reports experimental results measuring the performance of MAXSORT when used as the basis of a heuristic distance-estimating function for the 8-puzzle, and compares this observed performance with those of other known heuristics for the 8-puzzle. This section also proposes and tests another related heuristic for the 8-puzzle. Section 3.4 reports experimental measureme.nts of how closely the heuristic function based on MAXSORT approximates the distance function of the 8-puzzle. This larger example serves as a non-trivial application and as a vehicle for introducing additional concepts.

* A· ie analyud mathematically in [Hart, et el. 1978]. (Pohl 1970a]. [Pohl 1970b], [Niluon 1971], [Harrie 1974], [Yanderbruc 1976]. [Munyer 1976), [Munyer &r Pohl 1976), (lbareki 1977]. [Pohl 1977]. [Gelperin 1977), [Merlelli 1977), [G11chnit 1979]. and eleewhero. Attemplinc to 1pply euch ·nelylic rnulle ie not 1 mejor concern here; in Section 3.3 we me .. ure heurietic performance ··perillllnt·lly.

3.1. The MAXSWAP problem

The 8-puzzle is a one -person game the objective of which is to rearrange :o eiven configuration of eight tiles on a 3x3 board into another given configuration by iteratively sliding a tile into the orthogonally adjacent empty location, like so:

To apply the present approach (which might be called the "edge subgraph/supergraph transfer" approach) to the 8 -puzzle, first we must identify a suitable edge subgraph or edge supergraph of the 8-puzzle. Toward this end we note that an 8-puzzle tile configuration can be considered a permutation of the sequence I,2,. .. ,9, letting 9 correspond to the hole in the 8-puzzle, and numbering the nine locations of the 8-puzzle board in left to right, top to bottom manner, say. Hence the topmost of the four configurations depicted above corresponds to the sequence 398146572.

Now we define the "N-swap" graph to have N! nodes, corresponding to the N! permutations of the sequence 1,2, ... ,N. An edge connects two vertices of this graph iff the corresponding permutations differ by a single swap. In an obvious way, the behavior of any sorting algorithm which operates by sequentially interchanging pairs of array elements can be mapped into sets of paths in this graph. Taking N .. 9, there is evident a one-to-one correspondence between the nodes of 9-Swap (but not the edges) and those of the 8-puzzle graph.

By noting that lhe effect of moving a tile in the 8-puzzle graph is to exchange two elements of a 9 element vector, it is easy to see that the 8-puzzle graph is an edge subgraph of 9SWAP. Hence the 8-puzzle can be viewed as a restricted version of permutation sorting, such that every swap must include the largest element (i.e., 9), and that certain swaps are forbidden, depending on the location of the largest element.

If we impose the restriction on sorting N-element permutations that every :;wap must exchange the largest element, N, with some other element, we obtain what might be called I~"~ "N-MAXSWAP" graph. For illustrative purposes, Figure 2 depicts the 4MAXSWAP graph. Note that 8-puzzle Se 9MAXSWAP ~ 9SWAP, hence for arbitrary nodes s and t, h9SWAP(s, t) :S h9MAXSWAP(s, I) ~ hs-~:~.uzzte<s, 1). Hence tlie d1stance functions of both 9SW.A:t-' ana 9MAXSWAP underestimate the distance function of the 8-puzzle, but that of 9MAXSWAP is a closer approximation of the

8-puzzle's distance function than that of 9SWAP. * We will use 9MAXSWAP as the transfer problem for the 8-puzzle in this example; next, we must demonstrate the transfer.

3.2. The MAXSORT algorithm

We describe now what seems to be a most peculiar way of solving the 8-puule. Given a problem instance, A* iteratively expands nodes in the 8-puzzle graph and requires that a number be assigned to every new node generated, as the basis for deciding which node to expand next. To obtain each such number we propose to solve an entire instance of 9MAXSWAP using an algorithm defined below, and return a number measuring its performance (in fact, the number of swaps it executes). If solving instances of 9MAXSWAP itself required search, this approach might consume more time than if the 8-puzzle were solved using breadth-first search. However, the point of this example is that the 9-Maxswap problem is simpler than the 8-puzzle --- one can readily devise an efficient algorithm for it, as follows.

The basis for an algorithm which we call "MAXSORT" (defined by a SAIL procedure in the test ) for finding paths in an N-MAXSWAP graph is the observation that the largest element, N, in the permutation can always be swapped with the element whose proper place in the permutation it occupies, except when N is in the N'th position of the permutation. We illustrate using N · 4. To sort the permutation P · 2341 (into 1234), the algorithm first swaps 3 and 4 producing 2431, in which the element 3 now occupies its proper place. Next swapping 2 and 4 puts 2 in its proper place and then swapping 4 and 1 puts both those elements in their proper places and the algorithm terminates. To implement this policy of simply swapping the largest element 4 with the element whose proper place 4 is occupying, MAXSORT uses an internal auxiliary array 8, and begins by assigning to 8[i) the location of element i in the input permutation, i.e., 8[1:4)- 4123 for the above example. Then MAXSORT simply swaps iteratively P[8(4)) with P[8[8[ 4)]), updating both P and 8 at each ite~ation, until the sort is complete, with the followng exception to this rule.

Sorting 4321 using MAXSORT, the first swap produces 1324, but now 4 is in its proper place, and so we must do something other than swap 4 with itself indefinitely. Instead, the algorithm swaps 4 with the leftmost element of P that is not in its proper place, i.e., 3 in this case, and we proceed as before. (Determining this leftmost element is accomplished efficiently -- using the variable called avail for bookkeeping, the block named "available-spot-found" is executed at most N/3 times.) So each swap executed by MAXSORT moves zero or one new element, other than N, into its proper place and never moves an element, other than N, from its proper place. Table 1 shows the current permutation, the contents of the elements of 8, and the value of the variable avail for earh step in the above example.

* If the number of edan in 9MAXSWAP were clote to the number in the 8-puule we could infer that the dittance function of the former it 1 cto .. appro><imation of that of t~ .. latter, but euch it not the case' The 8-puzzle, 9MAXSWAI-, end 9SWAP eoch h .. 91 · 362,880 1tod11. The 9MAXSWAP araph hu 4·9! · 1,451,520 eda ... (The number of edaet in the N-MAXSWAP araph i· N· <N- 1 )/2.) Nodn in the 8-puzzle araph ara incident to 2, 3, or 4 edaeo, in the proportion 4A, I, retpeclively. Hence the number of eda11 io 9!(2·4/9 · 3·4/9 · 4·1/9) / 2 · 9'·4/3 · 483,840, 1 factor of 3 fewer thon in 9MAXSWAP. By comporioon, the 9SWAP areph hu 18·9! · 6,531,840 edan, a factor of 3.375 more than in 9MAXSWAP. (The number of edae· inN-SWAP it N! N(N-0/4.)

(Trace this sequence as a path in the graph in Figure 2.) *

To apply MAXSORT as a heur istic for the 8-puzzle, we take N - 9. Let KMAXSOin(p) denote the number of swaps executed by MAXSORT given permutation p. Then given an 8-puzzle instance with arbitrary initial node p and goal node q = 123456789, the function KMAXSORT can serve as a heuristic for the 8-puzzle: we take K(s) · KMAXSORT.(s), obtained for any state s by executing MAXSORT on s and counting the number of swaps it executes. For example if p "'296134758 and q - 123456 789, then MAX SORT executes seven swaps when sorting p, hence K(p) = 7. (It happens that h8-puzzlc(p,q) = 9 in this case.) For other goal nodes q, we compute KMAXSORT(p, q) by simply usinp, MAXSORT to sort p into q by lirsl transforminp, the instance (p, q) into the canonical form (p', 123456789) and then sorting p' by MAXSORT. The permutal ion p' is the image of p under the transformation that maps q into 123456789, e.g., if p- 258491367 and q = 485297361, then 4 in p becomes 1 in p', 8 in p becomes 2 in p', and so on, so that p' · 4 32159786. Note that every swap must include as one of its elements not 9, but rather the image of 9 under this transformat ion, i.e., 5 in this example. (The trivial generalization of the MAXSORT code to accomplish this transformation is omitted here for brevity.)

Since 8 -puzzle ~ 9MAXSWAP it follows that h9MAX5W"P(!>, t) < hgpu:z:zle(~, t). Hence if KMAXSOR..;:ls, t) c h9MAXSWAP(s, I) it follows from the A* adm1ssiollily theorem that solut ion paths found using KMAXSORT(s) as heur ist ic function for the 8-puzzle are of minimal length. * In words, to prove the premise is to show that for any 9-element permutations p and q, the number of swaps executed by MAXSORT in sorting p into q is minimal, i.e., it equals the minimum distance from p to q in the 9-MAXSWAP graph. Instead of attempting to prove this (its relevance beyond the example at hand being minimal), we note that it has been observed that heuristic functions that overestimate distance in a graph often are more efficient than similar functions that always underestimate the true distance ([Doran & Michie 1966]. [Nilsson 1971 ), [Gaschnig 1977), [Gaschnig 1979)). Hence it may advantageous for efficiency in solving the 8-puzzle if KMAXSORT does not find minimal length p~ths in 9MAXSWAP, prov1ded that a guarantee of mm1mal length solution paths in the 8-puzzle is not mandatory.

* The 1eneral behavior of MAXSORT for 4MAXSWAP con be depicted arephically as follows. Since the e><ecut ion of MAXSORT for an orbitrary 4 element permulal ion corriOponda to I path in the 4MAXSWAP craph (aee Ficure 2), the union over ell 4-element permutet ion of the .. ecut ion patha of MAXSORT (ie., to aort into ncendint order) io 1 oubcroph of 4MAXSWAP. In feet thi· oubaroph i· · 1ponnina tree of 4MAXSWAP <· .. Ficure 3.)

3.3. Experimental Performance Measurement Resulta

How efficient is the function KMAXSORT as a heuristic function for the 8-puzzle? To ·fmc out, we selected randomly a set of over 800 problem instances of the 8-puzzle, and solved each of these with A* using KMAXSORT as the heuristic function. As a measure of searcn efficiency, ior each such problem instance (sr· s 2 ) we measured the value of X(sr· sR.), the number of node-s expanded before a solution pam is found to problem instance (sr.· s ) when using KMAXSORT as . a heurist!c function w1th ~*. This sample of problem mstances IS identical to the one used in [Gaschnig 1977) and [Gaschnig 1979), as is the experimental procedure followed, hence those results and the present results are comparable. The problem instances (sr· s 2 ) in this sample are grouped together according to the value of h(sr· s 1 ), the length of a minimum length path in the graph from "'r to sg.

Figure 4 plots the observed values of XMEAN(N), the mean number of nodes expanded as a function of depth of the goal node (i.e., the mean over all instan~es (sr, s 2 ) in the sample such that h(sr, s ) .. N). Super1mposed Ttl Figure 4 for comparison pu~p%s~s are the analogo~s experimental data reported m F1gure 1 of [Gaschmg 1977] and [Gaschnig 1979) tor three particular 8-puzzle heur istic functions there called K 1, K 2 , and K3. Figure 4 shows that KMAXSORT is slightly better than K 1 (s), which computes the number of tiles out of place . in tile configuration s with respect to the goal node. F1gure 4 shows also that KMAXSORT usually expands many more nodes than do K2 or K 3 . ** So it turns out that KMAXSORT is a refatively mefficient heuristic for the 8-puzzre, compared with these other known heuristi.c functions, but inspection of Figure 4 reveals that 11 expands far fewer nodes in solving the 8-puzzle than does breadth-first search.

* At 1 matter of convenience, we tomelim.. write K(1) in1l .. d of K(e, t) when I i· underelood implicitly. For ··ample, in 1ny civen A' aearch node I is understood lo be the coel node.

** K 2 compuln the number of liln out of place, each wtithled by the orlhoconal dostence the tole must move to oh d"ortd 1pot, anumint no other til .. block the path; K 3 equal1 K 2 plu1 enother term menurina the dec··· to which the outer lile1 in 1 ecree in rol1lion·l order to tho .. ~n the coel node. See [Dortn It Michie 1966t [Nolnon 1971t [Gnchn11 1977], or [G11chnlc 1979) for 1ddilion1l clel1il1.

4. Analysis of Distance Function Approximation

The experimental results in Fip,ure 4 pose a challenge: why is KMAXSORT a relatively inefficient heuristic for the 8-puzzle, and 1s it coincidental that its performance is comparable to that of K 1? One approach to answering such questions is lo determine how closely KMAXSORT(s, t) approximates hS-:puzzl.e(s, t). Figure 5 plots experimental measuremenTs or the ranp,e of KMAXSORT's estimates of distance to the goal node in the 8-puzzre vs. the actual distance to the goal. KMIN(i) is defined with respect to KMAXSORT to be the minimum value of KMAXSORT(s, t) over an node pairs (s, t) such that h(s, t) .. 1, and similarly KMAX(i) is the maximum of these values. Hence KMIN(i) and KMAX(i) bound the values computed by KMAXSORT for nodes that happen to be distance i from the eoal. The data plotted in Figure 5 were recorded during the same experiment represented in Figure 4, in the following way. The value of KMAXSORT(sr, s 8 ) was recorded for each problem instance (sr., s 8 ) in the sample set. The value of h(sr, srz) equals the length of the solution path found, which is of minimum length since I<MAXSORT underestimates distance in the 8-puzzle graph. rn addition we measured the value of KMA>.<SORr(s,s ) for each node s along the solution path found fo.,. each problem instance in the sample set. Since the solution path found is of minimum length, the value of h(s,s 8 ) is known for each such node s. In all, Figuro~ 5 represents over 10,000 distinct observations of KMAXSORr(s, t) vs. h8- uzzl (s, t). Superimposed for compar1son in ~igure 5 arf anaFogous experimental me;~~c;urements of KMIN(i) and KMAX(i) for K 1, taken from Figure 2 in [Gaschnig 1977] or [Gaschnig 1979].

Figure 5 shows both that KMAXSORT is a poor approximation of hs-Duzzle· and that the approximation is only slightly better tnan tnat of K 1·

5. Discussion

We have described a general principle of problem similarity for path-finding state-space problems -- the edge subgraph and edge supergraph relations. We have demonstrated, using the 8-puzzle as case study, how this principle of "edge subgraph/supergr.aph transfer" can be exploited to aid in devising a heuristic function for a given problem, by transferring a heuristic from an "easier" problem to a related "harder" one. We have measured experiment ally the efficiency of the resulting heuristic function devised for the 8-puzzle, demonstrating at least a limited practical utility.

These first results leave many questions unanswered. Our intention here has been merely to introduce the idea for further consideration. Hence the remainder of this discussion focusses on extensions to the present efforts.

Additional insight might be obtained by applying the transfer approach to additional problem graphs, including some in which the transfer problem is an edge subgraph of the given problem instead of an edge supergraph, as in the 8-puzzle case study. In particular, we note of the 8-puzzle case study that a transfer problem (9MAXSWAP) was readily apparent, that an efficient algorithm for 9MAXSWAP was readily devised, and that this algorithm proved to be a relatively inefficient heuristic function for the 8-puzzle. How formidable these hurdles are for other problems remains to be determined.

Another objective is to attempt to devise for the 8-puzzle another transfer problem which is a closer approximation to it than is the 9MAXSWAP graph, that is to identify a problem graph that is an edge supergraph of the 8-puzzle and an edge subgraph of 9MAXSWAP.

It may be interesting to apply this transfer concept in reverse fashion: given a particular heuristic function for a given problem, identify the graph to which it is equivalent. For example, 1 one might attempt to determine whether a graph corresponding to the K 1 function is an edge supergraph of the 9MAXSWAP graph, oi to identify a graph corresponding to the function K2. A theory about the equivalence of problem graphs and heuristic functions along these lines is conceivable.

Acknowledgement. Richard Korf offered helpful comments on an earlier draft of this paper.

6. References

Doran, J., "An Approach to Automatic Problem Solving," in Machine Intelligence 1, N. Cotlins and D. Michie (eds.), American Elsevier Publ. Co., New York 1967.

Doran, J., "New Developments of the Graph Traverser," in Machine Intelligence 2, E. Dale and D. Michie (eds.), American Elsevier Publ. Co., New York 1968.

Doran, J., and D. Michie, "Experiments with the Graph Traverser Program," Proc. Royal Society of London, Series A, Vol. 294, 1966, pp. 235-259.

Ernst, G.W., Banerji, R.B., Hookway, R.J., Oyen, R.A., and Shaffer, D.E., "Mechanical Discovery of Certain Heuristics", Report 1136-A, Jennings Computing Center, Case Western Reserve IJniv., CIP.veland, Ohio, January 1974.

Gaschnig, J., "Exactly How Good are Heuristics?: Toward a Reali!>l ic Predictive Theory of Be!it First Search", Proc. 1ntl. Joint Conf. on Artificial Intelligence, Cambridge, Mass., August 1977, pp. 434-441.

Gaschnig, J., Performance Measurement and Analysis of Certain Search Algorithms, Ph.D. thesis, Dept. of Computer Science, Carnegie-Mellon University, Pittsburgh, Pa., May 1979.

Gelperin, D., "On the Optimality of A*," Artificial Intelligence, Vol. 8, 1977, pp. 69-76.

Harris, L., "Heuristic SEarch under Conditions of Error," Artificial Intelligence, Vol. 5, No. 3, North Holland Pub!. Co., Amsterdam, 1974, pp. 217-234.

Hart, P., N. Nilsson and B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," IEEE Trans. Sys. Sci. Cybernetics, Vol. 4, No.2, 1968.

lbaraki, T., "Theoretical Comparisons of Search Strategies in Branch-and-Bound Algorithms," International Journal of Computer and Information Sciences, Vol. 5, No. 4, December 1976, pp. 315-344.

Jackson, P. Introduction to Artificial Intelligence, Petrocelli Books, New York 1974.

*Given e heurielic function K for · siven problem sreph PI, one cen define enolher sreph P2 lhu·' the nod .. in P2 correepond to the node· in P 1; en eels· conned· two node· · end I in P2 iff K(e, I) · 1. Whether or not P2 eeliefiee the conditione of problem sreph depend· on the velue computed by K.

Martelli, A., "On the Complexity of Admissible Search Algorithms," Artificial Intelligence, Vol. 8, 1977, pp. 1-13.

Munyer, J., "Some Results on the Complexity of Heuristic Search in Graphs," Technical report HP- 76-2, Information Sciences Dept., U. Cal. Santa Cruz, September 1976.

Munyer, J., and I. Pohl, "Adversary Arguments for the Analysis of Heuristic Search in General Graphs," Technical report HP-76-1, Information Sciences Dept., U. Cal. Santa Cruz, July 1976.

Nilsson, N., Problem Solving Methods in Art ificial Intelligence, 1971.

Pohl, 1., "First Results on the Effect of Error in Heurist ic Search," Machine Intelligence 5, B. Meltzer and D. Michie (eds.), Edinburgh University Press, Edinburgh 1970 (1970a).

Pohl, I., "Heuristic Search Viewed as Path-Finding in a Graph", Artificial Intelligence, Vol. 1, 1970 (1970b).

Pohl, 1., "Practical and Theoretical Considerat ion in Heuristic Search Algorithms," in Machine Intelligence 8, E. Elcock and D. Michie (eds.), Ellis Howard ltd., Chichester, England 1977.

Polya, G., How to Solve It, Princeton University Press, Princeton, N. J. 1945.

Raphael, 8., The Thinking Computer : Mind Inside Matter, W. H. Freeman & Co., San Francisco 1976.

Rendell, L., "A Method for Automatic Generation of Heuristics for State-Space Problems", Report CS-76-10, Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada, February 1976.

Rendell, L., "A Locally Optimal Solution of the Fifteen Puzzle Produced by an Automat ic Evaluat ion Funct ion Generator," Report CS-77-36, Dept. of Computer Science, University of Waterloo, December 1977.

Samuel, A., "Some Studies in Machine Learning Using the Game of Checkers," in E. Feigenbaum and J. Feldman (eds.), Computers and Thought, McGraw-Hill 1963, pp. 71-105.

Samuel, A., "S-.me Studies in Machine Learning Using the Game of Checkers II. Recent Progress", IBM J. Research and Development, Vol. 11, No. 6, ( 1967), pp. 601-617.

Schofield, P. "Complete Solution of the Eight Puzzle," in Machine Intelligence 1, N. Collins and D. Michie (eds.), American Elsevier Publ. Co., New York 1967.

Slagle, J., and Farrell, C., "Experiments in Automatic Learning for a Multipurpose Heuristic Program," Communications A.C.M., Vol. 14, No. 2, pp. 91-99.

Swinehart, D., and 8. Sproull, SAIL, Stanford Art ificial Intelligence Laboratory Operating Note 57.2, January 1971.

Vanderbrug, G., "Problem Representations and Formal Properties of Heuristic Search," Information Science, Vol. 11, No. 4, 1976.

Wickelgren, W., How to Solve Problems, W. H. Freeman and Co., San Francisco 1974.

Minimum number

of swaps required

to sort

"iii

0

1:>0

u c:

0 -Cl)

"'

....

:.0

0

.2!

"'

Cl)

E - "'

·.:::

:l

~ "'

Q)

.c

II

::..::