
## 2. Preliminaries: Planning, Rewriting, And Local Search

The framework of Planning by Rewriting arises as the confluence of several areas of research, namely, artificial intelligence planning algorithms, graph rewriting, and local search techniques. In this section we give some baground on these areas and explain how they relate to PbR.

## 2.1 Ai Planning

We assume that the reader is familiar with classical AI planning, but in this section we will highlight the main concepts and relate them to the PbR framework. Weld (1994, 1999) and Russell & Norvig (1995) provide excellent introductions to AI planning.

PbR follows the classical AI planning representation of actions that transform a state.

The state is a set of ground propositions understood as a conjunctive formula.  PbR, as most AI planners, follows the Closed World Assumption, that is, if a proposition is not explicitly mentioned in the state it is assumed to be false, similarly to the negation as failure semantics of logic programming. The propositions of the state are modified, asserted or negated, by the actions in the domain. The actions of a domain are specified by operator schemas.

An operator schema consists of two logical formulas: the precondition, which defines the conditions under which the operator may be applied, and the postcondition, which specifies the anges on the state effected by the operator.  Propositions not mentioned in the postcondition are assumed not to change during the application of the operator. This type of representation was initially introduced in the STRIPS system (Fikes & Nilsson, 1971).

The language for the operators in PbR is the same as in Sage (Knoblock, 1995, 1994b),
which is an extension of UCPOP (Penberthy & Weld, 1992). The operator description language in PbR accepts arbitrary function-free first-order formulas in the preconditions of the operators, and conditional and universally quantified effects (but no disjunctive effects).

In addition, the operators can specify the resources they use. Sage and PbR address unit non-consumable resources.  These resources are fully acquired by an operator until the completion of its action and then released to be reused.

Figure 2 shows a sample operator schema specification for a simple Blocks World domain, 4 in the representation accepted by PbR. This domain has two actions: stack, which puts one block on top of another, and unstack, which places a block on the table. 5 The state is described by two predicates: (on ?x ?y) 6 denotes that a block ?x is on top of another block ?y (or on the Table), and (clear ?x) denotes that a ?x block does not have any other block on top of it.

An example of a more complex operator from a process manufacturing domain is shown in Figure 3. This operator describes the behavior of a punch, which is a machine used to make holes in parts. The punch operation requires that there is an available clamp at the machine and that the orientation and width of the hole is appropriate for using the punch.

After executing the operation the part will have the desired hole but it will also have a