On the Compilability and Expressive Power of State-Dependent Action Costs

Authors

  • David Speck University of Freiburg
  • David Borukhson University of Freiburg
  • Robert Mattmüller University of Freiburg
  • Bernhard Nebel University of Freiburg

Keywords:

Classical Planning Techniques And Analysis

Abstract

While state-dependent action costs are practically relevant and have been studied before, it is still unclear if they are an essential feature of planning tasks. In this paper, we study to what extent state-dependent action costs are an essential feature by analyzing under which circumstances they can be compiled away. We give a complete classification for all combinations of action cost functions and possible cost measures for the compilations. Our theoretical results show that if both task sizes and plan lengths are to be preserved polynomially, then the boundary between compilability and non-compilability lies between FP and FPSPACE computable action cost functions (under a mild assumption on the polynomial hierarchy). Preserving task sizes polynomially and plan lengths linearly at the same time is impossible.

Downloads

Published

2021-05-17

How to Cite

Speck, D., Borukhson, D., Mattmüller, R., & Nebel, B. (2021). On the Compilability and Expressive Power of State-Dependent Action Costs. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 358-366. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/15981