Higher-Dimensional Potential Heuristics for Optimal Classical Planning

Pommerening, Florian and Helmert, Malte and Bonet, Blai. (2017) Higher-Dimensional Potential Heuristics for Optimal Classical Planning. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI 2017). pp. 3636-3643.

[img] PDF - Published Version

Official URL: http://edoc.unibas.ch/54609/

Downloads: Statistics Overview


Potential heuristics for state-space search are defined as weighted sums over simple state features. Atomic features consider the value of a single state variable in a factored state representation, while binary features consider joint assignments to two state variables. Previous work showed that the set of all admissible and consistent potential heuristics using atomic features can be characterized by a compact set of linear constraints. We generalize this result to binary features and prove a hardness result for features of higher dimension. Furthermore, we prove a tractability result based on the treewidth of a new graphical structure we call the context-dependency graph. Finally, we study the relationship of potential heuristics to transition cost partitioning. Experimental results show that binary potential heuristics are significantly more informative than the previously considered atomic ones.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Pommerening, Florian and Helmert, Malte
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Series Name:Proceedings of the ... AAAI Conference on Artificial Intelligence
Note:Publication type according to Uni Basel Research Database: Conference paper
edoc DOI:
Last Modified:05 Apr 2017 11:46
Deposited On:05 Apr 2017 10:57

Repository Staff Only: item control page