As in Graphplan, an action instance is applicable in a rank if all of its preconditions are present and non-mutex in the previous rank. The way in which preconditions are tested for mutual exclusion in S T A N is based on our bit vector representation of fact mutex relations.

We take the logical or of all of the fact mutex vectors of the preconditions, and logically and the result with the precondition vector of the action. If the result is non-zero then there are mutex preconditions and the action is not applicable. This test corresponds to checking whether the action being considered is mutex with itself - a condition we define as being self-mutex.

Definition 8 An action a, with preconditions a p 1 . a pm, is self-mutex if:
( mvec ( a p 1 ) V mvec ( p 2 ) V ... V mvec ( a pm )) ∧ precs_of ( a )

## Is Non-Zero.

An applicable action is enacted by adding an action header to the new rank and setting its name to the name of the action and its bit mask to record its position in the spike.

In Figures 2 and 3 no-ops are given the names of the facts they achieve and are identified as no-ops by the flag components of their headers. We allocate space for the action level package and create and set its pres, adds and dels vectors. We then add any new facts on the add list of the action to the corresponding new fact rank. The addition of new facts req uires new fact headers to be initialised.

We then identify mutex actions and mutex facts in the new ranks. Mutex actions are identified in two phases. Actions which were non-mutex in the previous rank remain non-mutex and are not considered at this stage. First, existing action mutex relations are checked to see whether they hold in the new rank. Second, new action mutex relations must be deduced from the addition of new actions in the construction of this rank. We first consider the existing action mutex relations.

Two actions are mutex, as in Graphplan, if they have conflicting add and delete lists, conflicting precondition and delete lists or mutex preconditions. In the first two cases the actions are directly, or permanenily, mutex and never need to be re-tested although their mutex relationship must be recorded at each rank. In the third case the actions are indirectly, or temporarily, mutex and must be retried at subsequent ranks. We keep track of which actions to retry in order to avoid unnecessary retesting. We confirm that two actions, a and b, which were temporarily mutex in the previous rank are still temporarily mutex using the following logical operations on the fact mutex vectors for the action preconditions.

We first logically or together the mutex vectors for a's preconditions then and the result with the precondition vector for b. If the result is non-zero then a and b are mutex. This procedure, which is expressed concisely in Definition 9, is identical to that for checking whether an action is self-mutex except that, in this case, the result of oring the fact mutex vectors of the preconditions of one action is anded with the precondition vector of the other action. Since mutex relations are symmetric it is irrelevant which action plays which role in the test.

Definition 9 Two actions a (with n preconditions a p 1..a pn ) and b are temporarily mutex ij
( mvec ( a p 1 ) V mvec ( a p 2 ) V … V mvec ( a pn )) A precs of ( b )