

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

ssee what unfair analysis, but it reveals some interesting facts about the algorithm, and about what problems it does not solve. It is immediate from Theorem 4.8 and Corollary 4.9 that VPC cannot be expected to produce minimum-constrained de-/reorderings. Perhaps more surprisingly, VPC does not even guarantee that its output is a minimal-constrained deordering of its input, a problem already proven trivially polynomial (Theorem 4.4). This is illustrated by the following example.

SER SUPPOSE A TOTAL-ORDER PLANNER IS GIVEN THE PPI II =  0 as input. It may then return either of the Π-valid t.o. plans and          , with action conditions as shown in Figure 12. When used as input to VPC, these two t.o. plans will give quite different results  the plan will be converted to the p.o. plan 1 in Figure 12, while will be converted to the p.o. plan 2 in Figure 12. That is, in the first the plan case VPC produces a plan which is not only a minimal-constrained deordering but even a minimum-constrained deordering, while in the second case it does not even produce a minimal-constrained deordering. 8 The reason that VPC may fail to produce a minimal-constrained deordering is that it uses a non-admissible greedy strategy. Whenever it needs to find an operator   achieving an effect required by the precondition of another operator , it chooses the last su action ordered before in the input t.o. plan. However, there may be other actions earlier in the plan having the same effect and being a better choice.

## 8.2 The Kk Algorithm

Kambhampati and Kedar (1994) have presented an algorithm for generalising the ordering of a p.o. plan, using explanation-based generalisation. The algorithm is based on first constructing a validation structure for the plan and then use this as a guide in the generalisation phase. In the original paper, these computations are divided into two separate algorithms (EXP-MTC and EXP-ORD-GEN), but are here compacted into one single algorithm, KK (Figure 13). Furthermore, the version presented here is restricted to ground GT plans, while the original algorithm can also handle partially instantiated plans. This is no restriction for the results to be shown below.

The first part of the KK algorithm constructs a validation structure V for the plan, that is, an explanation for each precondition of every action in the plan. The validity criterion underlying this phase is a simplified version of Chapmans modal-truth criterion (Chapman,