Counterexample-guided Cartesian abstraction refinement

Seipp, Jendrik and Helmert, Malte. (2013) Counterexample-guided Cartesian abstraction refinement. In: Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS 2013) : [held 10 - 14 June 2013 in Rome, Italy]. Palo Alto, Calif., pp. 347-351.

PDF - Published Version

Official URL: http://edoc.unibas.ch/dok/A6212197

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. Our implementation performs tens of thousands of refinement steps in a few minutes and produces heuristics that are often significantly more accurate than pattern database heuristics of the same size.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Seipp, Jendrik and Helmert, Malte
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Note:Publication type according to Uni Basel Research Database: Conference paper
Related URLs:
edoc DOI:
Last Modified:19 Nov 2018 15:06
Deposited On:23 May 2014 08:34

Repository Staff Only: item control page