Abstract
I highlight some inefficiencies of Graphplan's backward search algorithm, and describe how these can be eliminated by adding explanation-based learning and dependency-directed backtracking capabilities to Graphplan. I will then demonstrate the effectiveness of these augmentations by describing results of empirical studies that show dramatic improvements in run-time (w 100× speedups) as well as solvability-horizons on benchmark problems across seven different domains.
Introduction
In the late 1990s, Graphplan emerged as a state-of-the-art algorithm for classical planning. The algorithm operates in two distinct phases: first, it constructs a "planning graph"—a reachability structure that captures potential actions and their effects over time; second, it performs a backward search to extract a valid plan from this graph.
Despite its initial success, Graphplan’s backward search suffered from significant inefficiencies. Specifically, it relied on chronological backtracking, which often forced the search to revisit irrelevant choices after a failure. Furthermore, its memoization strategy was weak; it only remembered exact sets of failed goals, failing to recognize that a failure might be caused by a much smaller subset of those goals. This led to redundant efforts and a limited "solvability horizon" for complex problems.
Algorithmic Enhancements: EBL & DDB
To address these bottlenecks, this research integrates two classic AI search techniques into the Graphplan framework:
Dependency-Directed Backtracking (DDB)
Rather than stepping back one level at a time, DDB identifies a Conflict Set—the specific subset of assignments responsible for a search failure. By analyzing these dependencies, the algorithm can "backjump" directly to the most recent variable involved in the conflict, bypassing irrelevant intermediate choices that would otherwise be exhaustively searched.
Explanation-Based Learning (EBL)
When a search node fails, the algorithm computes a "generalized memo." This is the minimal set of goals that caused the impasse, determined through a process called regression. By propagating failure explanations upward through the planning graph, the planner learns that if a small group of goals is impossible, any larger set containing them is also doomed to fail.
Efficient Memo Retrieval
Because EBL produces many compact, highly applicable memos, checking if a current goal set contains a failed subset becomes a frequent and potentially expensive operation. To mitigate this overhead, the author utilizes UB-Trees (Universal B-Trees) for efficient subset matching, ensuring that the time saved during search is not lost to the cost of learning.
Experimental Evaluation
The augmented Graphplan was tested across seven standard planning benchmark domains, including Blocks World, Logistics, Gripper, and the Traveling Salesperson Problem (TSP). These benchmarks represent a diverse range of constraints and search space sizes.
Key Results
The empirical results demonstrate a transformative impact on performance:
- Dramatic Speedups: The EBL/DDB-enhanced Graphplan achieved up to 100-fold speedups on several benchmark problems.
- Reduction in Search Effort: The number of backtracks—the primary metric for search complexity—dropped significantly. In the
Rocket-ext-adomain, backtracks were reduced from over 8,000 to just 764. - Memo Utility: Memos generated via EBL were far more effective than standard ones. In the
Rocket-ext-bdomain, an EBL-generated memo pruned the search 101 times on average, compared to just 3.2 times for standard Graphplan memos.
Conclusion and Future Work
By treating search failure as a source of "negative information" to be generalized and remembered, this work pushes the solvability horizon of Graphplan. The techniques allow the planner to solve problems that would otherwise time out after hours of computation.
Future research directions include refining memo-forgetting strategies to manage the growth of stored knowledge and exploring inter-problem learning, where insights gained from one planning task can be transferred to accelerate the solution of another. Additionally, combining these "look-back" techniques with "look-ahead" strategies like dynamic variable ordering could yield even greater performance gains.
Summary updated