Merge-and-Shrink Heuristics for Classical Planning: Efficient Implementation and Partial Abstractions

Sievers, Silvan. (2018) Merge-and-Shrink Heuristics for Classical Planning: Efficient Implementation and Partial Abstractions. In: Proceedings of the Eleventh Annual Symposium on Combinatorial Search (SoCS 2018). pp. 90-98.

[img] PDF - Published Version

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

Downloads: Statistics Overview


Merge-and-shrink heuristics are a successful class of abstraction heuristics used for optimal classical planning. With the recent addition of generalized label reduction, merge-and-shrink can be understood as an algorithm framework that repeatedly applies transformations to a factored representation of a given planning task to compute an abstraction. In this paper, we describe an efficient implementation of the framework and its transformations, comparing it to its previous implementation in Fast Downward. We further discuss partial merge-and-shrink abstractions that do not consider all aspects of the concrete state space. To compute such partial abstractions, we stop the merge-and-shrink computation early by imposing simple limits on the resource consumption of the algorithm. Our evaluation shows that the efficient implementation indeed improves over the previous one, and that partial merge-and-shrink abstractions further push the efficiency of merge-and-shrink planners.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Sievers, Silvan
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:12 Oct 2018 13:15
Deposited On:12 Oct 2018 13:15

Repository Staff Only: item control page