Relational Partially Observable MDPs
Relational Partially Observable MDPs
复制标题
关系型部分可观测 MDP
DOI：
10.1609/aaai.v24i1.7742
复制
发表时间：
2010
影响因子：
7.3
通讯作者：
R. Khardon
中科院分区：
文献类型：
--
作者：
Chenggang Wang;R. Khardon
关系马尔可夫决策过程（MDP）是随机规划问题的一个有用的抽象，因为人们可以开发独立于域大小或实例化的抽象解决方案。虽然已经有越来越多的兴趣，在发展关系完全可观察的MDP，有很少的工作关系部分可观察的MDP（POMDP），除了处理随机动作效应的问题状态的不确定性。本文提供了一个具体的形式化的关系POMDPs，使他们的解决方案的几个技术贡献。首先，我们表明，要保持正确性，必须区分量化状态和量化的信念状态，这意味着基于值迭代的解决方案本质上是有限的地平线的情况下。其次，我们提供了一个符号动态规划算法的有限时域关系POMDPs，解决他们在抽象层次上，通过提升命题增量剪枝算法。第三，我们表明该算法可以使用一阶决策图来实现，一阶决策图是关系结构上函数的紧凑表示，最近已用于求解关系MDP。
Relational Markov Decision Processes (MDP) are a useful abstraction for stochastic planning problems since one can develop abstract solutions for them that are independent of domain size or instantiation. While there has been an increased interest in developing relational fully observable MDPs, there has been very little work on relational partially observable MDPs (POMDP), which deal with uncertainty in problem states in addition to stochastic action effects. This paper provides a concrete formalization of relational POMDPs making several technical contributions toward their solution. First, we show that to maintain correctness one must distinguish between quantification over states and quantification over belief states; this implies that solutions based on value iteration are inherently limited to the finite horizon case. Second, we provide a symbolic dynamic programing algorithm for finite horizon relational POMDPs, solving them at an abstract level, by lifting the propositional incremental pruning algorithm. Third, we show that this algorithm can be implemented using first order decision diagrams, a compact representation for functions over relational structures, that has been recently used to solve relational MDPs.