Packages can be at locations or in rockets, and can move between these states in the resulting two-node FSM. In this example, rockets can be in states that involve more than one FSM, since they can be both at and fuelled, or at and unfuelled. STRIPS domains have been seen in this way in earlier work (McCluskey & Porteous, 1997; Grant, 1996), as discussed in Section 5.

## 2.1  Types In Tim

When twoobjects participate in identical FSMs they are functionally equivalent and can be seen to be of the same type. The notion of type here is similar to that of sorts in the work of McCluskey and Porteous (1997). A primary objective of the TIM module is to automatically identify the equivalence classes that form the primitive types in a domain description and to infer the hierarchical type structure of a domain on the basis of the primitive types. The way this is done is discussed in Section 2.3. The primitive types are functional equivalence classes, and the objects of the domain are partitioned into these classes. Having identified the types of the domain objects TIM infers the types of the parameters of all of the operators.

State invariants are inferred as a final stage.

The early parts of this process rely on three key abstract data types, the properly space, the attribute space and the transition rule. Formal definitions of these components are provided in Section 2.3, but we provide informal descriptions here to support the following definitions. Transition rules represent the state transformations that comprise the FSMs traversed by the objects in the domain. Properly spaces are FSMs, together with the objects that participate in them, the properties these objects can have and the transition rules by which they can acquire these properties. Allribute spaces contain collections of objects that have, or can acquire, the associated attributes. Attributes differ from properties because they can be acquired, or lost, without the associated loss, or acquisition (respectively),
of another attribute. Attribute spaces also contain the transition rules that enable the acquisition (or loss) of these attributes. Once the state and attribute spaces have been constructed we assign types to the domain objects according to their membership of the property and attribute spaces. Any two objects that belong in identical property and attribute spaces will be assigned the same type. It is therefore very important to ensure that the property and attribute spaces are adequately discriminating, otherwise important type distinctions can be lost. Much of the subtlety of the algorithm described in Section 2.2 is concerned with maintaining adequate discrimination in the construction of these spaces.

We present the following definitions here to support our informal characterisation of the roles of types in strips and in tim. The definitions are used againin Sections 2.4 and  2.6, w hich discuss how types are assigned to objects and operator parameters. Definition 1 A type vector is a bit vector in which each bit corresponds to membership, or otherwise, of a unique state or attribute space. The number of bits in the vector is always equal to the number of distinct state and attribute spaces.

Definition 2 A type is a set of domain objects each associated with the same type vector. Definition 3 A type vector, Vi, in which two distinct bits, si and si, are set corresponds to a sub-type of the type associated with a vector, V 2 , in which only s, is set (all other settings