Efficient Planning with State-Dependent Action Costs

在人工智能规划中，目标是自动找到将当前世界状态转换为理想目标状态的行动过程。可用的操作、当前状态和目标描述作为模型的一部分给出。在经典的计划中，行动通常有单位成本。虽然这种设置相对容易理解，但许多合理的扩展却不是这样。在这个项目中，我们想要研究一种泛化，在这种泛化中，行为的代价取决于它们被应用的状态。从建模者的角度来看，这种泛化很重要，因为它更自然，更不容易出错，从计算的角度来看，因为算法可以利用成本函数中存在的结构。此外，与状态相关的行动成本在规划和相关领域也有应用，比如有偏好的规划、数字规划和在存在状态相关奖励的情况下求解MDP。一个主要的挑战是在目标距离启发式中准确地反映这些成本。在之前的工作中，我们展示了如何通过将成本函数表示为某种类型的决策图，即所谓的边值多值决策图（evmdd）来解决这一挑战。我们表明，这导致信息丰富和有用的启发式函数。然而，关于与状态相关的行动成本的计划存在许多悬而未决的问题，这些问题围绕着两个问题：首先，成本evmdd的大小是行动成本所依赖的状态变量数量的最坏情况指数；其次，许多经典的启发式方法没有在状态依赖成本的背景下进行研究，如果状态依赖成本和条件效应之间的相互作用处理不当，启发式值可能会变得不必要地缺乏信息。在这个项目中，我们将通过研究EVMDD的静态和动态变量排序、EVMDD松弛、启发式及其在编译中的不变性，以及对状态依赖的动作成本和条件效应的统一处理来解决这些问题。

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.