Linear and Integer Programming-Based Heuristics for Cost-Optimal Numeric Planning

Authors

  • Chiara Piacentini University of Toronto
  • Margarita Castro University of Toronto
  • Andre Cire University of Toronto
  • J. Christopher Beck University of Toronto

DOI:

https://doi.org/10.1609/aaai.v32i1.12082

Keywords:

Cost-optimal Numeric Planning, Heuristic Search, Numeric Planning, Integer Programming, Linear Programming

Abstract

Linear programming has been successfully used to compute admissible heuristics for cost-optimal classical planning. Although one of the strengths of linear programming is the ability to express and reason about numeric variables and constraints, their use in numeric planning is limited. In this work, we extend linear programming-based heuristics for classical planning to support numeric state variables. In particular, we propose a model for the interval relaxation, coupled with landmarks and state equation constraints. We consider both linear programming models and their harder-to-solve, yet more informative, integer programming versions. Our experimental analysis shows that considering an NP-Hard heuristic often pays off and that A* search using our integer programming heuristics establishes a new state of the art in cost-optimal numeric planning.

Downloads

Published

2018-04-26

How to Cite

Piacentini, C., Castro, M., Cire, A., & Beck, J. C. (2018). Linear and Integer Programming-Based Heuristics for Cost-Optimal Numeric Planning. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). https://doi.org/10.1609/aaai.v32i1.12082