... planning.1
Interestingly, one of the
most widely studied planning domains, the Blocks World, also has this
property.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...2
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.3
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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...4
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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...5
(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)6
By convention, variables are preceded by a question mark
symbol (?), as in ?x.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...7
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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... inequality8
Equality is denoted by sharing variables in the rule
specification.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...9
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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...10
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 to the plan structure .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...11
Figure 32 in Section 6
proposes an example of a rule with a relationally-complete antecedent
using an appropriate syntax.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...12
The algorithm also accepts extra ordering constraints in
addition to the sequence if they are available from the initial plan
generator.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...13
To implement their algorithm it is enough to replace
line 3 in Figure 17 with:
find max such that
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...14
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].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...15
In mediators, rules that address the resolution of the
semantic heterogeneity are also necessary. See
[5,3] for details.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.