Narrowing the Gap Between Saturated and Optimal Cost Partitioning for Classical Planning

Authors

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

DOI:

https://doi.org/10.1609/aaai.v31i1.11022

Keywords:

planning, optimal planning, classical planning, heuristics, abstraction heuristics, cost partitioning, Cartesian abstractions

Abstract

In classical planning, cost partitioning is a method for admissibly combining a set of heuristic estimators by distributing operator costs among the heuristics. An optimal cost partitioning is often prohibitively expensive to compute. Saturated cost partitioning is an alternative that is much faster to compute and has been shown to offer high-quality heuristic guidance on Cartesian abstractions. However, its greedy nature makes it highly susceptible to the order in which the heuristics are considered. We show that searching in the space of orders leads to significantly better heuristic estimates than with previously considered orders. Moreover, using multiple orders leads to a heuristic that is significantly better informed than any single-order heuristic. In experiments with Cartesian abstractions, the resulting heuristic approximates the optimal cost partitioning very closely.

Downloads

Published

2017-02-12

How to Cite

Seipp, J., Keller, T., & Helmert, M. (2017). Narrowing the Gap Between Saturated and Optimal Cost Partitioning for Classical Planning. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1). https://doi.org/10.1609/aaai.v31i1.11022