Machine Discovery of Effective Admissible Heuristics

1 Introduction

Admissible heuristics are an important class of heuris­ tics worth discovering: they guarantee shortest path so­ lutions in search algorithms such as A· and they guar­ antee less expensively produced, but boundedly longer solutions in search algorithms such as dynamic weight­ ing [Pohl, 1973] and A; [Pearl, 1984]. Unfortunately, heuristics that are both admissible and effective ( accu­ rate and cheap to compute) often take years for people to discover. For example, although the Traveling Sales­ person problem was introduced in mathematical circles as early as 1931 [Lawler and Lenstra, 1984], it was not until 1971 that the Minimal Spanning Tree heuristic for it was discovered. The ultimate goal of this research is to develop a system for discovering effective admis­ sible heuristics automatically, thereby shifting some of the burden of discovery from humans to machines. This paper describes and evaluates an implemented program (Absolver II) that can tractably discover effective admis­

sible heuristics.

Previous proposed, but unimplemented methods to generate admissible heuristics for a problem involve find­ ing the length of a shortest path solution to transformed version of the problem; the length is the admissible heuristic. The transformations include edge supergraphs [Guida and Somalvico, 1979; Gaschnig, 1979], opera­ tor precondition dropping [Pearl, 1984], and homomor­ phisms [Kibler, 1985]. Analytic results show that for such heuristics to be effective, the transformed prob­ lems that generate them should be easier to solve and close to the original problem [Valtorta, 1984; Mostow and Prieditis, 1989]. One suggested way to make a trans­ formed problem easier to solve is to factor it into in­ dependently solvable subproblems when possible [Pearl, 1984]. The only implemented program to generate ad­ missible heuristics by searching for easy-to-solve trans­ formed problems (Absolver I) uses an exhaustive gen­ erator [Mostow and Prieditis, 1989]. Because the space of transformed problems is generally too large to search exhaustively, a smarter method of search control is re­ quired.

This paper extends previous work in three ways. First, it extends and unifies previous definitions of transfor­ mations that generate admissible heuristics (Section 2) . Second, it extends Absolver l's transformation catalogs (Section 3). Finally and most important, it describes and evaluates a new search control mechanism as imple­ mented in Absolver II (Sections 4 and 5).

2 Abstracting Transformations

Intuitively, an abstracting transformation removes de­ tails. To forma-lize this intuitive definition requires a few preliminary definitions. Let a state space search prob­ lem be a 3-tuple < S, c, P >, where S is a set of states describing situations of the world; c : S x S --+ !R is a total positive cost function that returns the length of a directed arc from one state to another; and P is a predicate that characterizes a class of goal states. For example, in the Eight Puzzle problem, the set of states consists of all tile permutations; the cost function on a pair of states returns 1 if one state is reachable from the other by swapping the blank with an adjacent tile, and oo otherwise. A goal predicate might specify that the tiles are to be in a particular order. Problem solving involves finding a finite sequence of states leading from the initial state to a state that satisfies the goal predicate. The cost function can be specified explicitly with a matrix or implicitly, relative to a set of parameterized actions called operators. Similarly, the goal predicate can be specified explicitly by enumerating all goal states or implicitly, relative to a goal statement that defines a class of states.

A function ¢ : S --+ S' is abstracting from problem < S, c, P > to problem < S', c', P' > iff for all s, t E S:

1. ¢ is total: ¢( s) E S'
2. ¢preserves or reduces cost: c'(¢(s), ¢(t)) ~ c(s, t)
3. ¢preserves goals: P(s)::? P'(¢(s))

As shown in Figure 1, a heuristic for a state in problem < S, c, P > is computed by first abstracting the state and then finding a shortest path solution in the abstracted problem< S', c', P' > (e.g. with A*). The length of that shortest path solution is the admissible heuristic. 1 For example, if the requirement that the adjacent location need be blank is dropped from moves in the Eight Puz­ zle problem, then moves in the abstracted problem will result in states where tiles are superimposed. The length of a shortest path solution in this transformed space is therefore an admissible heuristic for the original prob­ lem. In fact, -this length is the Manhattan Distance over summed all tiles (i.e. the rectilinear distance to each tile's goal destination).

