On the Relationship Between State-Dependent Action Costs and Conditional Effects in Planning

Authors

  • Robert Mattmüller University of Freiburg
  • Florian Geißer University of Freiburg
  • Benedict Wright University of Freiburg
  • Bernhard Nebel University of Freiburg

DOI:

https://doi.org/10.1609/aaai.v32i1.12088

Keywords:

Artificial Intelligence, Planning

Abstract

When planning for tasks that feature both state-dependent action costs and conditional effects using relaxation heuristics, the following problem appears: handling costs and effects separately leads to worse-than-necessary heuristic values, since we may get the more useful effect at the lower cost by choosing different values of a relaxed variable when determining relaxed costs and relaxed active effects. In this paper, we show how this issue can be avoided by representing state-dependent costs and conditional effects uniformly, both as edge-valued multi-valued decision diagrams (EVMDDs) over different sets of edge values, and then working with their product diagram. We develop a theory of EVMDDs that is general enough to encompass state-dependent action costs, conditional effects, and even their combination.We define relaxed effect semantics in the presence of state-dependent action costs and conditional effects, and describe how this semantics can be efficiently computed using product EVMDDs. This will form the foundation for informative relaxation heuristics in the setting with state-dependent costs and conditional effects combined.

Downloads

Published

2018-04-26

How to Cite

Mattmüller, R., Geißer, F., Wright, B., & Nebel, B. (2018). On the Relationship Between State-Dependent Action Costs and Conditional Effects in Planning. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). https://doi.org/10.1609/aaai.v32i1.12088