Efficient implementation of the plan graph in STAN

STAN is a Graphplan-based planner, so-called because it uses a variety of S Tate ANalysis techniques to enhance its performance. STAN competed in the A IPS-98 planning competition where it compared well with the other competito rs in terms of speed, finding solutions fastest to many of the problems pos ed. 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 opera tions on bit vectors, and that the graph should not be explicitly construct ed beyond the fix point. This paper describes the implementation of STAN's plan graph and provides experimental results which demonstrate the circumst ances under which advantages can be obtained from using this implementation .