Our definition of abstraction is sufficiently general to cover edge supergraph transformations, precondition dropping transformations, homomorphisms, and other admissible-heuristic-generating transformations not cov­ ered by these (e.g. subgoal dropping).

3 Extended Transformation Catalogs

Table 1 shows Absolver II's catalog of abstracting trans­ formations, which operate on the same STRIPS-style problem representation [Fikes et al., 1972] of Absolver I. Each transformation has been proved to be abstracting [Prieditis, 1990], thereby guaranteeing that all heuris­ tics generated from the catalog are indeed admissible. Since using breadth-first search to compute a heuristic generated from an abstracted problem is generally too expensive, we have implemented a catalog of speedup transformations (shown in Table 2 and henceforth called speedups), each of which has been proved to preserve ad­ missibility [Prieditis, 1990].

1 Admissibility, composability, partial ordering, and other results are proved in [Prieditis, 1990].

For example, after applying drop(Blank) in the Eight Puzzle, the resulting abstracted problem can be factored into a set of independently solvable problems; then finite differencing can be applied to recompute only that fac­ tor's heuristic that requires updating after each move in the original space; and finally, a lookup table can be precomputed for each factor. For n x n puzzles, the complexity reduction 1s as follows (original problem is leftmost):

Figure 2 summarizes our model for discovering ad­ missible heuristics. An abstracted version of the orig­ inal problem is sped up and then used as an admissi­ ble heuristic for all problem instances (problem + initial state). Notice that the effort to discover a heuristic for a problem is amortized over all instances of a problem because the derived heuristic is not instance-specific.

4 Absolver II

Absolver II uses a table (Table 3) of plausible abstracting transformations for each implemented speedup to iden­ tify and eliminate obstacles to applying speedups. 2 An "x" in a particular row/ column entry of this table means that the row's abstracting transformation is likely to lead to satisfying the column's speedup transformation, given our experience in applying the model by hand.

2 Finite Differencing is not shown because it is implicitly part of Factor; Precompute is not shown because it depends on hard-to-predict information such as search space size.

Using this table, Absolver II outputs the first heuristic it finds, which it assumes to be the best one, subject to the following evaluation criteria implicit in its search mechanism:

• The less information dropped to derive the heuristic the better (e.g. drop fewer preconditions).
• A heuristic must be derived from an abstracted problem that can be sped up. To avoid generat­ ing useless heuristics, Absolver II incorporates nec­ essary conditions for speedup into its generator of abstractions.

Absolver II is actually comprised of three subprograms: Composer, Dropper, and Summarizer. Using several meta-heuristics, Composer searches through the space of composition abstractions (e.g. sum) for those abstrac­ tions that lead to the removal of subsumed operators. Dropper attempts to factor a problem into independent subproblems by applying drop..pre and drop_goal (ir­ relevant operators are implicitly removed; drop is mod­ eled in terms of these two transformations). Dropper first builds a set of preconditions and subgoals to drop that are sufficient to make a pair of subgoals indepen­ dent. Next, using several meta-heuristics and a standard search algorithm for combining these drops, it tries to find a minimal set of drops that allows factoring. Sum­ marizer attempts to obtain a problem in which subsumed operators can be removed by applying count (to every predicate). Failing that, Summarizer applies parity (to every integer) in an attempt to obtain a problem in which subsumed operators can be removed. 3

Absolver II's overall search strategy is as follows. First, it calls Composer. If Composer fails to find a problem in which a certain percentage of subsumed op­ erators can be collapsed, then Absolver II calls Dropper. If Dropper cannot factor the problem into two or more independent subproblems, then Absolver II calls Sum­ marizer as a last resort. After Absolver II succeeds in applying a speedup transformation within either Com­ poser, Dropper, or Summarizer, it calls itself recursively on the resulting problem, thus resulting in a hierarchy of abstractions, which generates a hierarchy of heuris­ tics, each of which is used to more efficiently compute heuristics lower in the hierarchy. The rest of this section describes Composer and Dropper; Summarizer is not de­ scribed since it is relatively straightforward.

