Subset-Saturated Transition Cost Partitioning


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



Classical Planning Techniques And Analysis


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.




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.