Computing Abstraction Hierarchies by Numerical Simulation

Alan Bundy, Fausto Giunchiglia, Roberto Sebastiani, Toby Walsh

TL;DR

The RESISTOR model offers a novel numerical simulation approach to automatically generate abstraction hierarchies for AI planning. By modeling planning constraints as electrical resistances, it achieves orders-of-magnitude speedups over traditional symbolic reasoning methods like ALPINE and HIGHPOINT.

Introduction

In classical AI planning, the "state-space explosion" remains a primary hurdle. Abstraction hierarchies address this by allowing planners to first solve high-level "skeleton" problems before refining them into detailed low-level plans. However, the effectiveness of this approach hinges on the quality of the hierarchy. Poorly constructed abstractions lead to excessive backtracking, where a high-level plan cannot be realized at the ground level. While previous systems like ALPINE and HIGHPOINT utilized logical proofs to build these hierarchies, they often proved computationally expensive and sometimes failed to prevent backtracking in complex scenarios.

The RESISTOR Model

The authors propose the RESISTOR model, which shifts from complex logical reasoning to a fast numerical simulation. The core idea is to assign a "numerical criticality" or difficulty to every precondition based on an analogy to electrical circuits:

  1. Series Resistance (Operators): The difficulty of an action (operator) is the sum of the difficulties of its required preconditions.
  2. Parallel Resistance (Preconditions): If multiple actions can achieve a specific state (precondition), its difficulty is calculated as the parallel sum (harmonic mean) of those actions.

Through successive approximation, the algorithm iterates until difficulty values stabilize. Preconditions with high "resistance" are placed at the top of the hierarchy to be solved first, ensuring that the most difficult constraints guide the initial planning phase.

Experimental Evaluation

The RESISTOR model was evaluated against four classic AI planning benchmarks: the Tower of Hanoi, the Manufacturing domain, the Computer Hardware domain, and the Robot-Box domain.

The Robot-Box domain environment used for benchmarking.

The Robot-Box domain (illustrated above) provides a classic testbed for moving objects between rooms with varying door constraints. In these tests, RESISTOR demonstrated a natural ability to enforce "precondition monotonicity," ensuring that harder-to-achieve states are always handled at higher abstraction levels.

Results and Discussion

The primary advantage of the RESISTOR model is its computational efficiency. By avoiding the combinatorial explosion of symbolic reasoning, it generates hierarchies significantly faster than its predecessors.

Comparison of CPU time for hierarchy generation and planning in the Computer Hardware domain.

As shown in the performance data, RESISTOR maintains a near-linear growth in CPU time as problem complexity increases, whereas ALPINE and HIGHPOINT exhibit much steeper curves. In the Computer Hardware domain specifically, RESISTOR reduced hierarchy generation time from over 15 seconds (HIGHPOINT) to just 0.12 seconds. Beyond generation speed, the resulting hierarchies also improved overall planning efficiency, reducing node expansion and backtracking across all tested domains.

Conclusion

The RESISTOR model demonstrates that numerical simulation can be a powerful alternative to deep logical reasoning in AI planning. By abstracting difficulty into a single numerical value, the system provides a robust, fast, and scalable method for building high-quality abstraction hierarchies that significantly enhance planner performance.

Summary updated

Abstract

We present a novel method for building ABSTRIPS-style abstraction hierarchies in planning. The aim of this method is to minimize the amount of backtracking between abstraction levels. Previous approaches have determined the criticality of operator preconditions by reasoning about plans directly. Here, we adopt a simpler and faster approach where we use numerical simulation of the planning process. We demonstrate the theoretical advantages of our approach by identifying some simple properties lacking in previous approaches but possessed by our method. We demonstrate the empirical advantages of our approach by a set of four benchmark experiments using the ABTWEAK system. We compare the quality of the abstraction hierarchies generated with those built by the ALPINE and HIGHPOINT algorithms.
BibTeX
@inproceedings{bundy1996computing,
  author = {Alan Bundy and Fausto Giunchiglia and Roberto Sebastiani and Toby Walsh},
  title = {{Computing Abstraction Hierarchies by Numerical Simulation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure