A Hierarchical Planner that Generates Its Own Hierarchies

Jens ChristensenAAAI 1990

Abstract

Classical AI planning often suffers from exponential search space growth as task complexity increases. While hierarchical abstraction can mitigate this, traditional methods require manual encoding or suffer from "semantic cliffs" where details are either critical or entirely ignored. This paper presents PABLO, a nonlinear planner that automatically constructs abstraction hierarchies through predicate relaxation. By defining predicates as "satisfied" if they are achievable within a fixed number of steps, PABLO smooths transitions between abstraction levels and supports anytime planning with executable intermediate actions.

Introduction

In classical planning, the search space expands exponentially with the number of possible action sequences. Hierarchical planners address this by solving a simplified "big picture" version of the problem before refining the details. However, previous systems like NOAH required tedious manual abstraction definitions, and systems like ABSTRIPS used binary importance levels that often led to inefficient plans. PABLO introduces an automated approach to hierarchy generation that discovers importance based on the effort required to achieve specific states.

Methodology: Predicate Relaxation

The core innovation of PABLO is Predicate Relaxation. Instead of a predicate $P$ being strictly binary (true or false), PABLO constructs a hierarchy of relaxed versions ($P^n_{rel}$):

  • $P^0_{rel}$: The original, strict predicate.
  • $P^1_{rel}$: True if $P$ is already true OR if $P$ can be made true by applying a single operator.
  • $P^n_{rel}$: Generalizes this logic by looking $n$ steps ahead using regression (calculating preconditions required to reach a state).

PABLO operates as a nonlinear planner, building a partial order of actions rather than a simple linear list. It begins planning at the highest level of abstraction—where predicates are easiest to satisfy—and gradually refines the plan toward the "base level" of reality.

The abstraction hierarchy generated by PABLO, showing transitions from high-level goals to base-level operators.

Evaluation and Benchmarks

PABLO was evaluated using classic symbolic logic benchmarks to test its recursive and hierarchical capabilities:

  1. Towers of Hanoi: A standard puzzle used to measure the depth of automatically generated hierarchies.
  2. Blocks World Variations: Specifically, a multi-block stacking problem designed to test how the planner handles complex preconditions and potential interruptions.
The initial state and goal configuration for the Blocks World benchmark problem.

Key Results

Empirical evidence demonstrates that PABLO's automated hierarchy generation provides significant performance gains:

  • Computational Efficiency: In the Towers of Hanoi domain, PABLO solved problems in 6.6 seconds with the relaxation hierarchy, compared to 68.5 seconds without it.
  • Complexity Scaling: Planning time was reduced from exponential to linear relative to the number of operators.
  • Hierarchy Depth: For an $n$-disk Towers of Hanoi problem, PABLO automatically generates $n-1$ levels of abstraction, whereas previous state-of-the-art systems like ABSTRIPS could only generate one.

Discussion and Limitations

PABLO's ability to provide "anytime" planning is a major advantage; because it understands the path through its relaxed predicates, it can suggest a plausible, executable action even if the full plan is not yet finished. This makes it highly suitable for real-time robotics.

However, the system relies on an independence assumption. When moving between abstraction levels, PABLO assumes that newly created subgoals can be achieved without conflicting with one another. If these "details" have global consequences, the planner may be forced into computationally expensive backtracking. Future work suggests restricting relaxation to the most common conditions to improve scaling in very large domains.

Conclusion

PABLO represents a significant advancement in automated planning by removing the need for manual hierarchy encoding. Its use of predicate relaxation provides a robust framework for managing complexity and generating reactive plans in symbolic domains.

Summary updated

BibTeX
@inproceedings{christensen1990hierarchical,
  author = {Jens Christensen},
  title = {{A Hierarchical Planner that Generates Its Own Hierarchies}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1990},
}
Figure