Counterexample-Guided Abstraction Refinement for Pattern Selection in Optimal Classical Planning

Authors

  • Alexander Rovner University of Basel
  • Silvan Sievers University of Basel
  • Malte Helmert University of Basel

DOI:

https://doi.org/10.1609/icaps.v29i1.3499

Abstract

We describe a new algorithm for generating pattern collections for pattern database heuristics in optimal classical planning. The algorithm uses the counterexample-guided abstraction refinement (CEGAR) principle to guide the pattern selection process. Our experimental evaluation shows that a single run of the CEGAR algorithm can compute informative pattern collections in a fairly short time. Using multiple CEGAR algorithm runs, we can compute much larger pattern collections, still in shorter time than existing approaches, which leads to a planner that outperforms the state-of-the-art pattern selection methods by a significant margin.

Downloads

Published

2021-05-25

How to Cite

Rovner, A., Sievers, S., & Helmert, M. (2021). Counterexample-Guided Abstraction Refinement for Pattern Selection in Optimal Classical Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 29(1), 362-367. https://doi.org/10.1609/icaps.v29i1.3499