The Downward Refinement Property

1 Introduction

Plan formation is concerned with finding sequences of operators that bring about certain goal states from cer­ tain initial states. This task is particularly difficult be­ cause of the exponential nature of the search spaces in­ volved. Abstraction [1, 2, 3, 4] is a widely adopted strategy for lessening this computational burden. . .

It is well-known that if one has a good abstract10n hi­ erarchy, then search can be made exponentially more effi­ cient. Korf [5] has shown that by using macro-operators (a form of abstraction), the average time. comp~exity of planning search can drop from exponent1al to hnear. Similar speed-up results have been reported by Knoblock [2] for ABSTRIPs-style abstraction. However, close exam­ ination reveals that the downward refinement property (DRP) is a major assumption underlying both analyses. This property simply states that if a non-abstract, con­ crete level solution to the planning problem exists, then any abstract solution can be refined to a concrete solu­ tion without backtracking across abstraction levels. That

·This work is supported by grants from the Natural Science and Engineering Council of Canada. The au­ thors' e-mail addresses are fbacchusCilogos .waterloo. ca and qyangCilogos .waterloo. ca.

The Downward Refinement Property

Fahiem Bacchus and Qiang Yang·

Depaxtment of Computer Science University of Waterloo Waterloo, Ontaxio, Canada N2L-3Gl

is once a solution is found at the abstract level it need n~ver be reconsidered, just refined.

Furthermore, experiments with Abstrips (1] and Abtweak (4] have shown that abstraction only incre~s search efficiency in hierarchies that are close to havmg the DRP, i.e., in hierarchies where most abstract solu­ tions can be refined. In hierarchies where this is not the case, using abstraction can in fact decrease the effi­ ciency of the planner. Hence, it is important to charac­ terize those hierarchies that have the DRP. Such a char­ acterization could be to used to check whether a given abstraction hierarchy has the DRP. In the presence of the DRP a modified search strategy is applicable that runs exponentially faster without giving up complete­ ness. A characterization could also be used to generate an abstraction hierarchy for a given domain guaranteed to have the DRP.

In this paper, we will provide a semantics for ABSTRIPs-style abstraction. We will then use this ~e­ mantics to give a definition of the DRP. After examm­ ing the effect of the DRP on search efficiency, we will give a semantic condition that is sufficient to ensure the DRP. This semantic condition yields both a better un­ derstanding of the nature of the DRP and collection of syntactic conditions that are sufficient for guaranteeing its presence. To be useful, we have focused on conditions that can be tested in polynomial time, allowing a speci­ fication of a domain hierarchy to be checked quickly for the DRP.

2 The Planning Representation

We will focus on planning problems that can be de­ scribed with a quantifier-free language, £, consisting of a collection of predicates, of various arities; constants; and variables, used to describe parameterized operators. Such a language can be given a semantics by a traditional first-order model, with a domain of discourse, relations over the domain, and an interpretation function map­ ping the symbols of the language to semantic entities. The result of such a model will be the assignment of a truth-value to every formula of the language. Abstract­ ing away from the models we can focus on their end prod­ uct: the truth-value assignments. Treating these assign­ ments as functions from the formulas to TRUE/FALSE, we can view distinct truth-value functions as alternate realities or possible worlds as described by C. We will call these distinct truth-value functions possible worlds, and will use W to denote the set of all possible worlds. We say that a possible world w satisfies a formula A E C (set of formulas S) if it assigns the truth-value TRUE to A (to every member of S), and we will use w I= A to denote this.

Now consider a collection of formulas of C, S. If this collection is consistent (i.e., if there is at least one possi­ ble world that satisfies S), then in general there will be many possible worlds which satisfy S. We will use the notation Es to refer to the set of all worlds w E W that satisfy S . 1 If we add new formulas to S then Es will shrink in size, and if we remove formulas from S, Es will increase. 2 FUrthermore, it can be the case that a syntactically distinct set of formulas T will be such that ET = Es (in the case where T is logically equivalent to S).

