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 ssse type machine and collect pairs of step number ?n1 and machine object ?x.

(define-rule :name resource-swap
:if (:operators ((?n1 (machine ?x) :resource)
(?n2 (machine ?x) :resource))
:links ((?n1 :threat ?n2)))
:replace (:links (?n1 ?n2))
:with (:links (?n2 ?n1)))
Figure 10: Resource-Swap Rewriting Rule 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 8 ( : neq ), comparison (< <= > >=), and arithmetic (+ - * /) predicates. The user can also add arbitrary predicates and their corresponding programmatic implementa¬