the worlds where it was *needed*, which in general is fewer worlds than where it is *reachable* (i.e.

it is always the case that ℓ RP
r(·) |= ℓr(·)). Next we form L
RP
1 with the execution preconditions of actions in ARP
1and antecedents of effects in E
RP
1, which are ¬clog, inP1, and inP2, labelled with all worlds where an action or effect needed them. In the same fashion as level two, we support the literals at level one, using persistence for inP1 and inP2, and Flush for ¬clog. We stop here, because we have supported all clauses at level one.

For the general case, extraction starts at the level b where BSiis first reachable from BSP .

The first relaxed plan layers we construct are ARP
b−1
, E
RP
b−1
,L
RP
b, where L
RP
bcontains all clauses C ∈ κ(BSi), labelled as ℓ RP
k(C) = BSP .

For each level r, 1 ≤ r ≤ b, we support each clause in L
RP
rby choosing relevant effects from Er−1 to form E
RP
r−1
. An effect ϕ j(a) is relevant if it is reachable in some of the worlds where we need to support C (i.e. ℓr−1(ϕ j(a)) ∧ ℓ RP
r(C) 6=⊥) and the consequent gives a literal l ∈ C. For each clause, we have to choose enough supporting effects so that the chosen effect worlds are a superset of the worlds we need to support the clause, formally:

$$\forall_{C\in{\mathcal{L}}_{r}^{R P}}\ell_{r}^{R P}(C)\models\left(\begin{array}{c}{{}}\\ {{\bigvee_{\begin{array}{c}{{\ell_{r-1}^{R P}(\varphi^{j}(a))}}\\ {{\ell\in C,}}\\ {{\varphi^{j}(a)\in{\mathcal{E}}_{r-1}}}\end{array}}}\end{array}}}\end{array}\right)$$

We think of supporting a clause in a set of worlds as a set cover problem where effects cover subsets of worlds. Our algorithm to cover the worlds of a clause with worlds of effects is a variant of the well known greedy algorithm for set cover (Cormen, Leiserson, & Rivest, 1990). We first choose all relevant persistence effects that can cover worlds, then choose action effects that cover the most new worlds. Each effect we choose for support is added to E
RP
r−1 and labelled with the new worlds it covered for C. Once all clauses in L
RP
rare covered, we form the action layer ARP
r−1 as all actions that have an effect in E
RP
r−1
. The actions in ARP
r−1 are labelled to indicate all worlds where any of their effects were labelled in E
RP
r−1
.

We obtain the next subgoal layer, L
RP
r−1
, by adding literals from the execution preconditions of actions in ARP
r−1 and antecedents of effects in E
RP
r−1
. Each literal l ∈ LRP
r−1 is labelled to indicate all worlds where any action or effect requires l. We support the literals in L
RP
r−1 in the same fashion as L
RP
r. We continue to support literals with effects, insert actions, and insert action and effect preconditions until we have supported all literals in L
RP
1.

Once we get a relaxed plan, the relaxed plan heuristic, h LUG
RP (BSi), is the summation of the number of actions in each action layer, formally:

$$h_{R P}^{L U G}(B S_{i})=\sum_{i=0}^{b-1}\mid{\mathcal A}_{i}^{R P}\mid$$

Thus in our CBTC example we have h LUG
RP (BSG**) = 3**. Notice that if we construct the LUG
without mutexes for CBTC we reach the goal after two layers. If we had included mutexes the LUG, then it would reach the goal after three layers. The way we use mutexes will not change our relaxed plan because we do not use mutexes to influence relaxed plan extraction. Mutexes only help to identify when a the belief state BSiis not reachable from BSP .