Abstract
The ideas of dependency directed backtracking (DDB) and explanation based learning (EBL) have developed independently in the constraint satisfaction, planning, and problem-solving communities. In this paper, I formalize and unify these ideas under the task-independent framework of refinement search, which can model the search strategies used in both planning and constraint satisfaction. I show that both DDB and EBL depend upon a common theory of explaining search failures and regressing them to higher levels of the search tree. The relevant issues of importance include (a) how the failures are explained and (b) how many failure explanations are remembered. This task-independent understanding of DDB and EBL helps support cross-fertilization of ideas among the Constraint Satisfaction, Planning, and Explanation-Based Learning communities.
Introduction
In the mid-90s, the AI community was fragmented. Researchers in Constraint Satisfaction Problems (CSP) and those in Automated Planning were using similar "speedup" techniques but describing them in incompatible ways. The core issue was the inefficiency of chronological backtracking—the standard search method where, upon hitting a dead end, the engine simply moves back to the immediate previous decision.
This often leads to "thrashing," where the search engine repeatedly explores different branches that are all doomed by the same fundamental mistake made much earlier in the search tree. While DDB (jumping back to the source of the error) and EBL (remembering the error to avoid it later) existed, there was no task-independent way to understand how they related or how to implement them consistently across different types of problems.
The Refinement Search Framework
The author introduces a generalized template called Refinement Search to bridge this gap. In this model, search nodes represent sets of potential solutions defined by constraints. Refinement operators split these sets into smaller subsets by adding more constraints, such as assigning a value to a variable in CSP or adding a step to a plan in Planning.
When a node has no solutions, the system identifies a subset of constraints ($E$) that cause the inconsistency, known as a failure explanation. The "secret sauce" of this framework is Regression: a formal way to determine which constraints had to exist before a decision was made for a specific failure to manifest after the decision.
Unifying DDB and EBL
Through this framework, the paper demonstrates that DDB and EBL are not distinct algorithms but different ways of utilizing the same underlying failure explanations:
- DDB occurs when a failure explanation regresses "unchanged" over a decision. This proves the decision didn't cause the failure, allowing the search to "jump" further up the tree to the actual cause.
- EBL occurs when these failure explanations (often called "nogoods") are stored and used as rejection rules to prune future branches of the search tree that share the same problematic constraints.
By using regression, the author shows that complex "dependency graphs" are unnecessary for intelligent backtracking. If you have a declarative representation of decisions and failures, regression can derive the dependencies on the fly.
The Propagate Algorithm
The primary result of this formalization is the Propagate procedure. This algorithm provides a step-by-step method for regressing failure explanations, deciding when to perform a dependency-directed jump, and generating rejection rules to prune future search.
As a theoretical formalization paper, no empirical datasets or benchmarks were used. Instead, the author demonstrates the concepts using a walk-through of a specific CSP example and references existing systems like UCPOP-EBL to show how the theory maps to real-world implementations. The framework successfully models seemingly disparate algorithms from both the CSP and Planning literature, providing a "common language" for future AI research.
Limitations and Future Work
The author acknowledges that EBL is not a "free lunch." The utility problem remains a concern: storing too many failure explanations can slow down the search because the engine spends more time checking its memory than actually searching. Additionally, because there are often multiple ways to explain a failure, picking the "best" (usually the smallest or most general) explanation is a heuristic process that significantly impacts performance.
Ultimately, this paper provides a map for cross-fertilization: CSP could benefit from the "utility analysis" research in the ML community, while Planning could benefit from the advanced backtracking algorithms developed for CSPs.
Summary updated