State-Dependent Cost Partitionings for Cartesian Abstractions in Classical Planning

Keller, Thomas; Pommerening, Florian; Seipp, Jendrik; Geißer, Florian; Mattmüller, Robert

State-Dependent Cost Partitionings for Cartesian Abstractions in Classical Planning

Thomas Keller, Florian Pommerening, Jendrik Seipp, Florian Geißer, Robert Mattmüller

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 3161-3168.

Abstract

Abstraction heuristics are a popular method to guide optimal search algorithms in classical planning. Cost partitionings allow to sum heuristic estimates admissibly by distributing action costs among the heuristics. We introduce state-dependent cost partitionings which take context information of actions into account, and show that an optimal state-dependent cost partitioning dominates its state-independent counterpart. We demonstrate the potential of our idea with a state-dependent variant of the recently proposed saturated cost partitioning, and show that it has the potential to improve not only over its state-independent counterpart, but even over the optimal state-independent cost partitioning. Our empirical results give evidence that ignoring the context of actions in the computation of a cost partitioning leads to a significant loss of information.

Thomas Keller, Florian Pommerening, Jendrik Seipp, Florian Geißer, and Robert Mattmüller. 2016. State-Dependent Cost Partitionings for Cartesian Abstractions in Classical Planning. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 3161–3168. https://ijcai.org/proceedings/2016/448

@inproceedings{ijcai2016p448,
  title     = {State-Dependent Cost Partitionings for Cartesian Abstractions in Classical Planning},
  author    = {Keller, Thomas and Pommerening, Florian and Seipp, Jendrik and Geißer, Florian and Mattmüller, Robert},
  booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-16}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Subbarao Kambhampati},
  pages     = {3161--3168},
  year      = {2016},
  month     = {7},
  url       = {https://ijcai.org/proceedings/2016/448},
}

TY  - CPAPER
TI  - State-Dependent Cost Partitionings for Cartesian Abstractions in Classical Planning
AU  - Keller, Thomas
AU  - Pommerening, Florian
AU  - Seipp, Jendrik
AU  - Geißer, Florian
AU  - Mattmüller, Robert
T2  - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2016
SP  - 3161
EP  - 3168
UR  - https://ijcai.org/proceedings/2016/448
ER  -