The above planners can primarily be classified based on the forward or backward direction, in which the heuristic is constructed and the state-space is traversed. We distinguish the following three categories:
 Forward heuristic construction, forward search (ASP, HSP, FF).

 Forward heuristic construction, backward search (HSPr, ALTALT).

 Backward heuristic construction, forward search (UNPOP, GRT).
Generally, the forward direction seems to be more advantageous than the backward one, both when constructing the heuristic and when searching, because in the backward direction and in case of incomplete goal states, problems with invalid states and unreachable facts usually arise. 

However, using the forward direction for both tasks requires reconstructing the heuristic function for each visited state, spending in this way a significant portion of the processing time, while using opposite directions for both tasks allows constructing the heuristic once, in a pre-processing phase.

This paper presents the GRT planning system. It is the only domain independent heuristic planner that constructs the heuristic once, in a backward direction and in a pre-processing phase. 

UNPOP, although it uses the same directions, reconstructs the heuristic from scratch for each visited state. GRT, in a pre-processing phase estimates the distance between each fact and the goals of the problem. During the search phase, these estimates are used in order to further estimate the distance between each visited state and the goals, guiding so the search process in a forward direction and on a best-first basis. Constructing the heuristic once offers the ability to evaluate states very quickly, while traversing the state-space in a forward direction allows the planner to avoid invalid states that arise in the regression space. 

The paper substantially extends previous work (Refanidis & Vlahavas, 1999b, 1999c, 2000a and 2000b), in that it presents and proves the fundamental theory of the planner, along with many new techniques developed on it, it extensively tests the contribution of each technique to its overall performance and provides a thorough comparison to other planning systems.

The rest of the paper is organized as follows: Section 2 presents the data structures and the main algorithms of the planner. Section 3 discusses the difficulties that incomplete goal states cause to the backward direction of the construction of the heuristic and presents methods to cope with them. The same methods are also applied to identify and enrich poor domain representations.

Two approaches to reduce the problem's size are presented in Section 4. The first one deals with the identification and elimination of irrelevant objects and the second one concerns the adoption of a numerical representation of resources.

Section 5 deals with the problem of local optimal states and proposes a method to cope with them. Specifically, the XOR-constraints are introduced and used in order to decompose difficult problems into easier sub-problems that have to be solved sequentially. Section 6 presents the operation of GRT, Section 7 presents the related work and Section 8 presents performance results, which show that GRT is among the fastest domain-independent planners. Finally, Section 9 concludes the paper and poses future directions.

## 2. The Grt Heuristic

In STRIPS (Fikes & Nilsson, 1971), each action a is represented by three sets of facts: the precondition list *Pre(a*), the add-list Add(a) and the delete-list *Del(a*), where Del(a) ⊆ *Pre(a*). A 
state S is defined as a finite set of facts. An action a is *applicable* to a state S if:
Pre(a) ⊆ S (1)
The state resulting from the application of an action a to state S is defined as: