Subset-Saturated Cost Partitioning for Optimal Classical Planning


  • Jendrik Seipp University of Basel
  • Malte Helmert University of Basel


Cost partitioning is a method for admissibly adding multiple heuristics for state-space search. Saturated cost partitioning considers the given heuristics in sequence, assigning to each heuristic the minimum fraction of remaining costs that it needs to preserve its estimates for all states. We generalize saturated cost partitioning by allowing to preserve the heuristic values of only a subset of states and show that this often leads to stronger heuristics.




How to Cite

Seipp, J., & Helmert, M. (2021). Subset-Saturated Cost Partitioning for Optimal Classical Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 29(1), 391-400. Retrieved from