Abstraction Heuristics for Factored Tasks


  • Clemens Büchner University of Basel, Switzerland
  • Patrick Ferber University of Basel, Switzerland
  • Jendrik Seipp Linköping University, Sweden
  • Malte Helmert University of Basel, Switzerland




One of the strongest approaches for optimal classical planning is A* search with heuristics based on abstractions of the planning task. Abstraction heuristics are well studied in planning formalisms without conditional effects such as SAS+. However, conditional effects are crucial to model many planning tasks compactly. In this paper, we focus on *factored* tasks which allow a specific form of conditional effect, where effects on variable x can only depend on the value of x. We generalize projections, domain abstractions, Cartesian abstractions and the counterexample-guided abstraction refinement method to this formalism. While merge-and-shrink already covers factored task in theory, we provide an implementation that does so. In our experiments, we compare these abstraction-based heuristics to other heuristics supporting conditional effects, as well as symbolic search. On our new benchmark set of factored tasks, pattern database heuristics solve the most problems, followed by symbolic approaches on par with domain abstractions. The more general Cartesian abstractions fall behind in terms of coverage but usually solve problems the fastest among all tested approaches. The generality of merge-and-shrink abstractions does not seem to be beneficial for these factored tasks.




How to Cite

Büchner, C., Ferber, P., Seipp, J., & Helmert, M. (2024). Abstraction Heuristics for Factored Tasks. Proceedings of the International Conference on Automated Planning and Scheduling, 34(1), 40-49. https://doi.org/10.1609/icaps.v34i1.31459