Plan Synthesis: A Logical Perspective

1. Normal Form for Conditional Plans

• A program is in normal form if it consists of

*For some applications it is desirable to constrain the programming language to use only a de signated subset of the propositions as tests in conditionals. This requires a straightforward modification of our definition and will not be pursued here.

**Equivalently in semantic terms: that satisfy the domain constraints the ~-instantiated plan constraints. Structures also satisfy

a sequence· of zero or more atomic actions followed optionally by a conditional program, both branches of which are in normal form, followed in turn by 0 or more further atomic actions. More formally stated, a program is in normal form if it can be written as A 1 ; ··· ;~, n ~ 0, with at most one A 1 not atomic, in which case A 1 is of the form t _. B,l,~ s2 where both Bj are themselves in normal form. The null sequence is identified withJ\, and we take 1\.;v. = ~;A =II(.

We have not precluded any essential solutions by insisting on this form, since every C-program can be put into normal form by transforming the longest (length > 1) sequence of steps whose first and last steps are conditionals into a single conditional as follows:

==) (s -A; ··· ;(t -c,D), B; ··· ;(t-C,D)) and applying this transformation recursively to A, B, and the residual ··· ;(t- C,D).

2. An Algorithm

Let us suppose we are looking for a normal-form program K that satisfies one of the dynamic constraints p ~ [«]q in R. We consider the following cases corresponding to the possible forms of d. :

