Least-cost flaw repair: a plan refinement strategy for partial-order planning

Abstract

We describe the least-cost flaw repair (LCFR) strategy for performing flaw selection during partial-order causal link (POCL) planning. LCFR can be seen as a generalization of Peot and Smith's "Delay-Unforced Threats" (DUnf) strategy [Peot & Smith 1993]; where DUnf treats threats differently from open conditions, LCFR has a uniform mechanism for handling all flaws. We provide experimental results that demonstrate that the power of DUnf does not come from delaying threat repairs per se, but rather from the fact that this delay has the effect of imposing a partial preference for least-cost flaw selection. Our experiments also show that extending this to a complete preference for least-cost selection reduces search-space size even further. We consider the computational overhead of employing LCFR, and discuss techniques for reducing this overhead. In particular, we describe QLCFR, a strategy that reduces computational overhead by approximating repair costs.