4.1 Composer: The Search for Subsumability

Composer's goal is to find an abstracted problem in which subsumed operators can be removed. It tries to reach this goal by searching through the space of pair-wise compositions with a standard hill-climbing al­ gorithm and a meta-heuristic in the form of a "simi­ larity" coefficient on each candidate composition. The similarity coefficient returns the number of pairs of op­ erators in which the composition results in the same value. The larger the similarity coefficient, the more likely that a particular composition will lead to operator subsumption. Composer applies the similarity coefficient to each pair-wise candidate composition and then prO­ ceeds in the direction of that pair-wise composition with the largest similarity coefficient (ties are broken arbitrar­ ily).

When the number of uninstantiated operators after subsumed operators are removed is 75% of the number of original operators, Composer calls itself recursively to build a hierarchy of heuristics. The 75% value, which we chose initially and have not had to change, is a rough indicator that the branching factor of the abstracted problem is sufficiently reduced such that search will b~ cheaper than in the original space, but not reduced so much that inaccurate though cheap-tO-compute heuris­ tics result.

For example, in the Fool's Disk problem (shown in Figure 3), where the object is to rotate each of the con­ centric disks until the numbers on each radius (labeled r1 - rs) sum to 12, Composer generates the hierarchy of problems shown in Figure 4, each of which generates an admissible heuristic.

The Diameters problem is a transformation of the orig­ inal Fool's Disk problem where the following pairs of radii are summed using the sum transformation: r1 and r 5 , r 2 and r 6 , r3 and r7, and r4 and rs. The Perpen­ dicular Diameters problem is a transformation of the Diameters problem where perpendicular diameters are summed. For example, in the Perpendicular Diameters problem, the composite r 1 and rs is summed with the composite r3 and r7. The All Numbers problem is a transformation of the Perpendicular Diameters problem:

3 Currently, Absolver II collapses problems to closed form only opportunistically.

all the numbers are summed. To compute, for exam­ ple, the Diameters problem heuristic for any state in the original Fool's Disk problem, the state is abstracted (by summing opposite radii) and then the search algorithm (e.g. A ·) is called recursively with the Diameters prob­ lem and the abstracted state. If this heuristic returns oo for a state at any level of abstraction, then the state can be pruned. In sum, to prune states that cannot reach the goal, the original Fool's Disk relies on the Diameters problem, which in turn relies on the Perpendicular Di­ ameters problem, which finally relies on the All Numbers problem. 4

The complexity of Composer is dominated by the com­ plexity of computing the similarity coefficient, whose complexity is O(m 2 ) for m operators. For each non­ recursive call of Composer, the similarity coefficient will be computed n(n- 1)/2 times for n integers since only integer pairs (or bags) are processed. Thus the total complexity of Composer is 0( m 2 n 3 ) since Composer will call itself recursively at most O(n) times.

4.2 Dropper: The Search for Factorability

Dropper is actually composed of two subprograms: Pair­ wise and Combine. Over each pair of subgoals, Pairwise finds a set of precondition and subgoal drops sufficient to make the pair of subgoals independent. For exam­ ple, Figure 5 shows that given a su bgoal At ( 1 , A) and a subgoal At ( 2, B) in the Eight Puzzle, an operator of the form Move(1,_,A) directly adds At(l,A) and an op­ erator of the form Move(2,_,B) directly adds At(2,B). Since Move ( 1, _,A) places the blank in some location (possibly location B) and Move ( 2, _,B) places the blank in some location (possibly location A), these operators might interact through Blank of both operator's pre­ conditions. Dropping Blank from the precondition of the Move operator eliminates this interaction. To test if the entire goal is factorable into at least two parts, the drop sets from each pair of subgoals must be com­ bined somehow. Combine uses an iterative deepening search algorithm with the meta-heuristic of focusing on the most frequently occurring drops first. This search algorithm tends to minimize the number of drops to ob­ tain a problem that can be factored into two or more subproblems. In our Eight Puzzle example, which only has a single drop set (dropping Blank from the operator and the goal), Combine converges to a factorable set af­ ter one iteration. Combine is then called recursively on each of the factors. It then terminates successfully since no other factorings can be obtained within each factor and produces the AND tree of factors shown in Figure 6, which is used to compute the Manhattan Distance heuristic.

