Efficient Planning with State-Dependent Action Costs

有效规划与国家相关的行动成本

• 批准号: 405834399
• 负责人: Dr. Robert Mattmüller
• 金额: --
• 依托单位: Arbeitsgruppe Grundlagen der Künstlichen Intelligenz
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2018
• 资助国家: 德国
• 起止时间: 2017-12-31 至 2021-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/405834399?language=en
• 关键词: Efficient; Planning; State; Dependent; Action

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.

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