Improving Graphplan's Search with EBL & DDB Techniques

Subbarao KambhampatiIJCAI 1999 · OpenReview

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.

Figure 1: The planning graph structure showing levels of actions and propositions, which serves as the basis for the backward search and regression of failure explanations.

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-a domain, 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-b domain, an EBL-generated memo pruned the search 101 times on average, compared to just 3.2 times for standard Graphplan memos.
Figure 3: Comparative performance table showing significant speedups and backtrack reductions across various benchmark domains.

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

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.
BibTeX
@inproceedings{kambhampati1999improving,
  author = {Subbarao Kambhampati},
  title = {{Improving Graphplan's Search with EBL \& DDB Techniques}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
  url = {https://openreview.net/forum?id=BJ-nvQGOWH},
}
Figure