Recall that MaxReq(v**) stands for an upper bound on the number of value changes of** v that may be required by a valid, irreducible plan. However, the maximal achievable number of value changes of v**, denoted by** MaxPoss(v**) can be greater or less than** MaxReq(v**). For**
example, if v **has no predecessors in the causal graph, and there are two operators affecting**
v **differently, then** MaxPoss(v) = ∞.

We denote the upper bound on the feasible number of value changes of v **that may**
be required in a valid, irreducible plan for Π by FMaxReq(v**). Informally, no more than** MaxPoss(v) value changes of v can **be required and no more than** MaxReq(v**) value changes**
of v should **be required, thus**

## Fmaxreq(V**) = Min(**Maxposs(V), Maxreq(V**)) (3)**

Determining FMaxReq(v) for all variables requires explicit examination of a given **problem instance. Recall that here we restrict the causal graph of Π to form a polytree. To**
simplify the presentation, we assume that the goal values are specified for all state variables, i.e. Goal ∈ D(v1) × . . . × D(vn**). Later we show that this assumption does not affect the**
generality of the algorithm. Denote by v 0 and v
∗the initial and the goal values of v **in Π,**
and by Λv ⊆ Λ the set of all operators affecting v**. First we examine the root variables of**
the causal graph, then we analyze the rest of the variables.

Denote by pred(v) the immediate predecessors of v **in the causal graph. If** pred(v) = ∅,
then there are at most two operators A−
v
, A+
v**in Λ**v: A+
v has v
∗ **as its postcondition, while**
A−
v has the reverse effect. Since these operators have no prevail **condition, if both** A−
vand A+
v are presented in Λ, then they can be applied one after another **an infinite number of**
times. Therefore, from Eq. 3, FMaxReq(v) = n**. If Λ**v 6= {A−
v
, A+
v } **then we have two cases:**
If the initial and the goal values of v **are the same, then we cannot change the value of** v and reconstruct it later, and thus FMaxReq(v**) = 0. Alternatively, if the initial and the goal**
values of v **are different then if Λ**v = {A+
v } then we can achieve the goal value of v **but only**
once and thus FMaxReq(v) = 1. Otherwise, the goal value of v **is unachievable, thus the**
given problem instance is unsolvable. Table 2 summarize this analysis.

| Λv        | FMaxReq(v)   |    |
|-----------|--------------|----|
| 0 = v ∗   | {A− , A+     |    |
| v         | v }          | n  |
| v         |              |    |
| otherwise | 0            |    |
| 0 6= v ∗  | {A− , A+     |    |
| v         | }            | n  |
| v         | v            |    |
| {A+ v }   | 1            |    |
| otherwise | no solution  |    |

Now consider a variable v **which is presented by an internal node in the causal graph:**
pred(v) = {w1, . . . , wk} 6= ∅. Observe that the number of possible value changes of v **depends**
on and only on:
1. The initial and the goal values of v**, i.e.,** v 0 and v
∗.