State Descriptions. In planning, C is used to write state descriptions: collections of formulas that are par­ tial descriptions of the state of the world. We restrict our attention to planning problems where the state de­ scriptions are finite, consistent collections of ground lit­ erals (a typical situation for STRIPS-style planners). By the above, each such state description, S, corresponds semantically to a set of possible worlds Es. FUrther­ more, because of our restriction to literals we have that Es1 = Es2 if and only if S1 = S2. 3 This follows from the fact that for each set of ground literals there exists a possible world that satisfies those literals and no other literals.

Operators. In addition to state descriptions, planning systems contain operators that, in the case of STRIPs­ style planners, are partial functions between state de­ scriptions. A STRIPs-style operator a is defined by three sets of literals, its preconditions, Pre(a), its add list, Add(a), and its delete list, Del(a). Applying an oper­ ator a to a state description S results in a new state description a(S), which is obtained by removing from S all the literals in Del(a), and then adding to S the lit­ erals in Add(a). That is, a(S) = (S\Del(a)) U Add(a), where '\' is the set difference operator.

Semantically, operators correspond to partial func­ tions between sets of possible worlds. More precisely, consider the power set of W. A subset of this power set is the set of describable sets of worlds, 'DW. This collec­ tion is defined by the condition that for each E E VW there exists a legal state description S (finite collection of literals by the above definition) such that E = Es. 4

1 Hence, l:s satisfies "All I know is S" in the sense of Levesque [6].

2 These notions mirror the possible worlds notion of knowl­ edge, where more knowledge corresponds to a. sma.ller set of accessible worlds (7].

3 This would not be true if we allow arbitrary formulas in our state descriptions. For example, {P(a), P(a) --+ Q(a)} a.nd {P(a),Q(a)} are distinct sets offormula.s but they have identical sets of satisfying worlds.

'Not every set of possible worlds is definable by a. finite collection of literals. For example, a. set consisting of a. sin-

FUrthermore, as we noted above, the set of literals S is unique. Thus, an operator a corresponds semantically to a partial function & from 'DW to 'DW, such that:

1. E E VW is in the domain of & if and only if E ~ EPre(a)·
2. &(E) = Ea(S)· where S is the unique state descrip­ tion corresponding to E. 5

In general, a planning system will contain operator templates instead of operators. These templates contain variables which specify parameterized versions of the ac­ tual operators. The operators themselves are generated by instantiating the variables in the template. We will often refer to these operator templates as if they were ac­ tual operators. In these cases we are implicitly referring to all of the template's instantiations.

Planning Problems and Plans A plan II is a se­ quence of operators 01, ... , On. A planning problem is a pair of state descriptions (I, G), where I is the initial state, and G is the goal state. If we apply the plan II to the initial state I the operators in II will define a sequence of state descriptions So, ... , Sn resulting from the application of the operators: So ~ S1 ~ ... ~ Sn, where So = I. A plan II is a solution a planning prob­ lem (I, G), or is correct with respect to (I, G), if the sequence of state descriptions generated by applying II to I satisfies two conditions: (1) Pre( a,)~ S,_1 , and (2) G ~ Sn. That is, the plan is correct if the preconditions of each operator are satisfied in the state to which it is applied, and the final state satisfies the goal G.

Semantically, a planning problem corresponds to a pair of sets from 'DW, (EI, Ea). A correct plan II for (I, G) corresponds to a semantic solution ft consisting of a sequence of functions &1 , ... , &n that traverse through VW such that E1 is in the domain of &1, each interme­ diate set of possible worlds, Es,_ 1 , is in the domain of the function next applied, &,, and the final set of pos­ sible worlds Es" is a subset of Ea. It is not difficult to see that every syntactic solution has a corresponding semantic solution and vice versa.

3 Abstraction

The type of abstraction we consider here is of the ABSTRIPs-style, where abstract operators are generated by eliminating preconditions. This type of abstraction has been widely used in planning research [1, 4, 9, 10]. Every literal L in the language C is assigned one of a finite number of integer criticality values denoted by crit(L). The number of levels of abstraction is equal to the number of distinct criticality values. In particular, let there be k+1 different criticality values correspond­ ing to the integers {0,1, ... ,k}, where the highest level of abstraction is k and level 0 corresponds to the concrete level where no abstraction occurs.

