Discovering Admissible Heuristics by Abstracting and Optimizing: A Transformational Approach

1 Introduction

Finding optimal {least cost) solutions to large state­ space problems is generally intractable without good admissible heuristics (evaluation functions that return lower-bound estimates of distance to goal). When cou­ pled with search algorithms that ensure optimality, like A· [Nilsson, 1980] or iterative-deepening A· (IDA·) [Korf, 1985a], such heuristics can reorder the search so that solutions are found much earlier. They can also reduce search by pruning states that lie more than a specified distance from the goal . This distance may be the exact solution length for problems where it is known a priori, an upper bound on acceptable solution length, or just infinity, in which case the predicate tests whether the goal is reachable at all from a given state.

However, good admissible heuristics can be hard to find . For example, after extensive study, Korf was un­ able to find a single good heuristic evaluation function for Rubik's Cube [Korf, 1985b]. He concluded that "if there does exist a heuristic, its form is probably quite complex."

The long-term goal of our research is to develop a sys­ tem that can discover good admissible heuristics auto­ matically, or at least with less user effort than discover­ ing them by hand. The main contribution of this paper is a model for discovering such heuristics, and its par­ tial implementation in a system called ABSOLVER. We next describe how it worlcs, and then evaluate it as an explanatory model, as a generative model, and as an au­ tomatic discovery engine.

2 ABSOLVER

Our approach, illustrated in Figure 1, derives admissi­ ble heuristics from abstractions of a state-space problem. ABSOLVER is initially given a STRIPS-like representa­ tion of a problem class. The distinction between a prob­ lem class and a problem instance is important because the effort of discovering a heuristic can be amortized over all instances of the problem class.

ABSOLVER generates abstractions by dropping infor­ mation from this description via a series of abstracting transformations chosen from a catalog. An optimal so­ lution path for any resulting abstracted problem gives a lower bound on true distance to goal. This lower bound can then be used as an admissible evaluation function for guiding the base-level search. Moreover, if the ab­ stracted goal is unreachable from an abstracted state (within the specified upper bound), the original state can safely be pruned.

However, using brute-force search to solve the ab­ stracted problem is generally too expensive. Suppose that using the abstracted problem to estimate distance to goal reduces the branching factor of the base level search from b to c. Base level depth is unchanged, so c 4 base level states must be e~anded and evaluated. Without optimization, it costs b,.· to perform each eval­ uation by searching an abstracted space with branching factor b .. and depth d,.. This strategy pays off only if c 4 * b!· < b 4 . Therefore an optimization phase is needed to speed up the computation of the heuristic, for exam­ ple by factoring the abstracted problem into independent subproblems.

Finally, since this model can generate good and bad heuristics, the effectiveness of a heuristic is evaluated on sample instances of the problem.

We now use a running example to illustrate each com­ ponent of this model in more detail.

2.1 Representation

Our model starts with a STRIPS-style problem class rep­ resentation consisting of a goal and a set of operators. To avoid anomalous abstractions, we exclude negation and universal quantifiers, and require the delete list to be a subset of the precondition list. An individual prob­ lem instance consists of finding a sequence of operator applications leading from a specified initial state to a state matching the goal.

