procedure KK
1 Input: A valid self-contained p.o. plan (
2 Y
Output: A deordering of the input plan e 4 comment Build a validation structure V for the plan 5 V   V 
6 Y
7  for 1 ≤   ≤    do for  E pre( i ) do 8 9 Find min s.t.

10 1. E post( k ) and 11 2. there is no   s.t.

and ¬ E post( j)
Ad ( k         ) to V
1 2 13 comment Construct a generalised ordering - for the plan 14  for each (  ) E X  do Add (    ) to ~' if either of the following holds 15 16 1. 2. (      ) E V for some 17 18 3. (
) E V and ¬ E post( )
) E V and ¬ E post( )
19 4.

20 return

$\text{e}\,13;\text{}$ The K. 
Figure 13: The KK algorithm 1987) without white knights. Since the algorithm is simplified to only handle ground plans here, an explanation is a causal link C , meaning that the action   produces the which is consumed by the action  c . The algorithm constructs exactly one condition causal link for each precondition, and it chooses the earliest producer of   preceeding  
with no intervening action producing ¬ between this producer and  c. The second phase of the algorithm builds a generalised ordering  ' for the plan based on this validation structure.  To put things simply, only those orderings of the original plan are kept which either correspond to a causal link in the validation structure or that is required to prevent a threatening action to be unordered wrt. the actions in such a causal link.

It turns out that also the KK algorithm fails in generating plans that are guaranteed to be even minimal-constrained deorderings. Consider the t.o. plan with action conditions as indicated in Figure 14. This t.o. plan is valid for the PPI
Since the KK algorithm always chooses the earliest possible producer
()
of a precondition for the validation structure, it will build the validation structure G. Hence, the final ordering produced by KK will be as shown in Figure 14a. However, this plan is not a minimalconstrained deordering of the original plan, since it can be further deordered as shown in Figure 14b and remain valid. In this example, the input plan was totally ordered. In the case of partially ordered input plans, the behaviour of the algorithm depends on the particular topological order choosen. So the algorithm may or may not find a minimal-constrained deordering, but it is impossible to guarantee that it will succeed for all plans. Similarly, the authors mention that one may consider different ways of constructing the validation struc­