Abstract
This paper presents SNLP+EBL, the first implementation of explanation-based learning (EBL) techniques for a partial order planner. We describe the basic learning framework of SNLP+EBL, including regression, explanation propagation, and rule generation. We then concentrate on SNLP+EBL's ability to learn from failures and present a novel approach that uses stronger domain and planner-specific consistency checks to detect, explain, and learn from the failures of plans at depth limits. We conclude with an empirical evaluation of the efficacy of this approach in improving planning performance.
Introduction
In the early 1990s, automated planning faced significant computational hurdles. While Partial Order (PO) planners—which operate by adding constraints to a partial plan rather than moving through discrete states—offered theoretical efficiency gains over state-space planners, their search spaces remained prohibitively large. Explanation-Based Learning (EBL) had previously been successful in speeding up state-space planners by analyzing failures to create search control rules. However, adapting EBL to PO planning presented two major challenges: the lack of a formal regression procedure for plan-space decisions (like causal links and orderings) and the prevalence of "silent failures" where planners hit depth limits without a clear logical contradiction to explain.
The SNLP+EBL Framework
SNLP+EBL extends the Sistine Nonlinear Planner (SNLP) by integrating a learning component that operates during the search process. The system focuses on three core mechanisms:
1. Constraint-Based Regression
Unlike state-space planners that regress over operators, SNLP+EBL regresses failure explanations over plan-space constraints. This includes tracking how step additions, promotions, and demotions contribute to a failure. When a branch of the search tree fails, the system identifies the minimal set of constraints responsible and propagates this explanation back up the tree to generate a generalized search control rule.
2. Learning from Depth-Limit Failures
A significant contribution of this work is the handling of "hidden" failures. In many domains, a planner might explore a path that is physically impossible but logically consistent within the current partial plan constraints until a depth limit is reached. To address this, the authors introduced NP-conditions (Necessarily Preservable Conditions)—conditions that must remain true for a plan step to be valid.
When a depth limit is hit, SNLP+EBL applies "strong consistency checks" using domain axioms. For example, in the Blocks World, an axiom might state that a block cannot simultaneously be "clear" and have another block "on" it. If the NP-conditions of a partial plan violate these axioms, the system can explain the depth-limit failure as a physical impossibility, allowing it to learn a control rule that prunes similar branches earlier in future searches.
Experimental Evaluation
The system was evaluated using randomly generated problems in the Blocks World domain, ranging from 3 to 8 blocks with varying goal complexities. The performance of the base SNLP planner was compared against SNLP+EBL and SNLP+DOMAX (a version that uses axioms for pruning but does not learn rules).
Results
The empirical results demonstrated a dramatic improvement in both success rates and computational efficiency. In a test set of 30 problems, the base SNLP planner solved only 60% of cases within the time limit, whereas SNLP+EBL achieved a 100% success rate.
As shown in the performance curves, SNLP+EBL significantly reduced the cumulative CPU time (dropping from 1767 seconds to 195 seconds in one test set). Notably, SNLP+EBL outperformed SNLP+DOMAX, indicating that the overhead of applying learned rules is significantly lower than the cost of repeatedly evaluating complex domain axioms during search.
Conclusion
SNLP+EBL represents a milestone in integrating EBL with partial order planning. By shifting the focus from state-space transitions to plan-space constraints and utilizing domain axioms to explain depth-limit failures, the system effectively tames the search complexity of PO planners. Future work involves extending this framework to more modern planners and addressing the "utility problem" to ensure that the accumulation of learned rules does not eventually degrade performance.
Summary updated