# Efficient Implementation Of The Plan Graph In Stan

## Derek Long

Maria Fox Department of Computer Science University of Durham, UK
D.P.LONG@DUR.AC.UK
MARIA . FOX ✅ DUR . AC . UK

## Abstract

STAN is a Graphplan-based planner, so-called because it uses a variety of STate ANalysis techniques to enhance its performance. STAN competed in the AIPS-98 planning competition where it compared well with the other competitors in terms of speed, finding solutions fastest to many of the problems posed. Although the domain analysis techniques STAN exploits are an important factor in its overall performance, we believe that the speed at which STAN solved the competition problems is largely due to the implementation of its plan graph. 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 fix point. This paper describes the implementation of STAN's plan graph and provides experimental results which demonstrate the circumstances under which advantages can be obtained from using this implementation.

## 1. Introduction

STAN is a domain-independent planner for STRIPS domains, based on the graph construction and search method of Graphplan (Blum & Furst, 1997). Its name is derived from the fact that it performs a number of preprocessing analyses, or STate ANalyses, on the domain before planning, using the Type Inference Module Tim described by Fox and Long (1998).

STAN competed in the AIPS-98 planning competition and achieved an excellent overall performance in both rounds. The results of the competition, which can be found at the URL given in Appendix A, show that STAN was able to solve some problems notably quickly and that it could find optimal parallel solutions to some problems which could not be solved optimally by any other planner in the competition, for example in the Gripper domain. The problems posed in the competition did not give STAN much opportunity to exploit its domain analysis techniques, so this performance is due mainly to the underlying implementation of the plan graph that STAN constructs and searches. A more detailed discussion of the competition, from the competitors' point of view, is in preparation.

The design of STAN's plan graph is based on two insights. 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. In order to best exploit the bit vector representation of information we construct a two-layer graph called a spike which avoids unnecessary copying of data and allows layer-dependent information about a node to be clearly separated from layerindependent information about that node. The spike allows us to record mutex relations