Least-Cost Flaw Repair: A Plan Refinement Strategy for Partial-Order Planning

David Joslin, Martha E. PollackAAAI 1994

Introduction

In Partial-Order Causal Link (POCL) planning, an agent constructs a plan by iteratively resolving "flaws." These flaws are categorized as either open conditions (goals or preconditions not yet satisfied) or threats (actions that potentially interfere with existing causal links). A critical decision for any POCL planner is the order in which these flaws are addressed.

Historically, planners like UCPOP employed a rigid "threats-first" heuristic. While later strategies suggested delaying "unforced" threats, these approaches remained largely heuristic. This paper introduces Least-Cost Flaw Repair (LCFR), a principled strategy that treats all flaws uniformly and prioritizes them based on the immediate branching factor they impose on the search space.

Methodology: Least-Cost Flaw Repair

The LCFR strategy is rooted in the principle of "least-commitment." Instead of prioritizing flaws by type (threat vs. open condition), LCFR selects the flaw that is most "constrained."

  1. Repair Cost Calculation: For every active flaw in a partial plan, the planner calculates the number of possible ways to resolve it. This count represents the number of successor nodes that would be generated in the search tree.
  2. Minimum Branching Selection: The planner always selects the flaw with the lowest repair cost. By resolving the most constrained flaws first, the search space is pruned early, preventing the exponential growth associated with high-branching choices.

To mitigate the computational overhead of calculating repair costs at every node, the authors also propose Quick LCFR (QLCFR). This variant estimates the cost once upon flaw discovery, significantly improving execution speed while maintaining much of the search efficiency.

Experimental Evaluation

The authors evaluated LCFR against several baseline strategies, including UCPOP and various threat-delaying variants (DUnf, LCOS), across a suite of 49 test problems from 15 distinct domains. These domains included standard benchmarks like the Briefcase world and Blocks world, as well as the more complex TileWorld, which features high branching factors.

Success rates across various planning domains.

As shown in the domain breakdown, LCFR demonstrates superior robustness, particularly in challenging environments like TileWorld and the STRIPS robot world, where traditional strategies often fail.

Key Results and Discussion

The experimental results highlight a significant improvement in both problem-solving capacity and search efficiency. LCFR solved 44 out of 49 problems, compared to only 32 for the standard UCPOP strategy.

Cumulative performance of different planning strategies showing percent of problems solved versus nodes examined.

Search Space Efficiency

Figure 1 illustrates that LCFR consistently finds solutions while examining fewer nodes than its competitors. In the TileWorld domain, LCFR solved a problem after generating only 73 partial plans, whereas UCPOP failed to find a solution within an eight-hour limit. This confirms that the branching factor, rather than flaw type, is the primary driver of search complexity.

Uniformity and Branching

A key insight from this work is that threats are not inherently "special." The perceived benefit of previous threat-delaying strategies likely stemmed from an implicit, though inconsistent, preference for low-cost repairs. By making this preference explicit and uniform across all flaw types, LCFR achieves more reliable performance.

Conclusion and Future Work

Least-Cost Flaw Repair provides a simple, principled approach to flaw selection in POCL planning. By focusing on minimizing the immediate branching factor, it significantly reduces the search effort required for complex problems. Future research may explore more sophisticated "look-ahead" mechanisms to estimate the long-term cost of repairs or improved tie-breaking strategies when multiple flaws share the same minimum cost.

Summary updated

BibTeX
@inproceedings{joslin1994least,
  author = {David Joslin and Martha E. Pollack},
  title = {{Least-Cost Flaw Repair: A Plan Refinement Strategy for Partial-Order Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure