3.1.1 Plan-Rewriting Rules: Syntax and Semantics

First, we introduce the rule syntax and semantics through some examples. Then, we provide a formal description. A plan-rewriting rule has three components: (1) the antecedent (:if field) specifies a subplan to be matched; (2) the :replace field identifies the subplan that is going to be removed, a subset of steps and links of the antecedent; (3) the :with field specifies the replacement subplan. Figure 6 shows two rewriting rules for the Blocks World domain introduced in Figure 2. Intuitively, the rule avoid-move-twice says that, whenever possible, it is better to stack a block on top of another directly, rather than first moving it to the table. This situation occurs in plans generated by the simple algorithm that first puts all blocks on the table and then build the desired towers, such as the plan in Figure 4. The rule avoid-undo says that the actions of moving a block to the table and back to its original position cancel each other and both could be removed from a plan.

Figure 6: Blocks World Rewriting Rules

(define-rule :name avoid-move-twice
 :if (:operators ((?n1 (unstack ?b1 ?b2))
                  (?n2 (stack ?b1 ?b3 Table)))
      :links (?n1 (on ?b1 Table) ?n2) 
      :constraints ((possibly-adjacent ?n1 ?n2)
                    (:neq ?b2 ?b3)))
 :replace (:operators (?n1 ?n2))
 :with (:operators (?n3 (stack ?b1 ?b3 ?b2))))

(define-rule :name avoid-undo
 :if (:operators 
       ((?n1 (unstack ?b1 ?b2))
        (?n2 (stack ?b1 ?b2 Table)))
      :constraints
       ((possibly-adjacent ?n1 ?n2))
 :replace (:operators (?n1 ?n2))
 :with NIL))

A rule for the manufacturing domain of [55] is shown in Figure 7. This domain and additional rewriting rules are described in detail in Section 4.1. The rule states that if a plan includes two consecutive punching operations in order to make holes in two different objects, but another machine, a drill-press, is also available, the plan quality may be improved by replacing one of the punch operations with the drill-press. In this domain the plan quality is the (parallel) time to manufacture all parts. This rule helps to parallelize the plan and thus improve the plan quality.

**Figure 7:** Manufacturing Process Planning Rewriting Rule
$\begin{figure}\hrule\begin{verbatim}(define-rule :name punch-by-drill-press :... ... (?n3 (drill-press ?o1 ?width1 ?orientation1))))\end{verbatim}\hrule\end{figure}$

The plan-rewriting rule syntax is described by the BNF specification given in Figure 8. This BNF generates rules that follow the template shown in Figure 9. Next, we describe the semantics of the three components of a rule (:if, :replace, and :with fields) in detail.

**Figure 8:** BNF for the Rewriting Rules
$\begin{figure}\hrule\begin{verbatim}<rule> ::= (define-rule :name <name> :if... ...red-var> = $\emptyset$, \{\} = optional, \vert = alternative} \hrule\end{figure}$

