New Refinement Strategies for Cartesian Abstractions
DOI:
https://doi.org/10.1609/icaps.v32i1.19819Keywords:
Classical Planning, Heuristic Search, Counterexample-Guided Abstraction RefinementAbstract
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.Downloads
Published
2022-06-13
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. https://doi.org/10.1609/icaps.v32i1.19819