1. ct= a;~ or d.= ,;a for some atomic act ion a. In the former case, ot- is a solution if Q 1- p/a::J [~]q , where p/a represents the strongest provable post-condition of p and a. Analogously, in the second case, .c is a solution if Q 1- p '::> [/3]a\q, where a\q is the weakest provable precondition of a and q. We call the former case "progression" and the latter "regression."
2. 3 · .c = t -~1· 1! 2 · In this case, o< is a solution if Q 1- pi\ t ::> [,S 1 Jq and Q ~ P "' ., t ::> [~2 J q ·

We see that ( 1) defines success, (2) suggests forward and backward strategies for sequential steps, and (3) suggests a forward strategy for conditionals.

*since ";" is associative, we write sequences a;b; ··· ;c without indicating the order of association.

**warren's method [17] for introducing conditionals produces plans of an even more restricted form: the conditional must be the last action in the sequence. That is, a plan, once split, may never rejoin. This is not an essential limitation, but it introduces a somewhat greater degree of redundancy than does our form. We note in passing that Warren's view of the conditional test as an action has much in common with POL's p? action.

In addition, we observe that there are several obvious ways to limit the search. First, if p :> p/a, the forward search need not consider act ion a. (A special case of this arises when p/a =true.) Dually, if a\q q, the backward search need not consider a. (Here we have a special case when a\q = false.) These checks eliminate self-loops. We can eliminate cycling in the search space altogether if we are willing to pay the price of checking whether pi:> p/a for any Pi in the leading chain of preconditions. Likewise we can check whether a\q ~ qj for any qj in the trailing chain of postconditions. It should also be noted that if p ~ t or p:>., t, the forward conditional search involving t need not be pursued. p/a can never be false, since this would imply failure of a to terminate, contradicting our assumptions about the domain constraints Q.

These observations lead directly to the following nondeterministic algorithm for computing solutions for the single constraint p ~ [·lq: (Multiple constraints will be discussed later.)

BIGRESSION* ALGORITHM

Assume p, q are not false. Solve(p,q) = Bigress(p,q,.l\ ,t\.). Bigress(pre,post,leader,trailer): IF Q._pre::. post THEN RETURN(leader;trailer). CHOOSE: CHOOSE <a, pre/a) from LiveForward(pre): RETURN(Bigress(pre/a, post, leader;a, trailer)) CHOOSE <a, a\post) from LiveBackward(post): RETURN(Bigress(pre, a\post, leader, a;trailer)) CHOOSE t from NonTriv(pre): RETURN( leader;C;trailer ) where C = ( t -Bigress (pre II t, Bigress(prelh t, LiveForward(p): IF s F 0 post,/\,!1. ), post, J\ , 1\ ) ) where S = <a, p/a> 1 a ~a. Q ~ p :;:,p/a} THEN RETURN( S ) ELSE FAIL(). Livellackward(q): IF s F 0 where S = <a, a\q) I a Ea., Q ~ a\q ::> q} THEN RETURN( S ) ELSE FAIL(). NonTriv(p): IF s F 0 where S THEN RETURN( S ELSE FAIL().

The algorithm as presented finds solutions for a single plan constraint. However, the extension to the general case is straightforward: To ensure that all the plan constraints are satisfied, a

*"lligression" stands for "bidirectional progression and regression."

"Cartesian product" version of this algorithm must be run. A failure in ~ of the constraint components counts as failure and serves to prune that branch.

The bigression algorithta makes use of three additional auxiliary functions: "Qt- ", "/", and "\". "QI-o" is a procedure that takes as input a nonmodal formula p and decides whether p is provable from Q. If the static axioms are rich enough,* this check can be done using only nonmodal reasoning, i.e., ordinary propositional decision methods. The functions "/" (progression) and "\" (regression) are the subject of the next section.

3. Progression and Regression

Ideally, we would like p/a to compute the strongest postcondition of condition p and action a. Similarly, we would like a \q to compute the weakest precondition. [ 1, 15) In PDL the weakest precondition of p and a can be expressed simply as [a)p, which is obviously the weakest formula implying "after a, p." The strongest postcondition can be expressed using a "converse" operator that we have not described. (See [5).)

However, given the restricted form of our dynamic axioms, there will be no propositional formula provably equivalent to either of these modal formulas. On the other hand, we can effectively compute the weakest precondition ~ and strongest postcondition post for which it is provable from Q that ~ implies "after a, q" and p implies "after a, post." It is these propositional formulae that we label p/a and a\q.

The formula p/a is found by taking the conjunction of the set of formulas each of which is a disjunction of a set of qi drawn from the "right-hand side" of the dynamic axioms of Q (pi ~ [a)qi) such that the disjunction of the corresponding pi's is implied by p. Dually, a\q is found by taking the disjunction of the set of formulas, each of which is a conjunction of a set of pi drawn from the "left-hand side" of the dynamic axioms of Q (pi::> [a)qi) such that that conjunction of the corresponding qi's implies q.

Let us consider the following sample axioms: A ::>[a) (B VC) G :>[a) .,B (FI\E)::>[a) D

In this case, a\(C \I D) (A !I G) V (FI\ E). The reason for this is that (B V C) conjoined with., ll implies (CVD), so the conjunction of the corresponding left-hand sides (A 1\ G) is one disjunct of a\(C 1/ D). Likewise, the formula D alone implies (CV!J), making the corresponding left-hand side (F ~ E) the second disjunct. These two cases exhaust the possibilities for getting ( C V D).

*specifically, the static axioms must generate all the nonmodal formulae generated by all of Q. In certain pathological cases, such as when Q contains a dynamic axiom of the form p ;::, [a)false, Q would have to be extended to include extra static axioms, since p~[a)f.slse and <a>true together imply -,p--a nonmodal formula derivable only through modal reasoning.

The reason the formulas p/a and a\q defined in this way are not exactly equivalent to the strongest postcondition and the weakest precondition lies in the nature of our atomic actions. Briefly stated, in the context of prog ramming languages one typically begins with primitives whose semantics are fully characterized and focuses on characterizing the derived opera tions (sequencing, etc.) [1). For example, the weakest precondition for the assignment primitive is given by the equation: wp("x:· E", P(x)) P(E), which asserts that the weakest precondi tion for condition P and action "x gets E" is precisely P with E substituted for x.

In our case, however, the primitive actions are specified only by axioms stating one-way implica tions. Thus, unless we make assumptions of a "non-monotonic" nature, we would generally be able to consistently add axioms that "weaken" the precondition or "strengthen" the postcondition of an act ion. Since "provably weakest" is unattainable , we make do with "weakest provable." This does not affect the completeness of the search algori thm, since we are looking only for programs that provably satisfy the specifications.

C. Hierarchical Planning

The key observation to be made in extending the single-level algorithm to lliUltilevel, hieraq:hical planning is that an atomic action at level k is a plan to be solved· for at level k+l. This point of view is possible because of the way the planning problem was formalized. Specifically, an atomic action is described by a set of dynamic axioms in Q. Likewise, the desired program is described by a set of dynamic axioms in R. Since the same formal objects--namely, sets of dynamic axioms--are involved in both cases, it is natural to assume as primitive some ac t ion with given properties at level k and then t o solve for a program having those properties at level k+l.

In formal terms, a hierarchical planning problem is a tree of single-level problems. If <Vk =<<flk, ctk>, Qk, Rk ( uk) > is the problem at non leaf node k, then node k has one successor for each ak i in ~, and that successor's problem has the form <Vk+l 'Qk+l·Q'(ak i)>, where Q' denotes the subset of dynamic ax'ioms of Qk having the form p :::l [ak i )q. In other words, the domain const raints on the primitive "a" at level k become plan requirements at level k+l. A solution is a plan using_ the vocabulary of the leaf nodes that satisfies the requirements of the· root node. That is, is a solution if it solves <Vn,Qn,Rl (u 1 )>. The proposi tional vocabulary and the action vocabulary can change from level to level, provided that the domain axioms have enough inferential structure t o make the transfer from level to level meaningful.

Obvious ly, for any node k, only the successor nodes co rresponding to actions actually used in k's solution need · be solved. Furthermore, finding a solution for each of these nodes guarantees that we have an overall solution.

As with other hierarchic planners, the main benefit of levels in our approach is heuristic: The selection of intermediate vocabularies and domain axioms constitutes a choice of "planning islands." Any algorithm that tries to solve a problem by solving the nodes in the hierarchy is, in essence, searching for a plan constrained to go through the states defined by the domain constraints of the intermediate actions. The main benefit of logic here is to define a reasonable relation between the levels, namely the relation: "correctly implements."

For a fixed determination of levels and a small number of actions it would be possible to precompute solutions to the subproblems, in which case, after solving the problem at the top level, the system would act more like a compiler than a problem solver. In dynamic situations in which the lower-level actions (in effect, the "tools" for solving the problem) are changing or when few actions are ever actually used, it seems more natural to solve subproblems as they arise.

IV DISCUSSION

A. Modeling Actions: The Legacy of STRIPS

Much of the research into the control of planning has been carried out in the STRIPS paradigm [2, 6). In this approach, actions are regarded not as mappings from states to states, but rather as syntactic transformations of state descriptions to other state descriptions, where state descriptions are logical formulas. One consequence is the oft-cited advantage of not having to mention the various "frame conditions," i.e., t*he properties that are invariant under an action. Unfortunately, the need for operators to be sensitive to the syntax of state descriptions led researchers to consider only very simple state descriptions (e.g. sets of atomic propositions) and very simple transformations (e.g., add lists and deletelists).

As an example of an action that is difficult to specify with a single addlist/deletelist pair, consider the action~. described by a pair of dynamic axioms:

On(light) :>[ toggle(switch) ).,On(light)

-,On( light) :> [ toggle(switch) I On( light) Since the consequents depend conditionally on the a ntecedents, it cannot be determined in isolation whether toggle adds or deletes the wff On(light). Nonetheless, a planning system given these axioms might reason that after two toggles, the light would surely have gone on at least once. Similar remarks hold for actions with disjunctive postconditions.

These possibilities notwithstanding, many planning systems do make the assumption that the truth of a given atomic proposition in the state resulting from applying a sequence of operators is a determinate, calculable thing. Techniques that rely critically on these assumptions are sometimes difficult to adapt to less constraining as s umptions. We offer two illustrations from NOAH [ 11 J.

* However, these invariants need not be as large an obstacle to practical implementation as is commonly supposed (see [10)).

B. Nonlinear Planning: Problems with Partial Orders and Shuffles

The basic idea behind nonlinear planning i s the following . To solve a conjunctive goal G1 & G2 , find a sequence 51= a;b; ··· ;c that achieves G1 and another sequence 52 z d;e; ··· ;f that achieves G2. Represent the overall plan as a network of partially ordered actions with 51 and 52 as parallel branches. Now use the "resolve-conflicts cr i tic" to detect interference between the plans and impose additional ordering constraints upon the actions to eliminate the interference. The network encodes the subset of the possible shuffles of 51 with 52 that a re believed to achieve the overall goal G1 & G2.

For the resolve conflicts critic to filter interference correctly, it must know what is true a t each node of the network. Unfortunately, for nodes that occur after joins, what is true depends c ritically on the ultimate linearization of the pa r a llel branches. In the general case, the best tha t can be done is to represent the disjunction of the strongest ;ostconditions of the alternative linea rizations. This requires considering the alternatives, of which there are . <m:n), where m and n represent the lengths of the action sequences in the two parallel branches . Since it is easy to i ma gine cases in which resolve-conflicts critici sm would be a n expensive operation, the belief tha t using a nonlinear strategy is computationally efficient seems to be grounded in the empirical hypothesis that operators encountered in practice will permit easy detection of conflicts.

C. Hierarchical Planning: Problems with Heuristic Decompositions

The justification for partial orderings in NOAH is linked with a desire not to commit the sys tem prematurely to a particular linear order of ac t ions which, though s e emingly correct at one l evel, may expand into incorrect plans at lower l e ve l s . This possibility can arise, of course, only if the relation between levels ("Plan A achieves the same effect as Action a") is not exac t. However, such inexactness undermines the o r igina l rationale f o r hierarchical planning-­ name ly, reducing complexity by means of fac t oriza tion--since it destroys compositionality a nd r equires that we c heck complex lower-level plans f o r "unexpected" gl obal inte r a c tions. He re t oo , a n empirical hypothesis is presumably invoked, name ly, that by some suitable metric the plan come s

*Ac tually, NOAH does not represent disjunctive pos t conditions--which may explain why disjunctive goa l s a re cons idered problematical.

"close" to implementing the abstract action. (It is not immediately obvious, though, what metric could be meaningful for the space in question.)

D. Some Benefits ~ Bigression

Some of the benefits of regression were first discussed by Waldinger [ 15] and appreciated by Warren [ 16]. These benefits accrue dually by including progression, which completes the logi ca l symmetry and allows bidirectional search. As we have described them, the progression and regression operations handle arbitrary Boolean formulas, thus solving conjunct lve and disjunctive goal s as particular a pplications of a more general strategy . Goals of maintenance and prevention can be incorporated into the algorithm as well by expressing as (nonmodal) wffs the condition to be maintained (m) and the condition to be prevented (v). Since the planning algorithm actually develops a descriptive wff (d) for each state reachable during plan execution, it is straightforward to add a check to the procedures LiveForward, LiveBackward, and NonTriv eliminatini paths through states where Q 1-- d :::>., m V v · This simple approach will work in situations i n which no dynamic replanning is anticipated; goal s of maintenance and prevention involving execution monitoring, feedback, and replanning require more complex strategies. Further research should be directed at these problems a s well as at effic i e ncy issues, especially clarification of the role of heuristi cs and the compilation of deduc tive processes.

ACKNOWEDGEMENTS

I have profited considerably from discussions with Richard Waldinger, Vaughan Pratt, Kurt Konolige, Dave Wilkins, Jerry Hobbs, and Bob Hoa r e .

*For a more thoroughgoing treatment of reasoning about processes with intermediate states, see [9].