gle world might require a.n infinite number of literals in its definition.

5 These semantics differ in important ways from the se­ mantics for STRIPS provided by Lifschitz [8]. Future work will explore these semantics in more detail, a.nd will treat the more general ca.se where the restriction to literals is removed.

Abstract Operators and Plans Given these ab­ straction levels we can define an abstraction operator Abs which maps a state description S to its i-th level abstrac­ tion Abs(i, S), where 0 $ i $ k. This abstract state is de­ fined by removing from S all literals with criticality value less than i. We can extend Abs so that it can be applied to an operator a to yield an abstract operator Abs(i, a). The abstract operator has the same add and delete lists as a but it has a abstracted precondition list. That is, Add(Abs(i, a)) = Add( a) and Dei(Abs(i, a)) = Del(a) but Pre(Abs(i, a)) = Abs(i, Pre( a)). Extending Abs fur­ ther we can apply it to plans. If II is a plan, then Abs(i, II) is an i-th level abstract plan where every opera­ tor a E II has been replaced by its i-th level abstraction Abs(i, a). Note that the ordering of the operators has not been disturbed.

Finally, say that an i-th level abstract plan Abs(i, II) is a i-th level abstract solution to the planning problem (I, G) if it is correct with respect to the problem with an abstracted goal. That is, if Abs(i, II) is a solution to (I, Abs(i, G)}. A 0-th level solution is called a concrete solution: it involves no abstractions.

It should be noted that as a consequence of our no­ tation Abs(O, a) = a, Abs(O, S) = S, and Abs(i, S) ~ Abs(i -1, S). Further, if II is correct with respect (I, G) then Abs(i, II) will be a solution to (I, Abs(i, G)}, i.e., an i-level abstract sol)ltion. However, if Abs(i, II) is an abstract solution, II will probably not be a solution as some of its operators might have unsatisfied lower level preconditions.