4 These admissible heuristics are not to be confused with the Fool's Disk problem-solving strategy described in [Ernst and Goldstein, 1982].

The complexity of Dropper is dominated by Pairwise, which constructs a transitive closure of the set of op­ erators that can possibly lead to achieving a goal. The worst-case complexity of constructing this transitive clo­ sure is O(btb), where bb is the backward branching factor (the average number of operator instances that adds a given predicate) and db is the backward depth (the length of the longest chain of operators in the set of relevant operators for a given subgoal). That is, the number of preconditions that Pairwise examines is proportional to the number of paths from a subgoal to each operator in the chain.

5 Experimental Results

Table 4 presents the results of applying Absolver II to several well-defined search domains, each of which is suf­ ficiently complex to require heuristics. The table lists the domain, the name of the heuristic, and the percentage of the space that was explored (to two significant dig­ its). The percentage is computed by dividing the num­ ber of heuristics generated before the named one was found by the number of abstractions with respect to our catalog of abstracting transformations and multiplying by 100. 5 The space size is a conservative estimate in that it includes only those abstractions that Absolver II actually used. For example, the space size for deriving the Manhattan Distance is 4096, since Absolver II only drops operator preconditions and subgoals to derive the heuristic and there are 9 subgoals and 3 preconditions (2 9 + 3 = 4096). Since integers are not part of the prob­ lem specification for the Eight Puzzle, Absolver II does not apply transformations such as sum. In contrast, to derive the Fool's Disk heuristic, Absolver II only applies sum (to the 8 radii) and not other transformations; it therefore searches a space of size 2 8 ( = 256).

The results of this table can be summarized as follows. Absolver II discovered effective admissible heuristics in 6 out of the 13 domains by exploring only a fraction of the space of heuristics derivable by the abstracting transfor­ mations in our catalog. Absolver II discovered 8 novel heuristics, 5 of which turned out to be effective. The novel effective heuristics include the first known (non­ trivial) admissible heuristic for the 3 x 3 x 3 Rubik's Cube (partially precomputed Center-Corner), which re­ sulted in roughly 8 orders of magnitude speedup with A* over blind search for long solutions; the best admissible heuristic for the Eight Puzzle (precomputed X-Y), which expanded 1.8 times fewer states than the Linear Con­ flict heuristic [Hansson et al., 1989], an adjusted more informed version of the Manhattan Distance heuristic; a heuristic in the Rooms World problem (search-computed Box Distance), which counts the minimum number of rooms each box must pass through to reach its goal des­ tination and which expanded 267 times fewer states than blind search; the Diameters Fool's Disk heuristic, which expanded 45.41 times fewer states than blind search; and an Instance Insanity heuristic, which is analogous to the Diameter's heuristic in that opposite side colors are combined and which expanded 2.61 times fewer states than blind search.

~Problem formulations, methods for choosing good formu­ lations, derivations, and performance of the resulting heuris­ tics are detailed in [Priedi tis, 1990] .

Absolver II derived several known admissible heuris­ tics including the Manhattan Distance heuristic of the Eight Puzzle (using a different formulation than for the X-Y heuristic) , the Number of Misplaced Disks heuris­ tic of the Towers of Hanoi, the Mutilated Checkerboard heuristic, and the Number of Misplaced Blocks heuris­ tic. All except the Manhattan Distance heuristic were of the same complexity as the originals-the Manhattan Distance heuristic is slower by O(n) for n x n puzzles because the derived heuristic uses search to compute the number of moves needed to get each tile from its current location to its goallocation. 6

