Efficient Implementation of the Plan Graph in STAN

The implementation is based on two insights: that many of the graph construction operations can be implemented as bit-level logical operations on bit vectors, and that the graph should not be explicitly constructed beyond the x point. A more detailed discussion of the competition, from the competitors' point of view, is in preparation. First, we observe that action pre-and post-conditions can be represented using bit vectors. Checking for mutual exclusion between pairs of actions which directly interact can be implemented using logical operations on these bit vectors. Mutual exclusion (mutex relations) between facts can be implemented in a similar way. Second, we observe that there is no advantage in explicit construction of the graph beyond the stage at which the x point is reached. Since no new facts, actions or mutex relations are added beyond the x point these goal sets can be considered without explicit copying of the fact and action layers. For example, using a heuristic discussed in Section 5.1, Sta In this paper we describe the spike and wave front mechanisms and provide experimental results indicating the performance advantages obtained. The layers correspond to snapshots of possible states at instants on a time line from the initial to the goal state.