
| Fact        | Distance from Goals   | Related Facts   |
|-------------|-----------------------|-----------------|
| (at R n2_0) | 0                     | ( )             |
| (at K n2_2) | 0                     | ( )             |
| (at R n1_0) | 1                     | ( )             |
| (at R n0_0) | 2                     | ( )             |
| (at R n0_1) | 3                     | ( )             |
| (at R n2_1) | 1                     | ( )             |
| (at R n2_2) | 2                     | ( )             |
| (in R K)    | 3                     | ( (at R n2_2) ) |
| (at R n1_2) | 3                     | ( )             |
| (at K n1_2) | 7                     | ( (at R n1_2) ) |
| (at R n0_2) | 4                     | ( )             |
| (at K n0_2) | 8                     | ( (at R n0_2) ) |

Initially the planner does not select the optimal action, since it leads to a state with a greater distance from the goals, according to the heuristic. In order to decide to move the robot towards the key, the planner should go through all the other valid plans, then backtrack and move the robot to worse states (this requires that the planner maintains a closed list of visited states and does not revisit them). In difficult problems, the number of states that the planner has to visit before following the optimal direction, is extremely large. This is the main reason why GRT, like many other heuristic planners, does not handle *grid*-like domains efficiently. 

For the 3x3 *grid* problem of Figure 2, an ideal planner should detect that, in order to move the key from n0_2 to *n2_2*, it is necessary that the robot gets the key, so the fact (at R *n0_2*) should be achieved before the fact (at R *n2_0*). However, the planner does not know that the facts (*at R* n0_0), (at R *n2_0*) and (at R *n0_2*) are related in some way, because the domain definition does not provide this piece of information. Therefore, it is necessary to provide the planner with information about relations that hold between the facts of the problem.

## 5.2 Defining Xor-Constraints

In order to avoid local optimal states, we provide GRT with knowledge of relations between facts, where exactly one of the facts can hold in each state. We call these relations XOR-constraints.

Definition 2 (XOR-constraint). An XOR-constraint is a relation between ground facts. The relation is valid in a state, if exactly one of the participating facts holds in that state.

The general form of an XOR-constraint schema is the following:
((*xor f*1 f2 ...) c1 c2 ...)
where fi are the facts that cannot co-appear in any state and ci are static facts that provide supplementary conditions such as type constraints, relations between objects, etc.

XOR-constraints can be formalized for almost any domain. For example, in the *logistics* domain we could define the following XOR-constraints:
( (*xor ( at ?Truck ** ) ) ( *truck ?Truck* ) )
( (*xor ( at ?Plane ** ) ) ( *plane ?Plane* ) ) ( (xor ( *at ?Package ** ) (*in ?Package ** ) ) ( package *?Package* ))