Absolver II derived several inferior heuristics. In the 2-D Routing domain, Absolver II derived the "Unvisited Signals" heuristic, which returns a count of the number of non-reached signal locations, instead of the more in­ formed Steiner Tree heuristic, which returns the length of a minimum rectilinear spanning tree and which we derived by hand [Prieditis, 1990], because it dropped a relation that was too salient for the problem. In the Traveling Salesperson Problem, Absolver II derived the "Unvisited Cities" heuristic, which computes the sum of the least cost edges leading to an unvisited city over all unvisited cities, instead of the more informed Mini­ mal Spanning Tree heuristic, which we derived by hand [Prieditis, 1990], because we have not implemented the speedup required to derive the Minimal Spanning Tree heuristic.

Absolver II failed to find an effective admissible heuris­ tic for the Think-A-Dot, Eight Queens, and Scheduling problems for the same reason we failed to find one by hand [Prieditis, 1990]: all abstractions that could be sped up removed too many important details and there­ fore resulted in relatively uninformed heuristics. For ex­ ample, to obtain the factorable abstracted problem that results in the Unassigned Jobs heuristic for the Schedul­ ing domain, the time and seriality constraints must be dropped. The resulting heuristic, which returns the min­ imum costs of unassigned jobs, is poorly informed. Our approach to discovering admissible heuristics appears to be unsuitable when the original problem is characterized by high goal or operator "interference" (many operators directly change a large proportion of subgoals in the orig­ inal problem or make a large proportion of operators subsequently inapplicable) and all abstracted problems are characterized by low goal or operator "interference" (few operators directly change a large proportion of sub­ goals or make operators inapplicable). Of course, it may be that to derive effective admissible heuristics for such domains requires abstractions and speedups beyond our model or that we were not able to find a "good" formu­ lation in which to derive heuristics.

6 Assuming finite differencing and ignoring a one time 0( n 4 ) initial computation.

6 Conclusions and Future Work

Absolver II tractably discovered many known admissi­ ble heuristics (though with varying efficiency relative to the original versions) and some novel effective admis­ sible heuristics by using a means-ends analysis search strategy. Some of these heuristics were still effective even though they are computed by search. Such search­ computed heuristics might be important in domains where effective closed-form heuristics cannot be found (e.g. Rooms World) .

As Absolver II is an experimental system, it has sev­ eral shortcomings, each of which suggests interesting di­ rections for future research. First, because it sometimes drops salient relations of a problem, it might be enhanced by a theory that links information loss via abstraction to accuracy of the resulting heuristics. This theory might allow Absolver II to predict the effectiveness of heuristics without testing them, which is currently left up to the user. Second, non-abstracting transformations might be required to derive effective heuristics in certain domains (e.g. Eight-Queens). Third, Absolver II might be able to boost the informedness of certain admissible heuris­ tics by taking into account interactions in the base level between independently solvable factored subproblems in the abstract level. For example, the LC heuristic might be derivable by incrementing the Manhattan Distance heuristic by 1 for each base-level interaction found be­ tween independent factors with only one shortest path solution. Finally, Absolver II sometimes derives infe­ rior heuristics because it overestimates the number of relations to drop to remove interactions; examples could help it focus on those interactions that actually occur. For example, Absolver II could assume (at the cost of admissibility) that a problem is factorable until an in­ teraction is detected among its factors when computing a heuristic for a particular problem instance. Once such an interaction is detected, its cause could be located and eliminated by abstraction.

Despite its shortcomings, Absolver II concretely demonstrates that effective admissible heuristics can be tractably discovered by a machine.

Acknowledgements

Thanks go to Jack Mostow, Tom Mitchell, Alex Borgida, Saul Amarel, Haym Hirsh, Christina Chang, Mukesh Dalal, Sridhar Mahadevan, and Prasad Tade­ palli. Thanks also go to Rich Cooperman for testing the Rubik's Cube heuristics and to Rich Korf for supplying the IDA* program used to collect data for the Manhat­ tan Distance heuristic.