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


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




Classical Planning Techniques And Analysis


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.




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. https://doi.org/10.1609/icaps.v31i1.15981