Bonet & Geffner proposed two basic heuristics for HSP, h m ax and h add . In h add the
(search) cost of a set of facts is the sum of the costs of each individual fact, while in hmax it is the maximum cost over all individual costs.  As noted by Haslum and Geffner (2000), hmax and hada are approximation of the optimal cost function of a relaxed problem where delete effects are ignored. h add ignores positive interactions among subgoals that could make one goal simpler after a second one has been achieved (this makes hgdd non-admissible). hmax is admissible, but it is less informative and effective for Bonet & Geffner's HSP planner.

A difference between the forward process of our algorithm for computing Num act s and Bonet & Geffner's forward propagation for computing h add is that in our propagation every action is applied at most once, while in their propagation it can be considered more than once (for computing hmax it suffices to apply each action once with an appropriate order). This restriction, that we introduced for efficiency reasons, can clearly lead to overestimation of reachability costs. By adding a new step between steps 17 and 18 of ComputeReachabilityInformation that adds to A every action with f as precondition, we can obtain a more accurate cost propagation like in h add . However, this could slow down the planning process, given that reachability information may be (re)computed many times during search.

Another important difference concerns the use of the subroutine RequiredActions at step 10 for estimating the cost of reaching a set of preconditions G.  Instead of considering the maximum value over the costs of the preconditions or the sum of their costs, like in hmax and hadd , respectively, we compute a relaxed plan for G , and we count the number of actions forming it. This can be seen as an intermediate approach between the hmgx and had methods, aimed at taking account of positive interactions among subgoals. 16 Finally, another difference concerns the initial set of actions used in the forward process.

While our set ( O ) does not contain actions with preconditions that are mutex, Bonet &
Geffiner's forward processes for computing hmex and hedd contain them.  The use of our restricted set of actions would make the approximation of hmax and hadd more accurate.

As observed by Hoffmann (2001), FF's reachability technique is similar to h mex ; and so the previous observations about h max compared to our reachability information hold also for FF's technique. Another difference with respect to FF concerns the choice of actions forming the relaxed plans. While RelaxedPlan and EvalAdd take threats into account, FF's relaxed plans do not consider them.  Moreover, FF can generate relaxed plans including actions with mutex preconditions, while we exclude such actions.

Most of the differences with respect to HSP's and FF's reachability information that we have outlined appear to also hold when comparing ComputeReachabilityInformation and SAPA's reachability techniques (in particular, the use of RequiredActions for estimating the ss forward process, and the use of a more restrictive set of actions O ). Another significant difference is that, while SAPA's reachability information concerns execution and temporal costs, our information concerns mainly search costs.  As a consequence, the action choices in RelaxedPlan depend mainly on the search costs (as we pointed out, when there is more than one action with the lowest search cost, Bestaction chooses the one with lower execution cc