Linear and Integer Programming-Based Heuristics for Cost-Optimal Numeric Planning
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.
Cite
Text
Piacentini et al. "Linear and Integer Programming-Based Heuristics for Cost-Optimal Numeric Planning." AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/AAAI.V32I1.12082Markdown
[Piacentini et al. "Linear and Integer Programming-Based Heuristics for Cost-Optimal Numeric Planning." AAAI Conference on Artificial Intelligence, 2018.](https://mlanthology.org/aaai/2018/piacentini2018aaai-linear/) doi:10.1609/AAAI.V32I1.12082BibTeX
@inproceedings{piacentini2018aaai-linear,
title = {{Linear and Integer Programming-Based Heuristics for Cost-Optimal Numeric Planning}},
author = {Piacentini, Chiara and Castro, Margarita P. and Ciré, André Augusto and Beck, J. Christopher},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2018},
pages = {6254-6261},
doi = {10.1609/AAAI.V32I1.12082},
url = {https://mlanthology.org/aaai/2018/piacentini2018aaai-linear/}
}