Subset-Saturated Transition Cost Partitioning

Drexler, Dominik and Seipp, Jendrik and Speck, David. (2021) Subset-Saturated Transition Cost Partitioning. In: Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021), 31. pp. 131-139.

[img] PDF - Accepted Version

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

Downloads: Statistics Overview


Cost partitioning admissibly combines the information from multiple heuristics for optimal state-space search. One of the strongest cost partitioning algorithms is saturated cost partitioning. It considers the heuristics in sequence and assigns to each heuristic the minimal fraction of the remaining costs that are needed for preserving all heuristic estimates. Saturated cost partitioning has recently been generalized in two directions: first, by allowing to use different costs for the transitions induced by the same operator, and second, by preserving the heuristic estimates for only a subset of states. In this work, we unify these two generalizations and show that the resulting subset-saturated transition cost partitioning algorithm usually yields stronger heuristics than the two generalizations by themselves.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Seipp, Jendrik
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
edoc DOI:
Last Modified:27 Aug 2021 10:31
Deposited On:25 Aug 2021 15:27

Repository Staff Only: item control page