... planning.¹

Interestingly, one of the most widely studied planning domains, the Blocks World, also has this property.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...²

These domains are analyzed in Section 4. Graphical examples of the rewriting process appear in Figure 30 for query planning and in Figure 21 for manufacturing process planning. The reader may want to consult those figures even if not all details can be explained at this point.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...aarts97.³

Although the space of rewritings can be explored by complete search methods, in the application domains we have analyzed the search space is very large and our experience suggests that local search is more appropriate. However, to what extent complete search methods are useful in a Planning by Rewriting framework remains an open issue. In this paper we focus on local search.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...⁴

To illustrate the basic concepts in planning, we will use examples from a simple Blocks World domain. The reader will find a ``real-world'' application of planning techniques, query planning, in Section 4.4.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...⁵

(stack ?x ?y ?z) can be read as stack the block ?x on top of block ?y from ?z.
(unstack ?x ?y) can be read as lift block ?x from the top of block ?y and put it on the Table.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... ?y)⁶

By convention, variables are preceded by a question mark symbol (?), as in ?x.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...⁷

This operator uses an idiom combining universal quantification and negated conditional effects to enforce that the attribute surface-condition of a part is single-valued.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... inequality⁸

Equality is denoted by sharing variables in the rule specification.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...⁹

The interpreted predicate possibly-adjacent makes the link expression in the antecedent of avoid-move-twice redundant. Unstack puts the block ?b1 on the table from where it is picked up by the stack operator, thus the causal link (?n1 (on ?b1 Table) ?n2) is already implied by the :operators and :constraints specification and could be removed from the rule specification.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...¹⁰

POCL planners operate by keeping track and repairing flaws found in a partial plan. Open conditions, operator threats, and resource threats are collectively called flaws [65]. AddFlaws(F,P) adds the set of flaws $F$ to the plan structure $P$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...¹¹

Figure 32 in Section 6 proposes an example of a rule with a relationally-complete antecedent using an appropriate syntax.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...¹²

The algorithm also accepts extra ordering constraints in addition to the sequence if they are available from the initial plan generator.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...¹³

To implement their algorithm it is enough to replace line 3 in Figure 17 with:
find max $k < i$ such that

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...¹⁴

In the logistics domain of AIPS98, the problems of moving packages by plane among different cities and by truck among different locations in a city are isomorphic, so we focused on only one of them to better analyze how the rewriting rules can be learned [6].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...¹⁵

In mediators, rules that address the resolution of the semantic heterogeneity are also necessary. See [5,3] for details.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.