Introduction next up previous
Next: Background Up: Flaw Selection Strategies For Previous: Flaw Selection Strategies For  



Much of the current research in plan generation centers on partial-order causal link (POCL) algorithms, which descend from McAllester and Rosenblitt's (1991) SNLP algorithm. POCL planning involves searching through a space of partial plans, where the successors of a node representing partial plan P are refinements of P. As with any search problem, POCL planning requires effective search control strategies.

In POCL planning, search control has two components. The first, node selection, involves choosing which partial plan to refine next. Once a partial plan has been selected for refinement, the planner must then perform flaw selection, which involves choosing either a threat to resolve or an open condition to establish.

Over the past few years, several studies have compared the relative efficiency of alternative flaw selection strategies for POCL planning and their extensions [Peot & Smith 1993, Joslin & Pollack 1994, Srinivasan & Howe 1995, Gerevini & Schubert, 1996, Williamson & Hanks, 1996]. These studies have been motivated at least in part by a tension between the attractive formal properties of the POCL algorithms, and the limitations in putting them to practical use that result from their relatively poor performance. To date, the POCL algorithms cannot match the efficiency of the so-called industrial-strength planners such as SIPE [Wilkins, 1988, Wilkins & Desimone, 1994] and O-Plan [Currie & Tate, 1991, Tate, Drabble & Dalton, 1994]. Flaw selection strategy has been shown to have a significant effect on the efficiency of POCL planning algorithms, and thus researchers have viewed the design of improved flaw selection strategies as one means of making POCL planning algorithms more practical.

In this paper, we review the literature on flaw selection strategies, 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 ZLIFO strategy (1996). 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.

next up previous
Next: Background Up: Flaw Selection Strategies For Previous: Flaw Selection Strategies For

TOM Conversion
Wed Jun 25 17:40:58 EDT 1997