pushUP(S)
As ← **get actions leading to S** forall a ∈ As x ← 0 Sx ← **get parent node of S**
/** Getting highest ancestor for each action Loop Ax ← **get actions leading to** Sx If (parallel(**a, A**x))
x ← x + 1 Sx ← **get parent node of** Sx−1 Else aj ← get action conflicting with a **from** Ax If **(Secondary Optimizations)**
Remove a and aj **from branch**
Include anew **if necessary**
Else Ax−1 ← Ax−1 + a As ← As − a break End Loop
/**Adjusting the partial plan Sx ← **get highest ancestor x in history**
createNewBranchF rom(Sx)
while x > 0 Snew ← regress Sx **with** Ax−1 Sx ← Snew x ← x − 1 END;
Figure 7: Pushup **Procedure**
re-arrangement of the plan is done by the Pushup **procedure, which is shown in Figure 7.**
The Pushup procedure is called each time before a node gets expanded, and **it will try to**
compress the partial plan. For each of the actions a ∈ As **we find the highest ancestor node**
Sx of S in the search branch to which the action can be applied (i.e., **it gives some literal in** Sx without deleting any other literals in Sx**, and it is pairwise independent of all the actions** Ax currently leading out of Sx, in other words the condition parallel(a, Ax**) is satisfied).** Once Sx is found, a is then removed from the set of actions As leading to S **and introduced** into the set of actions leading out of Sx **(to its child in the current search branch). Next, the** states in the search branch below Sx **are adjusted to reflect this change. The adjustment** involves recomputing the regressions of all the search nodes below Sx**. At first glance, this**
might seem like a transformation of questionable utility since the preconditions of a **(and**
their regressions) just become part of the descendants of Sx**, and this does not necessarily**
reduce the length of the plan. We however expect a length reduction because actions supporting the preconditions of a **will get "pushed up" eventually during later expansions.**