For example, the Eight Puzzle can be represented in terms of the predicates at(T, S) (tile Tis on square S), blank(S) (squareS is blank), and adj(S, S') (squareS is adjacent to square S'). The goal is re resented as a list ofsubgoals, e.g., {at( a, 1),at(b, 2), ... , blank(6) , where tiles are lettered a through g and squares are numbered 1 through 9. A single operator suffices:

The boxes will be explained later.

The heuristics generated by ABSOLVER depend to some extent on the initial representation. For example, ABSOLVER produces somewhat different results given a Cartesian representation in terms of the following pred­ icates. The predicate zloc(T, X) holds if tile T is at z-coordinate X; yloc(T, Y) if tile T is at y-coordinate Y; zlocb(X) if the blank is at z-coordinate X; ylocb(Y) if the blank is at y-coordinate Y, and adj(U, V) if U and V are adjacent z or y coordinates. The same goal now looks like

where z andy coordinates are numbered 1 through 3. Two operators suffice for this representation:

Other representations are also possible, for example, by treating the blank like a tile that happens to satisfy a predicate i1blank{T ).

2.2 Abstraction

Given a particular problem class representation, AB­ SOLVER generates abstractions of it by applying trans­ formations chosen from the catalog shown in Table 1. These transformations resemble generalization rules like those in [Michalski, 1983], except that they apply to state-space problems rather than concept descriptions. For example, ABSOLVER can derive a heuristic that is functionally equivalent to Manhattan Distance by apply­ ing the drop_predicate transformation to the blanlc pred­ icate in the single-operator representation, or to zlocb and ylocb in the Cartesian representation. In either case, the abstraction is formed by dropping the boxed pred­ icates from the operators and goal. In the abstracted problem space, each tile can move to adjacent squares regardless of where the other tiles and blank are.

2.3 Optimization

An abstracted problem can be sped up by one or more of the optimizing transformations listed in Table 2provided it satisfies their preconditions. Unfortunately, most abstractions do not; Section 3.3 discusses the dif­ ficult problem of finding abstractions that can be opti­ mized.

In our example, we can use the factor transforma.­ tion to split the abstracted problem into 8 independent subproblems, one for each tile. Next, factor simplifies each subproblem by restricting the set of operators to those that are relevant to achieving the subgoal. For example, the first subproblem has the goal at(a,1) and the restricted operator m011e(a, S, S'). For ann by n ver­ sion of the Eight Puzzle, this step reduces the abstracted problem from a search space containing (n 2 -1)"' states ( n 2 possible locations for each tile) to ( n 2 - 1) indepen­ dently solvable problems of size n , which can be solved in total time O(n 4 ).

If we use the Cartesian representation, we can obtain further speedup by applying drop..precondition to zloc in the ymove operator and yloc in the zmove operator, and factoring into separate subproblems for the z and y dimensions. The resulting problem has 2n 2 - 2 indepen­ dent subproblems, one for each tile and each dimension. For example, the first subproblem has the goal zloc(a, 1) and the restricted operator Zm011e(a,X,X'). Each sub­ problem has a search space of size n, corresponding to the number of columns (or rows). Thus the total time to evaluate Manhattan Distance is reduced to 0( n 3 ). In comparison, the standard closed-form formula for Man­ hattan Distance takes time O(n 2 ), the number of tiles.

2.3.1 Testing Factorability

The factor transformation partitions the goal into mu­ tually independent sets of subgoals, and identifies the op­ erators relevant to each set. The independence property ensures that the sum of the optimal solution costs for achieving each set is optimal for achieving their union, and is therefore admissible.

Thus in order for factor to be practical, we need an efficient way to check that two sets of goals, g1 and g2 , satisfy the following property:

Here diat(a,g) denotes the length of an optimal path from state B to goal g.

ABSOLVER computes a sufficient condition for (1) by overestimating the interactions among operators that might affect the various goals. The idea is that two goals are independent if no operator affects them both. To formalize this sufficient condition, we introduce the fol­ lowing relations:

Canhelp(g1, 92) iff some operator that adds 91 also adds a precondition of some operator that adds (a con­ junct of) 92.

Canhelp* is defined as the transitive closure of the Canhelp relation.

Affecta( op, g) iff op adds or deletes a predicate p such that Canhelp *(p, g).

Indep(gl! 92) iff ( -,:Jop )Affecb( op, gt) 1\ Affects( op, g2).

lndep(g1,g2 ) is the desired sufficient condition for (1).

To prove lndep(g1, 92), ABSOLVER computes the transitive closure of Canhelp. Without function symbols or negation, this closure is finite, but can be expensive to compute exactly. Therefore, ABSOLVER uses a form of symbolic evaluation that over-estimates the Canhelp* relation. To form the set of goals that can help achieve a predicate p, ABSOLVER backchains through every op­ erator that can add p, inserting its preconditions in the set. For example, when ABSOLVER backchains from the goal at(a,1) through the abstracted m011e operator, which adds at(T, S'), it binds T to a and forms the set {at( a, ANY), adj(ANY, ANY)}. This set is closed un­ der the backchaining operation. A similar technique is used to identify the operators relevant to achieving a given set of goals. For the goals here, the only relevant operator is m011e(a, S, S').

2.4 Using Heuristics

Since the cost-effectiveness of heuristics derived by AB­ SOLVER is generally difficult to predict, they must be evaluated empirically. ABSOLVER's performance ele­ ment inputs an initial state, a problem to solve, and optionally a heuristic. The problem is represented as a list of one or more subproblems, each consisting of a subgoal and a set of operators with which to achieve it. The IDA · search algorithm is used to solve each sub­ goal, guided by the heuristic (or breadth-first if none is given).

The heuristic is represented as an abstract problem. It is evaluated by recursively invoking the same search procedure on the abstract problem and returning the length of the optimal solution. Thus the computation of the heuristic can itself be guided by a hierarchy of successively more abstract problems.

To illustrate, consider the "X-Y Heuristic," which is derived by factoring an abstracted Cartesian representa­ tion of the Eight Puzzle into two subproblems, one for each dimension. However, instead of dropping the blank predicate to achieve factorability, the drop_precondition transformation is used to drop information about the X dimension from the subproblem for the Y dimension, and vice versa. In effect, each subproblem projects the puzzle onto one dimension. Thus a horizontal move is allowed only into the column containing the blank, and a vertical move is allowed only into the row containing the blank. X-Y is therefore more accurate than Manhattan Distance, which ignores the blank completely.

Although X-Y yields a base-level branching factor of only 1.19 for the Eight Puzzle (on a set of 18 random instances), it requires a considerable amount of search to compute. This search can be guided by Manhattan Distance. Unfortunately, even with such guidance the overall search time turns out to be about six times slower than using Manhattan Distance alone. It remains to be seen whether additional optimizations can make X­ y better than Manhattan Distance, which is the best known heuristic for Eight Puzzle.

3 Evaluating ABSOLVER

We now evaluate ABSOLVER from three perspectives: first, as an ezplanatory model that can rationally recon­ struct existing heuristics, thereby verifying admissibility by construction; next, as a generative model, helpful for suggesting new heuristics; and finally, as an automatic di!covery engine.

3.1 ABSOLVER as an Explanatory Model

An explanatory model should be evaluated by its gen­ erality and coverage. A general model applies to a wide class of domains. Within that class, a good model covers a large proportion of the phenomena to be explained. We tested ABSOLVER's generality by applying it to several puzzle domains. We tested its coverage by trying to red­ erive all published heuristics for three of them: the Eight Puszle, Towers of Hanoi, and Mutilated Checkerboard. The results are summarized in Table 3.

This evaluation simultaneously tested the model at three different levels of specificity. First, it tested the generality and coverage of the particular catalog of trans­ formations across several domains. Since we knew our initial catalog was incomplete, we were also interested in identifying useful new transformations. In fact, these problems served as our "training data" for developing the catalog in Table 1, so they should not be taken as a test of its coverage, though they do demonstrate the gen­ erality of the transformations used in multiple domains. Second, it tested the problem representation language, since some heuristics might not be derivable in that rep­ resentation. Finally, it tested the general model of ab­ straction plus optimization, which might fail to explain some heuristics.

What does it mean to rederive a heuristic? Clearly, it is not necessary to rederive specific code. On the other hand, functional equivalence alone is insufficient, since an abstraction-based heuristic computed using search may be much less efficient than the original version. We therefore compared their computational complexity.

The results can be summarized as follows. We were able to rederive functional equivalents with ABSOLVER for 6 of the 10 published heuristics, though with varying efficiency relative to the original versions.

The derived versions of # of Misplaced Tiles, # of Misplaced Disks, and Colored Squares were all compu­ tationally equivalent to the originals.

Three of the derived heuristics were less efficient than the original versions, owing to limitations in the chosen problem representations and deficiencies in the catalog of optimizing transformations. The derived Manhattan Distance was slower by O(n) (for n by n puzzles) because it uses search to compute the number of moves needed to get from row i to row i'. We have derived the closed form expression li- i'l on paper, but only by exploiting the numerical relationships implicit in the adj relation to induce a recurrence relation. Implementing this deriva­ tion in ABSOLVER would require a more sophisticated representation and an optimizing transformation capa­ ble of inducing the recurrence relation. Similarly, the derived versions of n-MaxSwap and n-Swap are slower by O(n 2 !) because they search for an ordered permuta­ tion instead of counting the number of swaps performed by an efficient sorting algorithm. A challenging direc­ tion for future work is automatically recognizing when an abstracted problem can be solved by adapting a known algorithm.

Two of the heuristics have the wrong form: Sequence Score is non-admissible, and Alternating Disks is a heuristic on moves, not states.

Euclidean Distance breaks our model in an interesting way, because it comes from adding knowledge about ge­ ometry. Our current model only generates abstractions by dropping information from the problem definition.

The Blocking Disks heuristic is defined only for states in which two of the pegs are empty. It was originally derived by analyzing a recursive algorithm for Towers of Hanoi to compute the exact number of moves required.

We see no way to derive this formula by abstracting the problem representation. However, extending AB­ SOLVER to find special-case heuristics might be worth­ while.

3.2 ABSOLVER as a Generative Model

How good is our model at suggesting new heuristics? Table 4 attempts to answer this question for several do­ mains. For each of these domains only "good" heuristics are listed; several other heuristics were derived but ap­ peared worse in terms of overall search time.

We were able to discover the first known (non-trivial) admissible heuristic for the 3z3z3 Rubik's Cube. For this problem, we started with a represention that par­ titions the Cubies into center, edge, and corner ones. Dropping the edge predicate allows the operators to be factored into those that affect corner Cubies and those that affect center Cubies.

How good is this Center-Corner heuristic? For 13 problems randomly scrambled to depth 6 or less, it reduces the branching factor from 9 (for breadth-first search) to 5:9. The heuristic is computed by solving the two subproblems. The subproblem for the six cen­ ter Cubies has three operators and is cheap to solve. The subproblem for the eight corner Cubies is equivalent to a 2z2z2 version of Rubik's Cube. Since our Prolog implementation of IDA" only expands about 10 states per second, we have not yet evaluated the Center-Corner heuristic on deep random solvable instances of the Cube.

We were also able to derive some new admissible heuristics for the Eight Puzzle. We have already de­ scribed the X-Y heuristic, which is more accurate than Manhattan Distance. Similarly, # Out of Column + #

Out of Row is more accurate than # Misplaced Tiles, and takes only twice as long to compute.

We also used the techniques reported in this paper to help demonstrate the unsolvability of a once-open lay­ out problem known as the Jagged Square Puzzle, shown in Figure 2. The task is to tile the 60-square figure us-

ing each pentomino once-or to prove that it cannot be done. When we attacked this problem, we believed it was still open. After proving it impossible, we found a published proof that relies on remarkably similar tech­ niques [Golomb, 1965].

We started with a problem representation that parti­ tions the squares into those in the interior of the Jagged Square, those bordering the outer edges, and those bor­ dering the inner "hole." (We later added "corners") . Next, we applied the count transformation to each par­ tition. Unfortunately, it turned out that the resulting admissible heuristic was not strong enough to prove the problem impossible, i.e., the abstracted initial state ap­ peared solvable. We then hand-generated every possible placement of the four most constraining pentominoes; taking symmetry into account, there were only a dozen or so. Finally, we executed exhaustive search in the ab­ stract space on each of these partial layouts to show the impossibility of completing any of them.

Table 4 also lists novel heuristics derived for some GPS domains [Ernst and Goldstein, 1982]: Fool's Disk, In­ stant Insanity, and Think-A-Dot.

One lesson of these examples is the frequent impor­ tance of clever partitioning in the initial problem rep­ resentation: the border and interior squares in Jagged Square; the corner, center, and edge Cubies in Ru­ bik's Cube; and the red and black squares in Mutilated Checkerboard. At present such partitioning is supplied as part of the initial representation.

3.3 ABSOLVER as an Automatic Discovery Engine

As an automatic discovery engine, ABSOLVER must be evaluated by the tractability of finding good heuristics in the space defined by the catalog of transformations. There is a tradeoff between tractability and coverage, since enlarging the catalog expands the space of derivable heuristics but makes it costlier to explore.

The full space defined by ABSOLVER's current cata­ log of transformations is far too huge to explore exhaus­ tively. For example, the drop transformations alone can be applied to any combination of subgoals and operator preconditions. For our nine-operator representation of the 3z3z3 Rubik's Cube, there are 126 subgoals and 312 preconditions: the number of combinations is astronom­ ical.

As a compromise between coverage and tractabil­ ity, we implemented an exhaustive generator using the coarser-grained drop_predicate as the only abstracting transformation and factor as the only optimizing trans­ formation. For the Eight Puzzle, it took this generator a few CPU seconds to test all combinations of dropped predicates. For the three-predicate, single-operator rep­ resentation, the only combinations with more than one factor yielded Manhattan Distance and # Out of Place Tiles (subject to the efficiency limitations discussed in Section 3.1). The five-predicate, two-operator Carte­ sian representation yielded more heuristics: Horizontal Distance, Vertical Distance, Manhattan Distance (their sum), analogs of all three for Distance of Blank, # Out of Column + # Out of Row, and Blank Out of Column + Blank Out of Row. For our three-predicate, nine­ operator representation of Rubik's Cube, the generator took over five hours, since our independence test for factorability currently takes time quadratic in the size of the largest transitive closure formed by the symbolic bac:kchaining step described in Section 2.3.1. Somewhat surprisingly, there is only one factorable combination­ the Center-Corner heuristic:.

To escape from the coverage-tractability tradeoff, we must use a better strategy than exhaustive generate-and­ test to find efficiently computable abstractions. We are investigating the use of means-ends analysis to identify which abstracting transformations will enable optimiza­ tions. In particular, if we can efficiently identify which applications of drop_lubgoal and drop_precondition will make it possible to apply factor, we will be able to find the factorable abstractions without generating and test­ ing all combinations of dropped goals and preconditions.

4 Relation to Previous Work

Figure 3 relates several previously reported proper­ ties that can hold between abstractions and heuristics [Nilsson, 1980, Pearl, 1984].

The relation of certain abstractions to state-space search heuristics was first suggested by Guida and So­ malvico [Guida and Somalvico, 1979] and Gaschnig [Gasc:hnig, 1979], who described how such heuristics might arise by using the depth of solutions in edge supergraphs of the original state-space search graph as lower-bounding heuristics. Such edge supergraphs naturally arise from dropping operator preconditions. Later, Valtorta (Valtorta, 1984], Pearl [Pearl, 1984], and Kibler [Kibler, 1985] each proved that abstractions such as those resulting from dropped operator preconditions would guarantee monotone (and hence admissible) heuristics. Our abstracting transformations extend the edge supergraph model of abstraction to include node­ merging.

Valtorta proved that using a dropped-precondition ab­ straction directly as a heuristic will alway· expand more total states in the two spaces than simply using breadth­ first search in the base space [Valtorta, 1984]. Pearl later pointed out that this liability might be overcome by fac­ toring the abstracted problem into independent or serial­ izable subproblems, which might be possible even when the original problem is not factorable [Pearl, 1984]. Fac­ toring reduces the total search complexity from the prod­ uct of exponentials to their sum. Though elegant, these methods were not implemented: the abstracting and op­ timizing transformations were performed by hand.

Some work has been done on automatic generation of abstractions in planning [Sacerdoti, 1974, Knoblock, 1988, Unruh et al., 1987], but not for the class of admissi­ ble heuristics addressed here. For example, ABSTRIPS used abstract solutions as skeletons for base solutions, which tends to reduce planning time but can produce sub-optimal plans. Furthermore, ABSTRIPS discards abstract solutions that cannot be refined into more con­ crete ones. In contrast, ABSOLVER uses abstractions solely to compute lower bounds and check solvability, thereby not discarding potentially valuable information from non-refinable abstract solutions. Other systems have been reported for serializing GPS subgoals (Ernst and Goldstein, 1982], but they do not guarantee the op­ timality of the solution paths.

In sum, while a few techniques have previously been reported for abstracting and simplifying state-space problems, ABSOLVER constitutes a novel attempt to automate, integrate, eztend, and evaluate these tech­ niques.

5 Conclusion

ABSOLVER appears to be the first mechanical genera­ tor of state-space heuristics guaranteed to find optimal solution paths. It achieves this admissibility property by decomposing the problem of discovering heuristics into generating abstractions and optimizing their evaluation.

ABSOLVER can be viewed at more than one level. First, its transformational model provides a unifying framework for characterizing and exploring a broad class of admissible heuristics and understanding when they are actually useful. Second, we have grounded the model by implementing a catalog of abstracting and optimizing transformations and using them to derive a number of heuristics. Third, we have demonstrated an automatic generator that uses two of these transformations to find efficiently computable heuristics.

As an explanatory model, ABSOLVER's coverage is encouraging in one sense but deficient in another. While its small catalog of abstracting transformations is ade­ quate to derive functional equivalents for many of the published heuristics we looked at in several puzzle do­ mains, its optimizing transformations are too weak to compute some of them as efficiently as the originals. We do not claim the catalog is complete, and in fact expect it to grow as we try to improve evaluation cost, derive more heuristics, and explore other domains. The few heuristics that did not match ABSOLVER's underlying model suggest interesting directions in which to extend it.

As a generative model, ABSOLVER has yielded some novel heuristics, notably the first non-trivial admissible heuristic for Rubik's Cube, and an interesting Eight Puz­ zle heuristic that is more accurate than the best known, though somewhat less cost-effective. Although all the transformations reported here are fully implemented, the techniques used in ABSOLVER are useful for generating heuristics even when applied by hand. In fact, that is how we actually discovered most of the novel heuristics, and how we proved the impossibility of a published lay­ out problem we thought was still open. Subsequent im­ plementation of the derivations served to verify their cor­ rectness and to expose the use of additional techniques. Thus the implementation is actually of secondary impor­ tance for discovering new heuristics, except to the extent that it makes the techniques easier to apply.

As an automatic discovery engine, ABSOLVER is lim­ ited by the intractability of exploring the space generated by its full catalog of transformations. Its exhaustive gen­ erator uses only one abstracting transformation and one optimizing transformation, thereby achieving tractabil­ ity at the cost of coverage. Nonetheless, it finds inter­ esting heuristics in more than one domain.

Of the many possible directions for extending AB­ SOLVER, two seem especially compelling. First, means­ ends analysis may make it possible to explore a richer space of possible heuristics automatically. Second, AB­ SOLVER's sensitivity to the initial problem representa­ tion, and the importance of clever partitioning in discov­ ering novel heuristics, suggest that a few transformations for representation-shifting might significantly enrich the space of discoverable heuristics.