LP-Based Heuristics for Cost-Optimal Planning


  • Florian Pommerening Universität Basel
  • Gabriele Röger Universität Basel
  • Malte Helmert Universität Basel
  • Blai Bonet Universidad Simón Bolívar




classical planning, admissible heuristics, linear programs, cost partitioning


Many heuristics for cost-optimal planning are based on linear programming. We cover several interesting heuristics of this type by a common framework that fixes the objective function of the linear program. Within the framework, constraints from different heuristics can be combined in one heuristic estimate which dominates the maximum of the component heuristics. Different heuristics of the framework can be compared on the basis of their constraints. With this new method of analysis, we show dominance of the recent LP-based state-equation heuristic over optimal cost partitioning on single-variable abstractions.  We also show that the previously suggested extension of the state-equation heuristic to exploit safe variables cannot lead to an improved heuristic estimate. We experimentally evaluate the potential of the proposed framework on an extensive suite of benchmark tasks.




How to Cite

Pommerening, F., Röger, G., Helmert, M., & Bonet, B. (2014). LP-Based Heuristics for Cost-Optimal Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 24(1), 226-234. https://doi.org/10.1609/icaps.v24i1.13621