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:
- Abstract Solve: A skeletal plan is generated in the most abstract space.
- Refine: The intermediate states of the abstract plan serve as "milestones" or sub-goals for the next level.
- Sub-divide: The gaps between these milestones are solved at the next, more detailed level of the hierarchy.
- Repeat: This process continues until a complete plan is formed in 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.
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