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.
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.
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