EUVIMEDEUVIMED entdecken
Crossref

New Flaw Search Strategies in CEGAR for Cartesian Abstractions in Optimal Classical Planning

Martín Pozo, Álvaro Torralba, Carlos Linares López

Journal of Artificial Intelligence Research · 15.08.2026 · 86

DOI: 10.1613/jair.1.21501 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Artificial Intelligence Research, online erschienen am 15.08.2026. Verfasst von Martín Pozo und 2 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Background

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 start from the trivial abstraction—an abstract state representing all concrete states—and iteratively refine it in a loop by splitting one abstract state into two. Each iteration of the loop searches an optimal abstract plan and replicates it into the concrete state space until finding a flaw—and splitting such abstract state—or returning a plan for the task if no flaw is found. Previous work finds only a single flaw in progression, by executing the abstract plan from the initial state and stopping when execution cannot be continued.

Objectives

A theoretical framework for identifying different flaws of abstract plans, analysing their properties and using them to refine abstractions in different ways leading to higher-quality heuristics.

Methods

We show that alternative types of flaw can be defined. Specifically, we search flaws in regression from the goals—resulting in higher heuristic values—and identify sequence flaws along the whole abstract plan by searching them in a Cartesian relaxation of the task after the first flaw, which greatly increases the flexibility of refinements in CEGAR.

Results

Our experiments show that across existing benchmarks numerous sequence flaws exist in most abstract plans. We observe that the selected flaw has a high impact on the heuristic, and we propose several strategies that generate more informed abstractions. Overall, this greatly improves the performance of the baseline that only used the first progression flaw.

Conclusions

Guiding the CEGAR process by analysing multiple flaws of an abstract plan trace and selecting the best refinement can improve its performance as a tool to generate admissible heuristics in planning. Thus, using our new types of flaw and flaw selection strategies, we get stronger heuristics than the state-of-the-art planners based on Cartesian abstractions.

Zitieren

APA

Pozo, M., Torralba, Á., & López, C. L. (2026). New Flaw Search Strategies in CEGAR for Cartesian Abstractions in Optimal Classical Planning. Journal of Artificial Intelligence Research, 86. https://doi.org/10.1613/jair.1.21501

Vancouver

Pozo M, Torralba Á, López CL. New Flaw Search Strategies in CEGAR for Cartesian Abstractions in Optimal Classical Planning. Journal of Artificial Intelligence Research. 2026;86. doi:10.1613/jair.1.21501

BibTeX
@article{Pozo2026,
  author = {Pozo, Martín and Torralba, Álvaro and López, Carlos Linares},
  title = {New Flaw Search Strategies in CEGAR for Cartesian Abstractions in Optimal Classical Planning},
  journal = {Journal of Artificial Intelligence Research},
  year = {2026},
  volume = {86},
  doi = {10.1613/jair.1.21501}
}
Kostenlos starten →