Search Reduction in Hierarchical Problem Solving

Craig A. KnoblockAAAI 1991

Introduction

In classical artificial intelligence, planning—the process of finding a sequence of actions to reach a goal—is notoriously difficult. The search space typically grows exponentially with the length of the solution, a phenomenon known as the "combinatorial explosion." While hierarchical approaches—solving a simplified version of a problem before filling in details—have long been hypothesized to mitigate this, formal complexity analysis and broad empirical evidence were previously lacking.

Craig Knoblock's research addresses this gap by providing the first rigorous analytical and empirical proof that hierarchical problem solving can transform search complexity from exponential to linear. By decomposing large problems into abstract subproblems, solvers can navigate complex domains like robot planning and scheduling with significantly greater efficiency.

Methodology: Abstraction Spaces

The core of this approach lies in Abstraction Spaces. Instead of searching directly in the "ground space" (the full, detailed problem), the solver utilizes a hierarchy of spaces. Each level represents a simplified version of the level below it, typically created by removing specific details or "literals."

The hierarchical solving process follows a structured refinement cycle:

  1. Abstract Solve: A skeletal plan is generated in the most abstract space.
  2. Refine: The intermediate states of the abstract plan serve as "milestones" or sub-goals for the next level.
  3. Sub-divide: The gaps between these milestones are solved at the next, more detailed level of the hierarchy.
  4. Repeat: This process continues until a complete plan is formed in the ground space.
The hierarchical refinement process illustrated using the Tower of Hanoi domain, showing transitions from abstract spaces to the ground space.

To automate this, the ALPINE system generates abstraction hierarchies, which are then executed by the PRODIGY planner. Knoblock's complexity analysis compares standard single-level search ($O(b^l)$) to this multi-level approach.

Experimental Evaluation

The paper evaluates hierarchical search across three distinct domains: the Tower of Hanoi, Extended STRIPS Robot Planning, and Machine-Shop Scheduling. The Tower of Hanoi serves as an "ideal" case with a perfectly regular mathematical structure, while the others represent more complex, real-world style benchmarks.

Key Results

In the Tower of Hanoi domain, empirical results perfectly align with theoretical predictions. As shown in Figure 2, search time for the non-hierarchical solver explodes exponentially as disks are added. In contrast, the hierarchical solver's CPU time grows linearly.

CPU time comparison between standard Prodigy and Hierarchical Prodigy in the Tower of Hanoi domain, demonstrating the shift from exponential to linear complexity.

In more complex domains like robot planning and machine-shop scheduling, Hierarchical PRODIGY significantly outperformed the standard version. While the standard planner often timed out after 10 minutes on harder problems, the hierarchical version found solutions quickly. Furthermore, hierarchical solutions were approximately 10% shorter, as the abstraction forced the solver to prioritize high-level goals and avoid unnecessary search "wandering."

Key Insights

  • Linear Complexity: Under ideal conditions—where problems decompose into constant-sized subproblems—search complexity drops from $O(b^l)$ to $O(l)$.
  • The Role of Backtracking: For perfect linear reduction, the solver must avoid backtracking across hierarchy levels. If an abstract choice makes a detailed solution impossible, efficiency gains are lost.
  • Abstraction as a Heuristic: Even in "messy" domains where ideal conditions aren't met, the hierarchy acts as a powerful heuristic, focusing the solver on critical constraints first.

Conclusion and Future Work

The effectiveness of this search reduction is highly dependent on the quality of the abstraction hierarchy generated by systems like ALPINE. While the results are promising, future work is needed to handle domains where "ordered monotonicity"—the principle that refining a plan won't invalidate abstract steps—is difficult to maintain. Additionally, addressing the costs of backtracking across levels remains a key challenge for applying these techniques to even broader classes of real-world problems.

Summary updated

BibTeX
@inproceedings{knoblock1991search,
  author = {Craig A. Knoblock},
  title = {{Search Reduction in Hierarchical Problem Solving}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure