procedure VPC;
1 Input: a valid self-contained t.o. plan < 1 2 n where 1 = 1 and n = G
Output: A self-contained valid p.o. plan 3 4  for 1 ≤  ≤
do for  E pre( i ) do 5 6 Find max st. E post( k);
7 if such a   exists  then 8 Order k < i 9 for ¬ E post( ¡) do 10 for 1 ≤
st. E pre( k) do Order k - i 11 for each primary effect   E post( ¡)  do 12 for 1 ≤  ≤  s.t. ¬  E post( k )  do 13 14 Order i < k 15 for 1 do Order i ← i and i ← G
16 return {{ 1 17 n Figure 11: The VPC algorithm into a p.o. plan which is then post-processed to determine which actions can be executed in parallel. The action language used is a STRIPS-style language allowing quantifiers and context-dependent effects. However, the plans produced by the planner, and thus input to VPC, are ground and without context-dependent effects.  That is, they are ordinary propositional STRIPS plans. The VPC algorithm is presented in Figure 11, with a few minor differences in presentation as compared to its original appearance: First, the algorithm is presented in the GT formalism, in order to minimize the number of formalisms in this article, but all preconditions are assumed to be positive, thus coinciding with the original algorithm.

Second, while the original algorithm returns the transitive reduction of the computed order it instead returns the transitive closure here, an unimportant difference in order to coincide with the definition of plans in this article. Furthermore, Veloso® has pointed out that the published version of the VPC algorithm is incorrect and that a corrected version exists. The version presented in Figure 11 is this corrected version. A proposition is a primary effect if it appears either in the goal or in the subgoaling chain of a goal proposition.

VPC is a greedy algorithm which constructs an entirely new partial order by analysing the action conditions, using the original total order only to guide the greedy strategy. The algorithm is claimed (Veloso et al., 1990, p. 207) to produce a 'least-constrained' p.o. plan, although no definition is given of what this means.  Veloso 7 has confirmed that the term 'least constrained plan' was used in a 'loose sense' and no optimality claim was intended. However, if this term is not defined, then it is impossible to know what problem the algorithm is intended to solve or how to judge whether it makes any improvement over using no algorithm at all. In the absence of such a definition from its authors, the algorithm will be analysed with respect to the least-constrainment criteria defined in Section 4. This is admittedly a