New Refinement Strategies for Cartesian Abstractions


  • David Speck University of Freiburg
  • Jendrik Seipp Linköping University



Classical Planning, Heuristic Search, Counterexample-Guided Abstraction Refinement


Cartesian counterexample-guided abstraction refinement (CEGAR) yields strong heuristics for optimal classical planning. CEGAR repeatedly finds counterexamples, i.e., abstract plans that fail for the concrete task. Although there are usually many such abstract plans to choose from, the refinement strategy from previous work is to choose an arbitrary optimal one. In this work, we show that an informed refinement strategy is critical in theory and practice. We demonstrate that it is possible to execute all optimal abstract plans in the concrete task simultaneously, and present methods to minimize the time and number of refinement steps until we find a concrete solution. The resulting algorithm solves more tasks than the previous state of the art for Cartesian CEGAR, both during refinement and when used as a heuristic in an A* search.




How to Cite

Speck, D., & Seipp, J. (2022). New Refinement Strategies for Cartesian Abstractions. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 348-352.