Source-linked AI summary
Efficient Implementation of the Plan Graph in STAN
M. Fox, D. Long
TL;DR
Plan-graph layers add little new information at each stage, but their contents must be copied into new layers. The paper presents representation changes including avoiding explicit construction beyond the buffer, and reports improved planner efficiency through lower overhead in identifying failing goal sets.
Problem
Plan-graph layers add little new information at each stage, yet information must be copied into every new layer.
Source: p. 3Method
The paper presents two plan-graph representation improvements, including avoiding explicit construction of layers beyond the buffer.
Source: p. 24, . Conclusion · p. 28Results
The implementation improves planner efficiency by reducing overhead in identifying failing goal sets.
Source: p. 8Takeaways & Limitations
The plan-graph representation changes address both layer construction and the overhead of identifying failing goal sets.
Source: pp. 8, 24, . Conclusion · p. 28In this domain, STAN is forced to take exponential time in the size of instances.
Source: p. 26
Abstract
from arXiv · showhide
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.
App endix A. W ebsite Addresses
Appendix A lists online resources for the paper’s domains, software, competition results, and STAN website.
- The online appendix provides the domains and problems used in the paper, STAN binaries, and a file describing how the graph-construction version of IPP was generated.Source: App endix A. W ebsite Addresses · p. 29
- The AIPS-98 planning competition results are available online.Source: App endix A. W ebsite Addresses · p. 29
- The St an website can be found at http://www.dur.ac.uk/\u0018dcs0www/ researc h/stans tuff/pla npage.h tml.Source: App endix A. W ebsite Addresses · p. 29