When CEGAR Meets Regression: A Love Story in Optimal Classical Planning
Martín Pozo, Alvaro Torralba, Carlos Linares Lopez
Abstract
Counterexample-Guided Abstraction Refinement (CEGAR) is a prominent technique to generate Cartesian abstractions for guiding search in cost- optimal planning. The core idea is to iteratively refine the abstraction, finding a flaw of the current optimal abstract plan. All existing approaches find these flaws by executing the abstract plan using progression in the original state space. Instead, we propose to do backward refinements by using regression from the goals. This results in a new type of flaw, that can identify invalid plan suffixes. The resulting abstractions are less focused on the initial state, but more informative on average, significantly improving the performance of current CEGAR-based techniques. Furthermore, they can be combined with forward refinements in several bidirectional strategies that provide the benefits of both methods.
BibTeX
@article{Pozo_Torralba_Linares Lopez_2024, title={When CEGAR Meets Regression: A Love Story in Optimal Classical Planning}, volume={38}, url={https://ojs.aaai.org/index.php/AAAI/article/view/30004}, DOI={10.1609/aaai.v38i18.30004}, abstractNote={Counterexample-Guided Abstraction Refinement (CEGAR) is a prominent technique to generate Cartesian abstractions for guiding search in cost- optimal planning. The core idea is to iteratively refine the abstraction, finding a flaw of the current optimal abstract plan. All existing approaches find these flaws by executing the abstract plan using progression in the original state space. Instead, we propose to do backward refinements by using regression from the goals. This results in a new type of flaw, that can identify invalid plan suffixes. The resulting abstractions are less focused on the initial state, but more informative on average, significantly improving the performance of current CEGAR-based techniques. Furthermore, they can be combined with forward refinements in several bidirectional strategies that provide the benefits of both methods.}, number={18}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Pozo, Martín and Torralba, Alvaro and Linares Lopez, Carlos}, year={2024}, month={Mar.}, pages={20238-20246} }