maximal sequence σ(v). However, if we would like our plan to be irreducible, then a **careful**
decision about the really required number of value changes of each variable is required.

This decision is captured in step 3b by analysis of the value changes of a variable vi **that**
were found necessary in the previous iterations of the algorithm in order to satisfy the predecessors of vi**in the causal graph. Note that the agenda is sorted with respect to some**
reverse topological ordering of the causal graph, thus if an operator affecting vi **was selected**
from the agenda then no operator affecting some predecessor of vi**in the causal graph will**
appear on the agenda until the end of the algorithm. No threats arise in pop-pcg**, and the**
ordering constraints are consistent.

Lemma 2 If forward-check was successful then pop-pcg **will return a valid plan.**
Proof: **The lemma will follow from the following claims:**
1. For every agenda item, there exists an operator that has it **as an effect.**

2. There are no threats in the output of **pop-pcg**.

3. The ordering constraints in O **are consistent.**
4. The agenda will be empty after a polynomial number of steps.
For the proof see Appendix B, p. 343. 

Recall that, for simplicity of presentation, we assumed that the goal values are specified for all state variables (single goal state), i.e. Goal ∈ D(v1)×. . .× D(vn**). Now we show that**
the presented approach, with minor modifications, works for **a set of possible goal states as**
well, if such a set is specified by a partial assignment on V, i.e. Goal ∈ D+(v1)×**. . .**×D+(vn).

Note that the latter assumption is widely accepted in the planning literature.

First, no modifications should be done in processing variables that are specified by **Goal**.

Now, for each variable v**, such that** v
∗is not specified by Goal**, the modifications are as**
follows:

1. The graph G(v) will consist of exactly n **nodes. This is correct since (i) according to**
Lemma 1, n changes of v have to be sufficient, and (ii) any value change of v **can be**
its last value change.

2. No changes in construction of G′(v**) and** G′e
(v).

3. In the procedure **determine-max-sequence**:
(a) In step 2d, determine the longest path from the dummy source node to any **other**
node in the graph.

(b) In step 2e, always **return success.**
Again, this is correct since any value change of v **can be its last value change, and, in**
particular, v **may remain unchanged in a plan for a given problem.**
Finally, the pop-pcg **algorithm starts with a null plan that contains the end operator**
A∗
i only if v
∗
i is specified by **Goal**.