$\mathbb{S}=\text{res}(\mathbb{S},a)=\mathbb{S}\setminus\text{Del}(a)\cup\text{Add}(a)$.  
S' = *res(S*,a) = S \ Del(a) ∪ *Add(a*) (2)
Inductively we can define the state resulting from the application of a sequence of actions (a1, a2, ..., aN) to a state S as:
S' = *res(S, (a*1, a2, ..., aN)) = *res( res(S*, (a1, a2, ..., aN-1)), aN) (3)
with the requirement that each action ai is applicable to the state res(S, (a1, a2, ..., ai-1)), for each i=1, 2, ..., N. In the formalization used henceforth, the set of problem constants is assumed to be finite and no function symbols are used, so the set of actions is finite. 

A planning problem P is a triplet P=(*O, Initial, Goals*), where O is the set of ground actions, Initial is the initial state and *Goals* is a set of facts. The task is to find a sequence of actions a1, a2, ..., aN that can be applied to the initial state, so that the state resulting from their application will be a superset of *Goals*. The sequences of actions are called *Plans*. A plan that can be applied to the initial state is called a *valid plan*. A valid plan that achieves the *Goals* is called a *solution* of the planning problem. A planning problem may have several or no solutions. In the latter case the problem is described as *unsolvable*.

The next sub-section gives a brief presentation of the ASP heuristic, which was our motivation and helps to understand the following concepts, whereas the subsequent sub-sections present the GRT heuristic in detail.

## 2.1 The Asp Heuristic

In the ASP heuristic, for each action a and for each fact p ∈ Add(a), a rule C→p is formed, where C=Pre(a). Assuming a set of rules, it is said that a fact p is *reachable* from a state S if p ∈ S or there is a rule C → p such that each fact q ∈ C is reachable from S.

So, a function g(p,S) is defined, which inductively assigns a number i to each fact p, where i is an estimate of the number of steps needed to achieve p from S, i.e. the distance of p from S. More specifically, g(p,S) is set to 0 for every fact p ∈ S, while g(p,S) is set to *i+1, i* ≥ 0, for each fact p for which a rule C → p exists, such that ∑∈=
r C
g(r, S) i. Thus:

$$g(p,S)=\left\{\begin{array}{c c}{{0,}}&{{\mathrm{if}\ p\in S}}\\ {{}}&{{}}\\ {{\mathrm{i+1,}}}&{{\mathrm{if~for~some~}C{\to}p,\ \sum_{r\in C}g(r,S)=i}}\\ {{}}&{{}}\\ {{\infty,}}&{{\mathrm{if}\ p\ \mathrm{is~not~reachable~from}\ S}}\end{array}\right.$$
$$\mathbf{\Sigma}(\mathbf{4})$$

In the case where there are more than one rules C→p for a fact p, the rule with the minimum cost is chosen. Note that a fact p that was initially achieved by a rule C1→p, may be re-achieved, later, by another rule C2→p with smaller cost. That is because not all the preconditions of the second rule had been achieved at the time when the first rule was applied. The task of applying rules continues until no rule that can achieve a fact with smaller cost exists. The distances computed in this way are unique.

For a set of facts P, their distance from S is defined as:

$$g(P,S)=\sum_{p\in P}^{d e f}g(p,S)$$
g(P,S) g( p,S) (5)
The ASP planner uses *g(P,S*) to estimate the distances between each intermediate state S and the Goals. So, the ASP heuristic function is defined as: 

$$({\boldsymbol{\bar{s}}})$$
