Journal of Artificial Intelligence Research, 6 (1997) 1-34. Submitted 2/97; published 6/97

© 1997 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.

Flaw Selection Strategies For Partial-Order Planning

Martha E. Pollack
Department of Computer Science and Intelligent Systems Program,
University of Pittsburgh, Pittsburgh, PA 15260 USA
pollack@cs.pitt.edu

David Joslin
Computational Intelligence Research Laboratory,
University of Oregon, Eugene, OR 97403 USA
joslin@cirl.uoregon.edu

Massimo Paolucci
Intelligent Systems Program,
University of Pittsburgh, Pittsburgh, PA 15260 USA
paolucci@pitt.edu

Abstract:

Several recent studies have compared the relative efficiency of alternative flaw selection strategies for partial-order causal link (POCL) planning. We review this literature, and present new experimental results that generalize the earlier work and explain some of the discrepancies in it. In particular, we describe the Least-Cost Flaw Repair (LCFR) strategy developed and analyzed by Joslin and Pollack (1994), and compare it with other strategies, including Gerevini and Schubert's (1996) ZLIFO strategy. LCFR and ZLIFO make very different, and apparently conflicting claims about the most effective way to reduce search-space size in POCL planning. We resolve this conflict, arguing that much of the benefit that Gerevini and Schubert ascribe to the LIFO component of their ZLIFO strategy is better attributed to other causes. We show that for many problems, a strategy that combines least-cost flaw selection with the delay of separable threats will be effective in reducing search-space size, and will do so without excessive computational overhead. Although such a strategy thus provides a good default, we also show that certain domain characteristics may reduce its effectiveness.

 
• Introduction
• Background
  • Node and Flaw Selection
  • Notation
• Flaw Selection Strategies
  • Threat Preference and Delay
  • Least-Cost Flaw Repair
  • Threat Delays Revisited
• Experimental Comparison of Flaw Selection Strategies
  • Experimental Design
  • The Value of Least-Cost Selection
  • Comparing LCFR and ZLIFO
  • The Value of Separable-Threat Delay
  • The Need for Domain Information
    • The Tileworld Problems
    • The Trains and Get-Paid Problems
  • Computation Time
• Conclusion
• References
• About this document ...