and dels corresponds to an index into the fact array and is set in precs if the fact at that index is a precondition (and unset otherwise), in adds if the fact at that index is an add list element (and unset otherwise) and in dels if the fact at that index is a delete list element of the action (and unset otherwise).

Definition 4  A fact mutex vector (FMV) for a fact, f, is a spike vector in which the bits correspond to the indices into the fact array and a bit is set if the corresponding fact is mutex with f Definition 5 An action mutex vector (AMV) for an action, a, is a spike vector in which the bits correspond to the indices into the action array and a bit is set if the corresponding action is mutex with a Definition 6 A fact level package for a fact, f, is an array of pairs, one for each rank in the spike, each containing a fact mutex vector for f and a vector of achievers, called the achievement vector (AV), in the previous action rank.

Definition 7 An action level package for an action, a, is an array of triples, one for each rank in the spike, each containing an action mutex vector for a and a list of actions mutex with a (MAs).

Using these definitions we can now provide a detailed description of the spike construction process.

## 2.1 The Spike Construction Process

We will make use of these header access functions in the following discussion:
mvec :  fact →  fact mutex vector precs of : action → precs adds of : action → adds dels of : action → dels The spike construction process takes place within a loop which stops when all goals are pairwise achievable, and thereafter alternates with search until the fix point is reached and the wave front mechanism takes over. The use of the wave front is discussed in Section 4.

The key component of the process is the rank construction algorithm which builds a fact rank and an action rank by extending the previous fact and action ranks in the spike. The action rank is started by adding no-ops for each of the fact headers in the previous fact rank. As soon as these are added, the fact headers can be updated to refer, by index into the action rank, to their achieving no-ops. This information allows STAN to give preference, when searching, to plans that use the no-op to achieve a goal rather than some other achiever. In Graphplan this preference was ensured by keeping all of the no-ops at the top of the graph layers and considering the achievers in order during search.

All possible action instances are then considered. All applicable action instances are enacted and then removed so that they will never be reconsidered for enactment. We then identify mutex relations between the actions in the new action rank, and between facts in the new fact rank.