TY - JOUR AU - Speck, David AU - Seipp, Jendrik PY - 2022/06/13 Y2 - 2024/03/29 TI - New Refinement Strategies for Cartesian Abstractions JF - Proceedings of the International Conference on Automated Planning and Scheduling JA - ICAPS VL - 32 IS - 1 SE - Main Track DO - 10.1609/icaps.v32i1.19819 UR - https://ojs.aaai.org/index.php/ICAPS/article/view/19819 SP - 348-352 AB - 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. ER -