being equal). Then the type associated with V2 can be seen to be a super-type of the type associated with V1 . Definition 4 A type structure is a hierarchy of types organised by sub-type relationships between the component types.

Definition 5 A type structure is adequately discriminating if objects are only assigned to state (and attribute) spaces that characterize their state transitions (and attributes).

Definition 6 A type structure is under-discriminating if it fails to distinguish types that are functionally distinct.

Definition 7 A type structure is over-discriminating if functionally identical objects are assigned to different types.

There are two distinct ways in which types play a role in the specification of a domain.

They can restrict the set of possible operator instances to eliminate all those that are meaningless in the domain and hence improve efficiency by reducing the size of the search space, and they can eliminate unsound plans that could be constructed if they were not provided.  The following examples clanfy the difference between these two roles.  The uty ped  sche ma:

| drive( X,Y,Z)   |
|-----------------|
| Pre:            |
| Ad:             |
| Del:            |

| at (X, Y),                | fuelled (X), location(Z)   |
|---------------------------|----------------------------|
| at (X, Z).                | unfuelled (X)              |
| at (X, Y),    fuelled (X) |                            |

permits more instances than the typed schema:

| drive( X,Y,Z)   |
|-----------------|
| params:         |
| Pre:            |
| Ad:             |
| Del:            |

| X:rocket, Y:package, Z:location            |               |
|--------------------------------------------|---------------|
| at (X, Y),    fuelled (X),    location (Z) |               |
| at (X, Z).                                 | unfuelled (X) |
| at (X, Y),    fuelled (X)                  |               |

but all meaningless instances will be eliminated during search because their preconditions will not be satisfiable. On the other hand, the typed schema:

| fly( X, Y, Z)   |                         |
|-----------------|-------------------------|
| params:         | X:aircraft,Y,Z:location |
| at (X,Y)        |                         |
| Pre:            |                         |
| Ad:             | at (X , Z)              |
| Del:            | at (X, Y)               |

ensures that only aircraft can be flown, whilst the untyped schema: