We indicate with Threats(a) the set of preconditions of the actions in A that would become unsupported when adding a (similarly for the action preconditions that could be subverted by an action in the relaxed plan). Using the causal-link notation of partial-order planners (e.g., McAllester & Rosenblitt, 1991; Penberthy & Weld, 1992), Threats(a) can be formally defined in the following way

$Threats(a)=\{f\mid$ no-op($f$) and $a$ are mutex; $\exists\,b,c\in\mathcal{A}$ such that $b\stackrel{{f}}{{\to}}c\}$.  
Note that, according to our representation, b → c implies Level ( b ) < Level ( a ) < Level ( c ),
where Level (x) denotes the level of x in A.

Figure 3 gives a recursive algorithm for computing our relaxed plans, RelaxedPlan, which uses the following additional notation.  Duration(a) denotes the duration of a ; 11 Pre (a) denotes the precondition nodes of a; Add (a) denotes the (positive) effect nodes of a; Supported facts ( l ) denotes the set of positive facts that are true after executing the actions at levels that precede l (ordered according to their level); Num acts ( p, l ) denotes an estimated minimum number of actions required to reach p from Supported_facts( l ) (if p is not reachable, Num acts ( p, l ) is a negative number). The technique for computing Num acts is described in Section 3.3.

Given a set G of goal facts, an initial state INIT t , and a possibly empty set of actions A t RelaxedPlan computes a pair Rplan = ⟨ ACT S, t ⟩ where: ACT S is a set of actions including A and forming a relaxed plan achieving G from INIT i ; t is a temporal value estimating the earliest time when all facts in G are achieved. The first element of Rplan is indicated with A set ( Rplan ), the second with End_time ( Rplan ).

As mentioned above and described in detail in Section 3.2.3, when we evaluate the addition of an action a, RelaxedPlan is run twice: first to compute a relaxed plan for the preconditions of a , and then to extend this plan for achieving the preconditions that would be subverted by a (i.e., Threats (a)). The input set A is the set of actions currently in the relaxed plan that can be "reused" to achieve an action precondition or goal of the relaxed
(sub)problem. A is not empty whenever RelaxedPlan is recursively executed, and when it is run to achieve Threats(a).

RelaxedPlan constructs Rplan through a backward process where Bestaction(g) is the action a ′ chosen to achieve a (sub)goal g , and such that: (i) g is an effect of a ′ ; (ii) all preconditions of a ′ are reachable from INIT t ; (iii) the reachability of the preconditions of a ′ requires a minimum number of actions, estimated as the maximum of the heuristic minimum number of actions required to support each precondition p of a ′ from INIT 1 (i.e.,
the maximum of N um acts ( p, l ) over each precondition p of a ′ ); ( iv ) a ′ subverts a minimum number of supported precondition nodes in A (i.e., the size of the set Threats ( a ′ ) is minimal). More formally,

$$B\,e\,d a c t i o n\,(g)=A R G M I N\,\left\{\operatorname*{max}_{\{a^{\prime}\in A_{g}\}}\left\{\operatorname*{max}_{p\in P r e\,\{a^{\prime}\}=F}N\,u m_{a}a c t s(p,l)+\left|T h r\,e a t s(a^{\prime})\right|\right\},\right.$$

where F is the set of positive effects of the actions currently in ACTS, and Ag is the set of actions with the effect g and with reachable preconditions, i.e.,