If p ∈ P\*Add(a*), then for every other fact q∈*P\Add(a*), if p%rel q, then dist(q)≥*dist(p*) 
(according to Proposition 3, which holds for *Facts*) and finally dist(q)=*dist(p*), because p has the maximum distance among the facts of P (the same rationale can be used in the case where there is a sequence of facts q1, q2, ..., qN, such that p%rel q1 and qi%rel qi+1, i=1, 2, ..., N-1). If q *∈Add(a*) and p%rel q, p would be a precondition of a, or a related fact of a precondition of a. However, in that case it would not be possible that p%rel q, because the distance of q would be greater than the cost of p (according to Axiom 2, which holds for the preconditions of action a) and this is in contradiction with the hypothesis that p has the maximum distance among the facts of P.

Let us consider the case where p ∈ Add(a). If p has just been firstly achieved, then the only facts q, for which p%rel q hold, are certainly the other just achieved or re-achieved add effects of action a, which have the same application cost. If p has been re-achieved by a with smaller cost, then it is impossible to hold p%rel q for another fact q ∈ *P\Add(a*). Actually, in this hypothetical case we would have dist(q)≥*dist*OLD(p), since Proposition 3 holds for q and the previous distance of p, and distOLD(*p)>dist*NEW(p), so dist(q)>*dist*NEW(p), which is in contradiction with the hypothesis that p has the maximum distance among the facts of P. Therefore, in any case, p or another fact of equal cost is included in M2 and the cost of achieving simultaneously the facts of P is equal to or higher than their maximum distance. 

We close this section by mentioning the two types of facts, the *static facts* and the *dynamic* facts, that can be found in a problem. The first type concerns the facts that are neither added nor deleted by any action, while the second concerns the rest of the facts. GRT classifies automatically the facts, by analyzing the action schemas of the domain. All the procedures presented in Section 2, i.e. the distance estimates and the related facts, concern only the dynamic facts.

## 3. Detecting And Enhancing Incomplete States

Backward heuristic construction induces a problem: In most of the problems the goals do not constitute a complete state description, so it is not possible to apply inverted actions to them. For example, in the commonly used *logistics* problems, where packages have to be moved between several locations via trucks and planes, the goals do not determine the final locations of the trucks and the planes. The source of the problem is that the GRT heuristic is constructed using a stricter than usual regression, i.e. it uses actions, the add effects and the non-deleted preconditions of which (i.e. the preconditions of the corresponding inverted actions) are included within the goals 
(in the usual regression, actions with at least one add effect within the goals are used). In this way GRT succeeds in obtaining more precise estimates and avoiding unreachable facts.

The solution adopted by GRT to confront the problem of incomplete goal states is to enhance the goals with new facts, which are not in contradiction to the existing ones. For example, since the goals of the 'logistics.a' problem (Veloso, 1992) do not determine the final locations of the two planes, it is supposed that each one of the planes could be at any of the three airports. So, the ground facts:
(*at plane1 pgh_air*) (at plane1 *bos_air*) (at plane1 *la_air*)
(at plane2 *pgh_air*) (at plane2 *bos_air*) (at plane2 *la_air*)
can be added to the new goal state, which is called henceforth the *enhanced goal state*.

It should be noted that the enhanced goal state is only used in the pre-processing phase, for the construction of the heuristic. During the search phase, attention is paid only to reach the original 