unit nononsumable resour es we onsidered, steps requiring the same resour e have to be

```
sequentially ordered, and su
                             h a 
                                  hain of ordering 
                                                    onstraints will appear in the plan.
                                                                                       

```

An example of a plan in the Blo ks World using this graph representation is given in Figure 4. This plan transforms an initial state onsisting of two towers: C on A, A on the Table, B on D, and D on the Table; to the nal state onsisting of one tower: A on B, B on C,

C on D, and D on the Table. The initial state is represented as step 0 with no pre onditions and all the propositions of the initial state as post onditions. Similarly, the goal state is

```
represented as a step goal with no post
                                      onditions and the goal formula as the pre
                                                                              ondition. The plan a
        hieves the goal by using two unsta
                                    k steps to disassemble the two initial towers
                                                                    

and then using three sta
                     k steps to build the desired tower. The 
                                                      ausal links are shown as
                                                                         

```

solid arrows and the ordering onstraints as dashed arrows. The additional ee ts of a step that are not used in ausal links, sometimes alled side ee ts, are shown after ea h step pointed by thin dashed arrows. Negated propositions are pre eded by :. Note the need

```
for the ordering link between the steps 2, sta
                                                    k(B C Table), and 3, sta
                                                                                  k(A B Table).
                                                                                                  

If step 3 
             ould be ordered 
                                    on
                                         urrently or before step 2, it would negate the pre
                                                                                                           ondition
                                                                                                                      
 lear(B) of step 2, making the plan in
                                                    onsistent. A similar situation o
                                                                                              
                                                                                               urs between steps
                                                                                                                      
1 and 2 where another ordering link is introdu
                                                              ed.
                                                                 

```

![0_image_0.png](0_image_0.png)

## 2.2 Rewriting

Plan rewriting in PbR is related to term and graph rewriting. Term rewriting originated

```
in the 
        ontext of equational theories and redu
                                                  tion to normal forms as an ee
                                                                                    tive way
                                                                                             

```

to perform dedu tion (Avenhaus & Madlener, 1990; Baader & Nipkow, 1998). A rewrite system is spe ied as a set of rules. Ea h rule orresponds to a preferred dire tion of an

```
equivalen
         e theorem. The main issue in term rewriting systems is 
                                                           onvergen
                                                                    e, that is, if
                                                                               

```

two arbitrary terms an be rewritten in a nite number of steps into a unique normal form.

In PbR two plans are onsidered \equivalent" if they are solutions to the same problem,
