successive fact layer after the layer in which they first appeared. Although the layers can get deeper at every successive stage they each duplicate information present in the previous layer, so there is only a small amount of new information added at every stage. The proportion of new material, relative to copied material, decreases progressively as the graph develops.

In the original Graphplan, mutex relations were checked for by maintaining lists of facts, corresponding to the pre- and post-conditions of actions, and checking for membership of facts within these lists. Because of the need to copy information at each new layer, the preand post-conditions of actions were duplicated even though this information did not vary from layer to layer (it can be determined once and for all at the point of instantiation of the schema). It is possible to identify layer-independent information, with each node in the graph, which can be stored just once using a different representation of the graph structure.

The spike representation reimplements the graph as a single fact array, called the faci spike, and a single action array, called the action spike, each divided into ranks corres ponding to the layers in the original Graphplan graph structure. The observations leading to this compressed implementation of the plan graph were made independently by Smith and Weld (1998). In STAN, a fact rank is a consecutive sequence of fact headers storing the layerindependent information associated with their associated facts in the corresponding fact layer. Similady, an action rank is a consecutive sequence of action headers storing layerindependent information about their associated actions in the corresponding action layer.

Each header is a tuple containing, amongst other things, the name of the fact or action it is associated with and a structure which stores the layer-dependent information relevant to that fact or action. In the case of fact headers this structure is called a fact level package and in the case of action headers it is an action level package. Figure 1 shows how a simple graph structure can be viewed as a spike.

In the spike the positions of all fact and action headers are fixed and can be referred to by indexing into the appropriate array. At any point, the sizes of the arrays are referred to using the constant MaxSize, a large number setting an upper bound on the size of the spike. All of the vectors allocated are also initialised to this size, although they are used in word-sized increments. This saves the effort of re-allocating and copying vectors as the spike increases in size towards MaxSize. We now define the data types so far introduced.

Definition 1 A spike vector is a bit vector of size MaxSize. Definition 2 A fact header is a tuple of six components: a name which is the predicate and arguments that comprise the fact itself; an index, i, giving the position of the fact in the fact array; a bit mask which is a spike vector in which the ith bit is set and all other bits are unset; a reference identifying its achieving no-op; a spike vector consumers with bits set for all the actions which use this fact as a precondition and a fact level package storing the layer-dependent information about that fact.

Definition 3 An action header is a tuple of eight components: the name of the action; an index, i, giving the position of the action in the action array; a bit mask which is a spike vector in which the ith bit is set and all other bits are unset; a flag indicating whether the action is a no-op; three spike vectors, called precs, adds and dels and an action level package storing the layer-dependent information about that action. Each bit in precs, adds