Algorithm: **pop-pcg** (hA, O,Li, agenda, Λ)
1. **Termination:** If agenda **is empty, return** hA, O,Li

2. Goal selection: Let hϑi, Aneedi be a rightmost **pair on the** agenda **(by definition,**
Aneed ∈ A and ϑiis one of the pre/prevail conditions of A**need**).
3. **Operator selection:**

(a) If A**need** 6= A∗
i
(ϑi = ν j i
) then Aadd = A(ν j i
) ∈ Γi ∪ {A0 i
}.

(b) Otherwise:
i. Let m **= max** { j | A(ν j i
) **∈ A}**.

ii. If v
∗
i is consistent with ν m i**(both associated with the same color from** {b,w})
then Aadd = A(ν m i
), else Aadd = A(ν m+1 i).

4. Plan updating: Let L = L ∪ {Aadd →
ϑi Aneed}, and let O = O ∪ {Aadd < Aneed}**. If**
Aadd is newly instantiated, then A = A ∪ {Aadd} and O = **O ∪ {**A0 i < Aadd < A∗
i
}
(otherwise A and O **remain unchanged).**
5. Update goal set: Let agenda = agenda - {hϑi, Aneedi}. If Aadd **is newly instantiated,**
then for each of its pre/prevail conditions Q, add hQ, Aaddi to agenda.

6. Threat prevention: If Aadd = A(ν j i
), j > 1, then, for each A ∈ A**, s.t.** ν j−1 i**belongs**
to the prevail conditions of A, add {**A < A**(ν j i
)} to O.

7. Recursive invocation: **pop-pcg**(hA, O,Li, agenda, Λ**), where** agenda **is topologically ordered (based on the causal graph with respect to the precondition part of each**
pair).
Figure 6: pop-pcg **algorithm**
fails if and only if the initial and the goal values of v **are different but there is no way to**
change the value of v even once. Thus, if forward-check **fails, then no plan exists.**
To prove the opposite direction we proceed as follows: We define the pop-pcg **algorithm**
(POP for polytree causal graphs) and show that it will succeed without backtracking if forward-check succeeds.5 pop-pcg **is described in detail in Figure 6, and it works as**
follows: First, let us expand each sequence of operator instances Γi by A(ν 1 i
) (A(b 1 i
)) which will stand for the dummy operator A0 i
. (Recall that up until now, only operators of the form A(ν j i
) for j > 1 were defined.) The algorithm maintains a goal agenda sorted **based**
on the causal graph structure: parent variables appear after their descendents. At each point, the next agenda item is selected; if it requires achieving some value for vi **we add the**
corresponding operator to the plan with the desired effect (step 3a). Actually, if we would be ready to accept plans with possible redundant steps, we can omit the next step 3b from the algorithm by assuming that the goal value of each variable v **is the last element of the**