Counterexample-Guided Cartesian Abstraction Refinement for Classical Planning

Seipp, Jendrik and Helmert, Malte. (2018) Counterexample-Guided Cartesian Abstraction Refinement for Classical Planning. Journal of Artificial Intelligence Research, 62. pp. 535-577.

[img] PDF - Published Version

Official URL: https://edoc.unibas.ch/65625/

Downloads: Statistics Overview


Counterexample-guided abstraction refinement (CEGAR) is a method for incrementally computing abstractions of transition systems. We propose a CEGAR algorithm for computing abstraction heuristics for optimal classical planning. Starting from a coarse abstraction of the planning task, we iteratively compute an optimal abstract solution, check if and why it fails for the concrete planning task and refine the abstraction so that the same failure cannot occur in future iterations. A key ingredient of our approach is a novel class of abstractions for classical planning tasks that admits efficient and very fine-grained refinement. Since a single abstraction usually cannot capture enough details of the planning task, we also introduce two methods for producing diverse sets of heuristics within this framework, one based on goal atoms, the other based on landmarks. In order to sum their heuristic estimates admissibly we introduce a new cost partitioning algorithm called saturated cost partitioning. We show that the resulting heuristics outperform other state-of-the-art abstraction heuristics in many benchmark domains.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Seipp, Jendrik and Helmert, Malte
Item Type:Article, refereed
Article Subtype:Research Article
Publisher:AI Access Foundation
Note:Publication type according to Uni Basel Research Database: Journal article
Identification Number:
edoc DOI:
Last Modified:12 Oct 2018 13:27
Deposited On:12 Oct 2018 13:27

Repository Staff Only: item control page