Delete Relaxations for Planning with State-Dependent Action Costs

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

Delete Relaxations for Planning with State-Dependent Action Costs

Florian Geißer, Thomas Keller, Robert Mattmüller

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 1573-1578.

Abstract

Most work in planning focuses on tasks with state-independent or even uniform action costs. However, supporting state-dependent action costs admits a more compact representation of many tasks. We investigate how to solve such tasks using heuristic search, with a focus on delete-relaxation heuristics. We first define a generalization of the additive heuristic to such tasks and then discuss different ways of computing it via compilations to tasks with state-independent action costs and more directly by modifying the relaxed planning graph. We evaluate these approaches theoretically and present an implementation of the additive heuristic for planning with state-dependent action costs. To our knowledge, this gives rise to the first approach able to handle even the hardest instances of the combinatorial Academic Advising domain from the International Probabilistic Planning Competition (IPPC) 2014.

Florian Geißer, Thomas Keller, and Robert Mattmüller. 2015. Delete Relaxations for Planning with State-Dependent Action Costs. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 1573–1578. https://ijcai.org/proceedings/2015/225

@inproceedings{ijcai2015p225,
  title     = {Delete Relaxations for Planning with State-Dependent Action Costs},
  author    = {Geißer, Florian and Keller, Thomas and Mattmüller, Robert},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {1573--1578},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/225},
}

TY  - CPAPER
TI  - Delete Relaxations for Planning with State-Dependent Action Costs
AU  - Geißer, Florian
AU  - Keller, Thomas
AU  - Mattmüller, Robert
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 1573
EP  - 1578
UR  - https://ijcai.org/proceedings/2015/225
ER  -