The ASP heuristic does not take into account the delete lists of the actions. The simplified problem that is created by ignoring the delete lists is referred to as the *relaxed problem* and the corresponding actions are referred to as the *relaxed actions*. The complexity for constructing HASP(S) is linear, with respect to the number of ground actions and the number of ground facts.

## 2.2 Backward Heuristic Construction

Instead of estimating the distance between each fact and the current state in a forward direction, as ASP does, GRT estimates the distance between each fact and the goals in a backward direction. This task is performed once, in a pre-processing phase. During the search phase, these estimates are used to estimate the distance between each intermediate state and the goals. The backward or forward estimation of the distance between two states often results in different values, since no heuristic is precise. However, the two directions result in estimates of equal quality on average.

The estimates of the distances between each fact and the goals are stored in a table, the records of which are indexed by the facts. We call this table the Greedy Regression Table (by which the acronym GRT comes from), since its estimates are obtained through greedy regression from the goals.

In order to construct the heuristic backwards, the actions of the problem have to be inverted. Let a be an action and S and S' be two states, such that a is applicable in S and S' = *res(S,a*). The inverted action a' of a is an action applicable in S', such that S = res(S', a'). The inverted action is defined by the original action as follows:

$\tau$
Pre(a')=Add(a) ∪ *Pre(a*) \ Del(a)

$$A d d(a^{\prime})=D e l(a)$$
$$(T)$$
$$D e l(a^{\prime}){=}A d d(a)$$

The inverted ground actions are applied to the goals, assigning progressively to each ground fact p an estimate of its distance from the goals, in a way similar to ASP. Applying inverted actions to the goals presupposes that the goals form a complete state. In Section 2 it is assumed that this is always the case, whereas in Section 3 the case of incomplete goal states is treated.

## 2.3 Related Facts

In order to obtain more precise estimates, GRT heuristic tries to track the interactions that arise when estimating the distances between each fact and the goals. By the word 'interaction' we mean that achieving a fact may affect achieving other facts positively or negatively. In order to track these interactions the notion of the *related facts* is introduced. Definition 1 (Related facts). A fact q is related to another fact p, if achieving p causes fact q to be achieved as well. 

We will use the notation q p %rel to denote that q is related to p. The set of all facts related to a specific fact p is denoted as *rel(p*), i.e.:

$$r e l(p)=\{q:q\smile_{r e l}p\}$$
rel( p) {q : q p} %rel = (8)
The set of related facts of a set of facts P is defined as the union of the related facts of P-facts: