supports subgoals that are harder to achieve. Here, the hardness of a literal l **is measured**
in terms of the level in the planning graph at which l **first appears. The standard rationale**
for this decision (c.f. Kambhampati & Sanchez, 2000) is that **we want to fail faster by**
considering the most difficult subgoals first. We have an additional justification in our case, we also know that a subgoal with a higher level value requires **more steps and actions for**
its achievement because it appeared later into the planning **graph. So, by supporting it** first, we may be able to achieve other easier subgoals along the way and thereby reduce the number of parallel steps in our partial plan.

Fattening the Pivot Branch: **Next the procedure needs to decide which subset** O ⊆ A
of the sibling actions of the pivot action ap **will be used to fatten the pivot branch. The**
obvious first idea would be to fatten the pivot branch maximally by adding all pairwise independent actions found during that search stage. The problem with this idea is that it may add redundant and heuristically inferior actions to the branch, and satisfying their preconditions may lead to an increase of the number of parallel steps.

So, in order to avoid fattening the pivot branch with such irrelevant actions, before adding any action a to O, we require **that the heuristic cost of the state** S
′**that results**
from regressing S over O + a be strictly lower than that of S**. This is in addition to the** requirement that a be pairwise independent with the current set of actions in O**. This**
simple check also ensures that we do not add more than one action for supporting the same set of subgoals in S.

The overall procedure for fattening the pivot branch thus involves picking the next hardest subgoal g in S **(with hardness measured in terms of the level of the subgoal in the**
planning graph), and finding the action ag ∈ A achieving g**, which is pair-wise independent**
of all actions in O and which, when added to O and used to regress S**, leads to a state** S
′
with the lowest heuristic cost, which in consequence should **be lower than the cost of** S.

Once found, ag is then added to O**, and the procedure is repeated. If there is more than one**
action that can be ag**, then we break ties by considering the degree of overlap between the** preconditions of action ag and the set of actions currently in O**. The degree of precondition**
overlap between a and O is defined as |prec(a) ∩ {∪o∈Oprec(o)}|. The action a **with higher**
degree of overlap is preferred as this will reduce the amount **of additional work we will need**
to do to establish its preconditions. Notice that because of **the fattening process, a search**
node may have multiple actions leading to it from its parent, **and multiple actions leading**
from it to each of its children.

Example: **Figure 5 illustrates the use of this node expansion procedure for a problem** from the logistics domain (Bacchus, 2001). In this example we have four packages pack1, pack2, pack3 and pack4**. Our goal is to place the first three of them at** ASU **and the** remaining one at home**. There are two planes** airp1 and airp2 **to carry out the plans. The**
figure shows the first level of the search after S **has been regressed. It also shows the pivot**
action ap **given by** unload(pack1,airp1,ASU)**, and a candidate set of pairwise independent** actions with respect to ap**. Finally, we can see in Figure 6 the generation of the parallel**
branch. Notice that each node can be seen as a partial regressed plan. As described in the paragraphs above, only actions regressing to lower heuristic estimates are considered in apar to fatten the pivot branch. Notice that the action unload(pack4,airp2,Home) **has been** discarded because it leads to a state with higher cost, even though it is not inconsistent