different than its initial location, and the corresponding actions, are not created. Note that in this stage, both the normal and the inverted actions are computed; the former are used in the mutex computation stage, while the latter are used in the heuristic construction stage. However, no preinstantiated actions are used during the state-space search, where the applicable actions to each state are computed by progressively instantiating the action schemas, using constraint satisfaction techniques (forward checking and intelligent backtracking).

The stages that follow are the computation of the mutual exclusion relations, the enrichment of the domain, and the problem processing. The latter stage consists of several sub-stages, as it is shown in Figure 6b, where the most important ones are the construction of the heuristic and the state-space search. Note that when we refer to the pre-processing phase of GRT, we mean all stages that precede the state-space search.

In the case where XOR-constraints are provided, GRT attempts to decompose the current problem into sub-problems. If this attempt is successful, the problem processing stage is executed recursively for each sub-problem, otherwise the current problem is solved. Finally, in the case of decompositions, the partial solutions are merged and the overall solution is returned.

## 7. Related Work

This section briefly presents other domain independent heuristic state-space planning systems, by emphasizing their similarities and differences to GRT, in terms of the way in which they construct their heuristic and the direction they traverse the state-space. We omit certain pieces of related work that concern specific pre-processing techniques implemented in GRT, as for example the elimination of irrelevant objects, since they have already been presented in previous sections.

The recent evolvement of the domain independent heuristic planning started with the work of Drew McDermott (1996, 1999) on UNPOP (UN-Partial Order Planner, UN- stands for non-). McDermott's planner is not restricted to pure STRIPS representations, supporting the more expressive language ADL (Pednault, 1989). The planner proceeds forward in the state-space. 

Distance estimates between states are based on the so-called regression graph, which is built from the goals using non fully-instantiated actions. UNPOP does not consider subgoals interactions and reconstructs the regression graph from scratch for each intermediate state. Although this planner is not competitive enough, compared to the subsequent heuristic planners, it was the faster one at the time of its appearance. However, we have to note that UNPOP has been developed in LISP, whereas the other heuristic planners are highly optimized C or C++ programs.

Although UNPOP was the first domain independent heuristic planner, the area has been pushed forward by the ASP (*Action Selection Planner*, Bonet, Loerings & Geffner, 1997) and HSP
(*Heuristic Search Planner*, Bonet & Geffner, 1998) planners. The attractive feature of these planners is the simple way the heuristic is constructed, presented in Section 2.1. ASP used a bestfirst strategy with limited agenda, while HSP uses a hill-climbing one with limited plateau search and restarts (an in-depth presentation of the state-space search algorithms is given by Zhang, 1999).

Both ASP and HSP reconstruct their heuristic from scratch for each intermediate state. A 
variation, called HSPr (r stands for *regression*), constructs the heuristic only once (Bonet & 
Geffner, 1999). This approach resembles GRT, although HSPr constructs the heuristic forward and searches backwards. Both approaches have the problem of incomplete goal states, however it arises in different phases of the planning process. GRT faces this problem in the pre-processing phase, by enhancing the goals, as it has been described in Section 3. In HSPr, the problem arises in the search phase, in the form of invalid states in the regression state space. To cope with the problem, HSPr computes mutual exclusion relations and checks each state in the regression state space for any 