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:
- Series Resistance (Operators): The difficulty of an action (operator) is the sum of the difficulties of its required preconditions.
- 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 (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.
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