**Figure 9:** Rewriting Rule Template
$\begin{figure}\hrule\begin{verbatim}(define-rule :name <rule-name> :if (:oper... ...ip> = interpreted predicate, \vert = alternative\end{verbatim}\hrule\end{figure}$

The antecedent, the :if field, specifies a subplan to be matched against the current plan. The graph structure of the subplan is defined in the :operators and :links fields. The :operators field specifies the nodes (operators) of the graph and the :links field specifies the edges (causal and ordering links). Finally, the :constraints field specifies a set of constraints that the operators and links must satisfy.

The :operators field consists of a list of node variable and node predicate pairs. The step number of those steps in the plan that match the given node predicate would be correspondingly bound to the node variable. The node predicate can be interpreted in two ways: as the step action, or as a resource used by the step. For example, the node specification (?n2 (stack ?b1 ?b3 Table)) in the antecedent of avoid-move-twice in Figure 6 shows a node predicate that denotes a step action. This node specification will collect tuples, composed of step number ?n2 and blocks ?b1 and ?b3, obtained by matching steps whose action is a stack of a block ?b1 that is on the Table and it is moved on top of another block ?b3. This node specification applied to the plan in Figure 4 would result in three matches: (1 C D), (2 B C), and (3 A B), for the variables (?n2 ?b1 ?b3) respectively. If the optional keyword :resource is present, the node predicate is interpreted as one of the resources used by a plan step, as opposed to describing a step action. An example of a rule that matches against the resources of an operator is given in Figure 10, where the node specification (?n1 (machine ?x) :resource) will match all steps that use a resource of type machine and collect pairs of step number ?n1 and machine object ?x.

**Figure 10:** Resource-Swap Rewriting Rule
$\begin{figure}\hrule\begin{verbatim}(define-rule :name resource-swap :if (:op... ...ce (:links (?n1 ?n2)) :with (:links (?n2 ?n1)))\end{verbatim}\hrule\end{figure}$

The :links field consists of a list of link specifications. Our language admits link specifications of three types. The first type is specified as a pair of node variables. For example, (?n1 ?n2) in Figure 7. This specification matches any temporal ordering link in the plan, regardless if it was imposed by causal links or by the resolution of threats.

The second type of link specification matches causal links. Causal links are specified as triples composed of a producer step node variable, an edge predicate, and a consumer step node variable. The semantics of a causal link is that the producer step asserts in its effects the predicate, which in turn is needed in the preconditions of the consumer step. For example, the link specification (?n1 (on ?b1 Table) ?n2) in Figure 6 matches steps ?n1 that put a block ?b1 on the Table and steps ?n2 that subsequently pick up this block. That link specification applied to the plan in Figure 4 would result in the matches: (4 C 1) and (5 B 2), for the variables (?n1 ?b1 ?n2).

The third type of link specification matches ordering links originating from the resolution of threats (coming either from resource conflicts or from operator conflicts). These links are selected by using the keyword :threat in the place of a condition. For example, the resource-swap rule in Figure 10 uses the link specification (?n1 :threat ?n2) to ensure that only steps that are ordered because they are involved in a threat situation are matched. This helps to identify which are the ``critical'' steps that do not have any other reasons (i.e. causal links) to be in such order, and therefore this rule may attempt to reorder them. This is useful when the plan quality depends on the degree of parallelism in the plan as a different ordering may help to parallelize the plan. Recall that threats can be solved either by promotion or demotion, so the reverse ordering may also produce a valid plan, which is often the case when the conflict is among resources as in the rule in Figure 10.

Interpreted predicates, built-in and user-defined, can be specified in the :constraints field. These predicates are implemented programmatically as opposed to being obtained by matching against components from the plan. The built-in predicates currently implemented are inequality⁸ (:neq), comparison (< <= > >=), and arithmetic (+ - * /) predicates. The user can also add arbitrary predicates and their corresponding programmatic implementations. The interpreted predicates may act as filters on the previous variables or introduce new variables (and compute new values for them). For example, the user-defined predicate possibly-adjacent in the rules in Figure 6 ensures that the steps are consecutive in some linearization of the plan.⁹ For the plan in Figure 4 the extension of the possibly-adjacent predicate is: (0 4), (0 5), (4 5), (5 4), (4 1), (5 1), (1 2), (2 3), and (3 Goal).

The user can easily add interpreted predicates by including a function definition that implements the predicate. During rule matching our algorithm passes arguments and calls such functions when appropriate. The current plan is passed as a default first argument to the interpreted predicates in order to provide a context for the computation of the predicate (but it can be ignored). Figure 11 show a skeleton for the (Lisp) implementation of the possibly-adjacent and less-than interpreted predicates.

Figure 11: Sample Implementation of Interpreted Predicates

(defun possibly-adjacent (plan node1 node2)
  (not (necessarily-not-adjacent 
        node1 
        node2 
        ;; accesses the current plan
        (plan-ordering plan)))

(defun less-than (plan n1 n2)
  (declare (ignore plan))
  (when (and (numberp n1) (numberp n2))
    (if (< n1 n2) 
        '(nil) ;; true
      nil))) ;; false

The consequent is composed of the :replace and :with fields. The :replace field specifies the subplan that is going to be removed from the plan, which is a subset of the steps and links identified in the antecedent. If a step is removed, all the links that refer to the step are also removed. The :with field specifies the replacement subplan. As we will see in Sections 3.1.2 and 3.1.3, the replacement subplan does not need to be completely specified. For example, the :with field of the avoid-move-twice rule of Figure 6 only specifies the addition of a stack step but not how this step is embedded into the plan. The links to the rest of the plan are automatically computed during the rewriting process.