robol is always in exactly one room but this cannot be inferred using the techniques so far described. In fact, this is an axiom about the world, or domain, rather than specific objects within it, and has to be obtained from information other than the state transformations of the objects.

It can be seen from the operator schemas for the Gripper domain that at robot 1 is balanced. That is, it is always deleted whenever it is added and added whenever it is deleted.

This means that the number of occurrences of at robot in the initial state determines the nmber of occurrences that are possible in any subsequent state. This leads to the construction, for this domain, of the invariant

## X : At_Robot(X)

= 1 ssince there is only one at robot relation in the initial state. The form of fixed resource invariants is always equational. Such an invariant states that the size of the set of combinations of objects satisfying a certain predicate is equal (or, in some cases, less than or equal) to a certain positive integer. Because this integer can be very large it is more convenient to write an equation than it would be to write a logical expression. The information encoded in the fixed resource invariants is very useful for identifying unsolvable goal sets without attempting to plan for them. For example, in the ICPARC version of the three-blocks Blocks world (Liatsos & Richards, 1997), in which there are only three table positions, there must always be exactly three clear surfaces. Any goal specifying more than three clear relationships can be identified as unachievable from the fixed-resource invariants for that domain.

The fixed-resource and uniqueness invanants produced by TIM can be seen as providing a form of multi-mulex relations, in contrast to the binary mutex relations inferred during the construction of the plan graph in Graphplan-based planners (Blum & Furst, 1995). Binary mutex relations indicate that two actions or facts are mutually incompatible, whilst multimutex relations indicate that larger groups of actions or facts are collectively incompatible. Binary mutex relations, preventing a fact that can be true of only one object from holding of two different objects simultaneously, can be extracted from the identity invariants that TIM Infers. Multi-mutex relations are more powerful than binary ones. STAN can detect usolvable goal-sets by using the fixed-resource and uniqueness invariants even when the binary mutex relations at the corresponding level do not indicate that any problem exists.

To infer these invanants we examine the predicates in the language to see whether they are exchanged on the add and delete lists of the operator schemas. If a predicate is exchanged equally in all schemas (it always appears the same number of times on the add list as on the delete list of a schema) then the predicate corresponds to a fixed resource.

lf a single schema upsets this balance then the predicate is not treated as fixed. Given a fixed resource predicate, it can be inferred that there can never be more combinations of objects satisfying that predicate than there are in the initial state. Because of the slightly odd encoding of the rocket world considered in this paper, only location is a fixed resource. at is not fixed because it is not equally exchanged in the load schema. Examples of fixed resource invariants inferred from various standard domains are provided in Appendix C.

There are certain circumstances under which it is necessary to infer the weaker invariant t hat