Efficient Implementation of the Plan Graph in STAN

D. Long, M. Fox

Research output: Contribution to journalArticle

81 Citations (Scopus)

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.
LanguageEnglish
Pages87-115
Number of pages28
JournalJournal of Artificial Intelligence Research
Volume10
Publication statusPublished - 1999

Fingerprint

Planning

Cite this

@article{b8321bad2e494ffcb15e37dd3a8c8580,
title = "Efficient Implementation of the Plan Graph in STAN",
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.",
author = "D. Long and M. Fox",
year = "1999",
language = "English",
volume = "10",
pages = "87--115",
journal = "Journal of Artificial Intelligence Research",
issn = "1076-9757",

}

Efficient Implementation of the Plan Graph in STAN. / Long, D.; Fox, M.

In: Journal of Artificial Intelligence Research, Vol. 10, 1999, p. 87-115.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Efficient Implementation of the Plan Graph in STAN

AU - Long, D.

AU - Fox, M.

PY - 1999

Y1 - 1999

N2 - 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.

AB - 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.

UR - http://www.jair.org/papers/paper570.html

M3 - Article

VL - 10

SP - 87

EP - 115

JO - Journal of Artificial Intelligence Research

T2 - Journal of Artificial Intelligence Research

JF - Journal of Artificial Intelligence Research

SN - 1076-9757

ER -