Abstractions for Planning with State-Dependent Action Costs
Abstractions for Planning with State-Dependent Action Costs
复制标题
具有依赖于状态的行动成本的规划的抽象
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Robert Mattmüller
中科院分区：
文献类型：
--
作者：
Florian Geißer;Thomas Keller;Robert Mattmüller
扩展经典的规划形式主义与状态相关的行动成本（SDAC）允许指数更紧凑的任务编码。最近的工作提出了使用边值多值决策图（EVMDDs）来表示成本函数，它允许自动检测和展示成本函数中的结构，并使启发式估计器准确地反映SDAC。然而，到目前为止，只有不可接受的添加剂启发式被认为是在这种情况下。在本文中，我们定义了信息的可接受的抽象算法，使最优规划与SDAC。我们讨论了如何抽象的成本值可以从EVMDD中提取，代表具体的成本函数，而无需调整它们所选择的抽象。我们的理论分析表明，这是有效的笛卡尔或粗糙的抽象。我们适应反例引导的抽象细化方法来获得这样的抽象。由此产生的启发式的经验评估表明，高度准确的值可以快速计算。
Extending the classical planning formalism with state-dependent action costs (SDAC) allows an up to exponentially more compact task encoding. Recent work proposed to use edge-valued multi-valued decision diagrams (EVMDDs) to represent cost functions, which allows to automatically detect and exhibit structure in cost functions and to make heuristic estimators accurately reflect SDAC. However, so far only the inadmissible additive heuristic has been considered in this context. In this paper, we define informative admissible abstraction heuristics which enable optimal planning with SDAC. We discuss how abstract cost values can be extracted from EVMDDs that represent concrete cost functions without adjusting them to the selected abstraction. Our theoretical analysis shows that this is efficiently possible for abstractions that are Cartesian or coarser. We adapt the counterexample-guided abstraction refinement approach to derive such abstractions. An empirical evaluation of the resulting heuristic shows that highly accurate values can be computed quickly.