Semantically, this style of abstraction has an easy de­ scription. The abstraction of a state description will correspond to a larger set of possible worlds, i.e., 'Es ~ SAbs(i,S)· i > 0. The semantic function corresponding to the abstract operator has the same definition as the con­ crete level function, it simply has a (potentially) larger domain. In particular it now includes all 'E E VW such that 'E ~ 'EAbs(i,Pre(a))· The semantic function denoting Abs(i, a) is Abs(i, &). Similarly, if Sis the set of literals that defines 'E E 'DW, then Abs(i, 'E) is simply 'EAbs(i,S)·

Since abstraction preserves the property that the state descriptions are collections of literals, we continue to have a one-to-one correspondence between abstract so­ lutions (plans) and sequences of semantic function ap­ plications, where the semantic functions now correspond to abstract operators.

To simplify our subsequent discussion, we further re­ strict our attention to a special case where criticalities are assigned to predicates only. That is, an atomic for­ mula and its negation always have the same criticality value.

4 The Downward Refinement Property

Let us fix an arbitrary planning problem (I, G). All of our subsequent discussion will be about plans, at vari­ ous levels of abstraction, that are intended as solutions to this fixed problem. For simplicity, we will augment ev­ ery such plan with special initial and terminal operators. The initial operator ao, has no preconditions and has I as its add list. The terminal operator an+l has G as its preconditions and an empty add list. Both have empty delete lists. Semantically, &o is a function whose domain is all of 'DW and whose range is 'Er; &n+l is an identity function whose domain is {'EI'E ~ 'E0 }. Hence, II will have the form ~ So ... Sn °~ 1 Sn+lt where So = I and Sn = Sn+l · The advantage of this convention is that all of the states in the sequence of states defined by the non-augmented II are sandwiched by a pair of operators in the augmented II. Note also that ao is unaffected by abstraction, as it has no preconditions, but an+l is affected, as it has the goal as its preconditions and the goal is altered by abstraction.

We can now give a semantic definition of the DRP. Let fi be a semantic solution to a planning problem (Ih, 'Ea}. Using the convention of augmented plans, this solution is a sequence of function applications with a corresponding sequence of semantic states: ~ 'Es 0 ~ Q &n+l ... ~ 'Es" 1-+ , where 'Es 0 = 'Er, 'Es" ~ 'Ea, and each 'Es, E Domain(&i+t).

Forward Justification A plan may contain extrane­ ous operators. Justification is a notion that characterizes some of the redundant operators in ft; i.e., operators that can be removed without affecting its correctness. In particular, in the version of justification we define, an operator is called justified in fi if it is the last opera­ tor in the sequence to guarantee that a particular literal is satisfied before it is required as a precondition for a subsequent operator or in the goal state.

Justification plays an important role in determining what is a "good" refinement of an abstract plan.

Definition 1 (Forward Justified Plans) Let L be a lit­ eral. We say that fi is correct with respect to L, if and only if, whenever Domain(&,) ~ 'EL, then 'Ei-1 ~ 'EL· That is, correctness with respect to L ensures that when­ ever L is required as a precondition, it is supplied.

The first operator in the plan &1 is forward justified with respect to L if and only if upon removing it from ft, fi is no longer correct with respect to L.

Inductively, let Q, be the set of operators in fi that precede&, and that are not forward justified with respect to L. Then &, is forward justified with respect to L if and only if upon removing &, and all of the operators in Q, from ft, fi is no longer correct with respect to L.

Now, we can define fi to be fon.oard justified if and only if for every operator &, in fi there is some literal L such that &, is forward justified with respect to L. ·

This definition of forward justification is equivalent to a syntactic definition given in [11]. It is not, perhaps, the most natural definition of non-redundant plans from a semantic point of view, and we have examined anum­ ber of alternatives. However, for the purposes of this particular paper our definition has the advantage that it corresponds with concepts previously defined in [11].

If a plan fi is not forward justified, then it can be con­ verted to a forward justified plan by simply removing the non-justified operators. Furthermore, it is not difficult to demonstrate that if fi is a correct plan (with respect to our fixed planning problem) then its forward justified version will also be correct.

Monotonic Refinement The idea behind monotonic refinement is that it defines a "good" refinement of an abstract plan. It captures the intuition that when an abstract plan at level i is refined to level i-1 we want to preserve as much of the work done at the abstract level as is possible. That is, we would not be gaining much advantage from abstraction if we continually replanned achievements of the higher level at the lower level. One way such an undesirable effect could occur is to refine the abstract plan by reversing all of the high-leyel operators and then plan at the lower level from scratch. Restricting the legal refinements to be monotonic guarantees that such wasteful behavior will not occur.

Definition 2 (Monotonic Refinement) Let fi1 and fi2 be forward justified abstract solutions, with fi1 being an i-th level solution and fh an i-1-th level solution, 0 < i < k.

We ~y that fi2 is a monotonic refinement of fi1, if when we forward justify Abs(i, ll2) we obtain fi1. ·

Note that a monotonic refinement must be a correct plan, i.e., a solution. When we refine an abstract plan we push the operators in that plan to a lower level of ab­ straction, generating additional preconditions for those operators. Monotonic refinement essentially means that when we add new operators to refine the plan, i.e., to make it correct again, they are added solely to achieve these new preconditions or lower level goal conditions, not to achieve previously satisfied conditions. Hence, when we drop the new conditions again, by abstraction, all of the operators we added during refinement will be­ come redundant. Thus, rejustifying the plan will yield the original abstract plan.

Our definition of monotonic refinement is the seman­ tic version of a syntactic definition given in [11]. Hence, by results from that work it can be shown that in ev­ ery ABSTRIPs-type abstraction hierarchy, completeness is preserved even when search is restricted by considering only monotonic refinements of abstract solutions [4].

The Downward Refinement Property

Definition 3 (DRP) An abstraction hierarchy has the downward refinement property if and only if for every forward justified i-th level abstract solution fi, there is a monotonic refinement of fiat level i-1, for 0 < i :5 k.

· In other words, a hierarchy has the D RP if every so­ lution at an abstract level can be monotonically refined to a solution at the next lower level of abstraction.

Example 1 Consider the Towers of Hanoi domain with 3 pegs, Peg1, Peg2, Peg3 and 2 disks Big, Small. Us­ ing predicates OnBig(x) and OnSmall(x), where x is a peg, we can represent the location of the two disks. The initial state is {OnBig(Peg1), OnSmall(Peg1)} and the goal state { OnBig(Peg3), OnSmall(Peg3)}. We can define two operators MoveBig(x,y) which moves the big disk from peg x to y, and MoveSmall(x,y) which similarly moves the small disk. We have that Pre(MoveSmall(x,y)) is {IsPeg(x), IsPeg(y), OnSmall(x)}; Add(MoveSmaJJ(x,y)) is {OnSmall(y)};

and Dei(MoveSmall(x, y)) is { OnSmall(x)}. For the other operator we have Pre(MoveBig(x,y)) is {IsPeg(x), IsPeg(y), -,QnSmall(y), -,QnSmall(x), OnBig(x)}; Add(MoveBig(x,y)) is { OnBig(y)}; and Dei(MoveBig(x,y)) is { OnBig(x)}.

Predicates that are not modifiable by any action, like Ispeg, act as constraints at all levels of abstraction. For example, the Ispeg preconditions insure that the param­ eters can only refer to pegs regardless of the level of abstraction. Hence, we always place these ''type" predi­ cates at the highest level of abstraction, i.e., level k. 6

There are two ways to construct an abstraction hi­ erarchy. We can put OnBig on the abstract level and OnSmall on the concrete level, or we can assign the crit­ icalities the other way around. As we will demonstrate later, the first choice produces a hierarchy that has the DRP, while the second choice produces one that does not.

5 Effects on Search Efficiency

The main reason for being concerned with the DRP is its profound effect on search efficiency.

In planning, it is reasonable to require that complete­ ness is preserved when an one-level planning system is extended to a multiple-level system. Hence, if a non­ abstract solution to a problem exists, the abstract plan­ ner should also be able to find a concrete solution.

To preserve the completeness of abstract planning, a search method that is complete across abstraction levels has to be adopted [4]. Typically, this means that one cannot abandon alternate abstract paths in the search tree when a solution is found at an abstract level. In­ stead, all paths have to be kept in the open list to be explored later. This can greatly hamper the efficiency of search.

On the other hand, one can do considerably better in hierarchies that satisfy the downward refinement prop­ erty. At any level of abstraction, search for alternate abstract plans can be terminated once a single correct plan has been found. In other words, search never back­ tracks to a previously explored abstract level. The DRP guarantees that any abstract solution can be refined to a concrete level one. Thus, if there is a concrete level so­ lution, search in this manner will find it without having to considering alternate abstract plans .

Let b be the average branching factor of the search, and d be the length of an optimal solution. Then breadth-first search without abstraction will take on av­ erage O(bd). On the other hand, say we have k levels of abstraction and assume that the branching factor is constant and equal to b in each abstract level. Further assume that at each level of refinement approximately k/d new operators are inserted. 7 Then, if the DRP is not satisfied and we assume that there is only a 50% chance that an abstract solution can be refined to a so­ lution at the next lowest level, it can be shown that the average case complexity remains O(bd). With the DRP, however, it can be shown that the average case com­ plexity becomes O(k x b(d/k)). That is, the search is exponentially, in k, more efficient.

6 In actuality, since they are not changed by any action, type predicates do not play a role in determining the DSP.

7 These assumptions are similar to those made in [12].

The downward refinement property has been imple­ mented as an option in the ABTWEAK planner [4]. And experiments done in Towers of Hanoi domain with three disks have shown that there can be as much as a 10 fold improvement in search time and space when using the DRP. This often makes the difference between termina­ tion and non-termination.

6 Semantic Conditions for the DRP

Given an abstraction hierarchy, one would like to tell whether it has the DRP. Alternatively, from a domain specification one may want to generate a hierarchy with the DRP guaranteed. We will now provide a set of condi­ tions sufficient to guarantee that the DRP holds. This is done by first providing a semantic condition, and then, in the next section, we will consider various syntactic realizations of this condition.

First we provide a sufficient condition for monotonic refinement.

Lemma 1 Let Ih and Ih be forward justified abstract solutions, with fi1 being an i-th level solution and fi2 an i-1-th level solution. fi2 is a monotonic refinement of ll1 if the following two oonditions hold.

1. fi1 is a subsequence of Abs(i, ll2).
2. Let &1 and &2 be any pair of adjacent operators in fi1, and let E be the semantic state between these two operators in fi1. Now by condition (1) there are two corresponding operators &1 and &2 in fi2 that are the i-1level refined versions of &1 and &2. Let E' be any semantic state in fi2 lying between &1 and &2. The second condition is then stated as the requirement that E' ~ Abs(i, E). ·

Now we can give a condition for the downward refine­ ment property.

Theorem 1 Let fi1 be any forward justified i-th level abstract solution to any planning problem that has a concrete solution. Let &1 and &2 be any pair of adjacent operators in fi1, and let E be the semantic state between these two operators in ft1. Let &1 and &2 denote the i-1level refined versions of &1 and &2. Suppose that for every semantic state E1 such that E1 E Range( &1) and E1 ~ Abs(i, E), there exists a state E2, such that

1. E2 ~ Abs(i, E), and E2 E Domain(&;), and
2. a solution ft2 consisting of i-1level operators exists for the problem (E1, E2}, such that for every state E' in ll2, E' ~ Abs(i, E).

Then the D RP is satisfied by the hierarchy. ·

Intuitively, when we refine an abstract solution it may no longer be a solution because of newly introduced and as yet unsatisfied low level preconditions. Hence, look­ ing at the situation between two adjacent operators in the abstract solution we see that the semantic state that is the result of the first operator may no longer be in the domain of the second operator, because of unsatis­ fied low level preconditions. Our DRP condition states that the hierarchy has the property that a sequence of new operators can be found that will reconnect the two operators. Furthermore, this sequence has the property that it does not affect any higher level conditions; i.e., at the i-th level nothing is changed.

7 Syntactic Checks for The DRP

In this section, we present some sufficient syntactic con­ ditions for the DRP. These conditions are presented in order of increasing sophistication, and range of applica­ bility. Each of these conditions is a syntactic realization of Theorem 1.

Complete Independence We start by considering the most trivial case for the DRP. Suppose that the k+1 criticality levels decompose the operators into k+ 1 dis­ joint subsets, Oo, ... , O~c, so that all of the literals in the precondition, add and delete lists of each operator in oi have the same criticality value, i. This condition, which we call complete independence insures that no operator used to achieve a condition in an i-th level solution will have any effect on any othet levels, and furthermore it will not require any preconditions from other levels ei­ ther.

It is not hard to see that complete independence en­ sures the DRP. On the semantic level, the k+1 abstrac­ tion levels define k+ 1 independent subproblems. Any concatenation of the solution paths at two adjacent lev­ els of abstraction returns a monotonic refinement of the abstract solution. Thus, we have

Theorem 2 Complete independence is sufficient to guarantee the D RP.

Example 2 Consider again the Tower of Hanoi do­ main. Assume that there are two copies of the 2-disk version of the problem. Given the restriction that no disk for one problem is allowed to be moved to a peg for the other problem, a complete-independence hierarchy can be trivially built by putting one copy of the problem on the abstract level, and the other one on the concrete level.

Complete low-level connectivity The second con­ dition we can place on the preconditions is more useful than complete independence.

Definition 4 (Complete Low-Level Connectivity) Let S1 and S2 be any states such that Abs(i, SI) = Abs(i, S2). That is, S1 and S2 only differ with respect to literals at criticality levels less than i. Complete low-level connec­ tivity is satisfied if for any two such states at any level of abstraction i, there is an i-1 level solution, n to the planning problem (S1, S2} such that no operators in ll add or delete a literal with criticality higher than level i-1.

Intuitively, this condition states that we can always achieve lower level preconditions without violating the higher level effects. According to the condition, every pair of states s1 and s2 are connected by a path, pro­ vided that Abs(i, S1) = Abs(i, S2). Furthermore, the condition requires that no operators on this path affect a higher level literal. This is equivalent to saying that the path never travels out of a state defined by higher level literals. Thus, the conditions of Theorem 1 are satisfied. Hence, we have the following theorem:

Theorem 3 Complete low-level connectivity is suffi­ cient to guarantee the DRP.

Example 3 Consider again the 2-disk Tower of Hanoi domain. Construct an abstraction hierarchy by placing the predicate OnBig on the abstract level, and OnSmall on the concrete level. If we fix the position of the big disk we can freely move the small disk from any peg to another. The hierarchy satisfies the complete low­ level connectivity condition. Now consider the opposite hierarchy where the predicate OnSmall is placed on the abstract level, while OnBig is on the concrete level. This hierarchy does not satisfy the complete low-level connec­ tivity restriction, since whether or not the big disk can be moved to another peg depends on where the small disk is located. In this case it is also possible to show that the hierarchy does not have the DRP. For example, there is no monotonic refinement of the abstract plan MoveSmall(Peg1, Peg3).

Unfortunately the complete connectivity condition is difficult to check syntactically. However, special cases can be constructed which can be checked. We give one example.

Definition 5 (Checkable Low-Level Connectivity) Complete low-level connectivity holds if for all levels i we have the following:

For any pair of literals £1 and £2, such that crit(£1) = crit(L2 ) = i-1, there exists o: with Pre(o:) = {LI}, Abs(i-1,Add(o:)) = {£2}, and Abs(i-1, Del(o:)) = 0.

Necessary Connectivity The third condition we can place on the preconditions is the most general. The pre­ vious connectivity condition requires th~t all low level states be connected. This, however, is too restrictive. All that is actually required is low level connectivity be­ tween pairs of states that could be generated during the refinement of a higher level plan. We call this condition necessary connectivity.

In particular we have:

Definition 6 (Necessary Connectivity) Let 0>, be the set of operators whose add and delete lists contain at least one literal with criticality value greater than or equal to i. The condition of necessary connectivity is satisfied if for every level of abstraction i we have the following.

Let o:1 and o:2 be operators from 0;:::1 such that

1. Abs(i, o:1(Pre(o:1))) U Abs(i, Pre(o:2)) does not con­ tain both a literal and its negation, where o:1 (Pre( o:I)) is the application of o:1 to its own pre­ conditions, and
2. Abs(i-1, Pre(o:2)) =F 0.

By these restrictions o:1 and o:2 are operators that could appear in sequence in an i-th level plan, i.e., the weakest postcondition state of 0:1 does not contradict the precon­ ditions of 0:2 at level i; and 0:2 depends on preconditions at level i-1 so that there is the possibility of a problem when refining to this level. For every such pair o:1 and o:2 there must exist an operator {3 such that:

1. {3 does not add or delete a literal with criticality higher than i -1,
2. Abs( i-1, Pre({3)) ~ o:1 (Pre( o:I) ), i.e., the precondi­ tions of {3 at abstraction level i-1 are satisfied in weakest the postcondition state of o:1, and
3. Abs(i-1, Pre(o:2)) ~ ,B(Pre(,B)); i.e., operator ,8 achieves the i-1 preconditions of o:2.

Intuitively, this condition is saying the following: for every pair of operators that might be sequenced in a plan at level i, there exists an operator ,8 whose preconditions at abstraction level i-1 are satisfied in any state that results from applying o:1, and that be used to achieve the i-1-th level preconditions of o:2. Moreover, the operator {3 does not change any literal whose criticality value is greater than i-1. Therefore, on the semantic level, the conditions of Theorem 1 are satisfied. Thus, we have the following:

Theorem 4 Necessary connectivity are sufficient to guarantee the D RP.

Example 4 Consider the following extended Tower of Hanoi domain with two disks, where there is an addi­ tional peg, Peg4 that is completely disconnected from the other three pegs. That is, although initially a disk can be placed on Peg4, no disk can be moved to or away from it.

If we place OnBig at the abstract level and OnSmall at the concrete level, then the extended Tower of Hanoi domain satisfies the necessary connectivity condition. However, since Peg4 is disconnected from the rest of the pegs, the concrete-level states are not completely con­ nected. Therefore, the hierarchy does not satisfy the complete low-level connectivity condition.

Example 5 Consider the robot planning domain de­ scribed by Sacerdoti [1]. A robot can travel between several rooms, where each pair of rooms is connected by one or more doors. A door can be either opened or closed by the robot. In addition, a number of boxes also exist, which can be either pushed around by the robot. To be more complex, we can also allow the robot to carry a box from one location to another. To carry a box, the robot has to first pick it up.

The domain is described by a number of predicates (see [1] for a complete description). An abstraction hi­ erarchy can be built by assigning criticality values to the predicates in the following way. The highest level of abstraction consists of all type-preconditions, such as Connects, which asserts that a door connects two ad­ jacent rooms. The next level down are predicates In­ room, At and Nextto. Further down are predicates that describe the status of the door, Status(dx,Open) or Sta­ tus(dx,Closed). The lowest level are the predicates Hold­ ing and Handempty.

Suppose that all the goals are described by predicates Inroom and/or Nextto. Then the above hierarchy satisfies the DRP. In particular, the hierarchy satisfies the complete low-level connectivity condition. For example, the robot can either close or open a door once it is next to the door, without changing any location predicates. Similarly, the robot can pick up or put down a box with­ out changing any door status or location predicates.

Example 6 Consider a problem of inter-city traveling by an agent. Assume that the agent can travel between cities by bus, train, or plane. Also assume that within each city, the agent can travel between a number of key locations by means of public transportation. Finally, the agent can travel to particular addresses in the local vicinity of each key location by walking. An abstraction hierarchy for this problem domain can be built by placing city-level locations at the highest level, the key locations at the next level, and the addresses at the concrete level. This hierarchy satisfies the DRP: once the agent is in a particular city he will never have to leave the city to travel between key locations in the city, and once he is at the nearest key location he never travel to another key location to travel between local addresses.

8 Conclusions and Future Work

In this paper, we have formalized the downward refine­ ment property for ABSTRIPs-type of abstraction hierar­ chies. The DRP guarantees completeness of planning even when search refrains from backtrack across ab­ straction levels. Our analysis shows that an exponential amount of savings in search can be achieved. We have presented a general semantic condition for guaranteeing the DRP, and have derived a number of syntactic con­ ditions from it. Although we lack the space it can be demonstrated that these conditions can be checked in polynomial time. Another topic we have not addressed is the use of our syntactic checks in the automatic gen­ eration of abstraction hierarchies that are guaranteed to have the DRP. It is possible to specify an algorithm that accomplishes this task.

This 'work is a step towards understanding abstract problem-solving in general. A number of extensions will be made in future work. One such extension is to design a richer set of conditions that allows for a broader range of application. Another is to explore the use of statistical information in the verification and generation of abstrac­ tion hierarchies. As stated above, all of our conditions are sufficient for guaranteeing the DRP. In practice, it may be the case that a large portion of a domain satis­ fies the property, but not all of it. This might cause the statistical phenomena that most, but not all, abstract solutions can be monotonically refined. We intend to explore the ramifications of this type of behavior. For example, if we have additional statistical information, then we may be able to make inferences as to how close the hierarchy is to having the DRP and the effect this would have on search efficiency.

Acknowledgements Thanks to Craig Knoblock and Josh Tenenberg for helpful comments.