Subset-Saturated Transition Cost Partitioning

Authors

  • Dominik Drexler Linköping University University of Freiburg
  • Jendrik Seipp Linköping University University of Basel
  • David Speck University of Freiburg

Keywords:

Classical Planning Techniques And Analysis

Abstract

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.

Downloads

Published

2021-05-17

How to Cite

Drexler, D., Seipp, J., & Speck, D. (2021). Subset-Saturated Transition Cost Partitioning. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 131-139. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/15955