needed to solve the original problem. Note, however, that this decomposition may lead to loss of completeness. In domains where no deadlock exists, some solutions may be pruned. In domains where deadlocks do exist, the decomposition may produce unsolvable sub-problems. In order to maintain completeness, the algorithm should backtrack to all the possible inverted actions that could achieve the facts in the Pre-Processing Algorithm, even those with large application costs. 

However, due to the combinatorial explosion problem, this approach is not adopted by GRT.

A usual situation is the case where the sub-problems need further decomposition. This situation arises in two cases. The first is when two objects need each other to achieve their goals, as in the case of *grid* domain, with the keys and the robot, and the second case is when there is a sequential interaction between three or more objects. In these cases, the ordering graph of the initial problem encodes one aspect of the interaction, while the ordering graphs of the sub-problems encode other aspects. However, in order to avoid infinite decompositions, a cutoff level is defined.

## 6. The Grt Operation

GRT has been implemented in C++5. Its operation consists of several stages, which are shown in Figure 6a.

![0_image_0.png](0_image_0.png)

In the first stage the domain and problem files are parsed and the initial data structures are constructed. The second stage consists of computing the facts and the actions of the problem. The facts are stored in a tree structure, which is indexed by their predicates and their objects and allows for fast access, while the actions are stored in a linked list. Moreover, multiple pointers connect each fact with the actions, where the fact appears. The computation of the facts and actions is performed incrementally, by repeatedly applying the following steps:
 If a fact has been reached, create new actions that include this fact and others already reached, in their preconditions.

 If an action has been created, add its add effects in the tree structure.

The process starts with the initial state facts and continues until no more facts and actions can be reached. This approach is time efficient and succeeds in not generating many unreachable facts and actions. For example, in the *logistics* domain, the facts denoting that a truck is located in a city 