Abstraction Heuristics for Classical Planning Tasks with Conditional Effects

Martín Pozo, Jendrik SeippIJCAI 2025 · DOI

Introduction

Classical planning aims to find the optimal (cheapest) sequence of actions to reach a goal state. While many real-world scenarios are naturally modeled using conditional effects—where an action's outcome depends on the state in which it is performed—most state-of-the-art optimal planners struggle to handle them natively. Traditional approaches often rely on "compiling away" these effects into simpler actions, a process that can lead to an exponential explosion in the problem description size.

This paper, presented at IJCAI-25, introduces a novel framework for computing abstraction heuristics natively for tasks with conditional effects. By moving away from exact (induced) abstractions toward over-approximated ones, the authors develop a suite of heuristics that outperform current state-of-the-art optimal planners in complex domains like quantum circuit transformation and matrix multiplication.

Methodology: Embracing Non-Induced Abstractions

The core innovation is the shift from induced abstractions (which perfectly mirror concrete transitions) to conservative, non-induced abstractions. Computing perfect abstractions for conditional effects is NP-hard; by allowing over-approximations, the authors make the computation tractable while maintaining the "admissibility" required for optimal planning (ensuring the heuristic never overestimates the cost to the goal).

The CEGAR Adaptation

The authors adapted the Counterexample-Guided Abstraction Refinement (CEGAR) loop, which starts with a trivial abstraction and refines it upon discovering "flaws"—paths that are valid in the abstraction but impossible in the concrete state space. To handle conditional effects, the authors developed specialized flaw detection strategies and a "Cartesian over-approximation" for regression to manage the logical complexity introduced by state-dependent effects.

Experimental Evaluation

The proposed methods were evaluated on a massive benchmark of 1,963 tasks across 21 domains, including standard International Planning Competition (IPC) tasks and specialized problems like quantum circuit transformation (CNOT domains) and matrix multiplication.

Coverage and Performance

The experimental results demonstrate the superiority of the new heuristics. The best configuration, labeled $C^{fBS}_B$, which combines Cartesian and Pattern Database (PDB) abstractions using Saturated Cost Partitioning (SCP), achieved the highest overall coverage.

Table 1: Coverage results across various domains, showing the superior performance of the $C^{fBS}_B$ configuration compared to baselines.

As shown in the table above, $C^{fBS}_B$ solved 1,270 tasks, significantly outperforming the baseline LM-Cut (1,062) and the previous state-of-the-art Symbolic Bidirectional Search (1,211). Notably, in "General Conditional Effects" domains, the proposed method solved 341 tasks compared to 316 for symbolic search.

Heuristic Quality

Beyond coverage, the quality of the heuristic estimates is a critical factor. The authors compared their combined approach against other abstraction methods to measure how "informed" the heuristics were.

Figure 3: Comparison of heuristic values ($h$-values) for different methods. Higher values closer to the top-left indicate a more informed heuristic.

The scatter plots illustrate that the combined Cartesian and PDB approach ($C^{fBS}_B$) provides significantly tighter estimates (higher heuristic values) than Merge-and-Shrink ($h^{MS}_{SCP}$) or PDBs alone, particularly in the "General" and "Factored" task categories.

Conclusion

By natively handling conditional effects through non-induced abstractions, this research provides a powerful new tool for optimal classical planning. The integration of CEGAR-based Cartesian abstractions with PDBs via Saturated Cost Partitioning sets a new state-of-the-art for these complex problems. Future work will explore domain abstractions to further balance computational efficiency and heuristic accuracy.

Summary updated

BibTeX
@inproceedings{pozo2025abstraction,
  author = {Martín Pozo and Jendrik Seipp},
  title = {{Abstraction Heuristics for Classical Planning Tasks with Conditional Effects}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/957},
}
Figure