Generalized Potential Heuristics for Classical Planning

Francès Medina, Guillem and Corrêa, Augusto B. and Geissmann, Cedric and Pommerening, Florian. (2019) Generalized Potential Heuristics for Classical Planning. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. pp. 5554-5561.

PDF - Published Version

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

Downloads: Statistics Overview


Generalized planning aims at computing solutions that work for all instances of the same domain. In this paper, we show that several interesting planning domains possess compact generalized heuristics that can guide a greedy search in guaranteed polynomial time to the goal, and which work for any instance of the domain . These heuristics are weighted sums of state features that capture the number of objects satisfying a certain first-order logic property in any given state. These features have a meaningful interpretation and generalize naturally to the whole domain. Additionally, we present an approach based on mixed integer linear programming to compute such heuristics automatically from the observation of small training instances. We develop two variations of the approach that progressively refine the heuristic as new states are encountered. We illustrate the approach empirically on a number of standard domains, where we show that the generated heuristics will correctly generalize to all possible instances.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Francès Medina, Guillem and Geissmann, Cedric and Pommerening, Florian and Blaas Corrêa, Augusto
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:International Joint Conferences on Artificial Intelligence
Note:Publication type according to Uni Basel Research Database: Conference paper
Related URLs:
Identification Number:
edoc DOI:
Last Modified:29 Jan 2020 15:59
Deposited On:29 Jan 2020 15:46

Repository Staff Only: item control page