Efficient Planning with State-Dependent Action Costs

• Applicant: Dr. Robert Mattmüller
• Subject Area: Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
• Term: from 2018 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 405834399

In AI planning, the objective is to automatically find a course of actions that transforms the current state of the world into a desired goal state. Available actions, current state, and goal description are given as part of the model. In classical planning, actions usually have unit costs. While this setting is relatively well-understood, many reasonable extensions are not. In this project, we want to study the generalization in which actions can have costs that depend on the state in which they are applied. This generalization is important both from a modeler perspective, since it it is more natural and less error-prone to work with, and from a computational perspective, since algorithms can then exploit structure that is present in cost functions. In addition, state-dependent action costs have applications within planning and related areas, such as planning with preferences, numeric planning, and MDP solving in the presence of state-dependent rewards.A major challenge is to accurately reflect such costs within goal-distance heuristics. In previous work, we showed how this challenge can be approached by representing cost functions as a certain type of decision diagrams, so-called edge-valued multi-valued decision diagrams (EVMDDs). We showed that this leads to informative and useful heuristic functions.However, there is a number of open questions regarding planning with state-dependent action costs which revolve around two issues: first, the size of the cost EVMDDs is worst-case exponential in the number of state variables on which the action costs depend; and second, many classical heuristics have not been studied in the context of state-dependent costs, and heuristic values can become unnecessarily uninformative if the interaction between state-dependent costs and conditional effects is handled inappropriately. In this project, we will address those questions by studying static and dynamic variable orderingfor EVMDDs, EVMDD relaxations, heuristics and their invariance under compilations, and a uniform treatment of state-dependent action costs and conditional effects.

• DFG Programme: Research Grants
• Co-Investigator: Professor Dr. Bernhard Nebel