Solving POMDPs using quadratically constrained linear programs
Solving POMDPs using quadratically constrained linear programs
复制标题
使用二次约束线性程序求解 POMDP
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
S. Zilberstein
中科院分区：
文献类型：
--
作者：
Chris Amato;D. Bernstein;S. Zilberstein
自20世纪90年代初以来，马尔可夫决策过程（MDP）及其部分可观察对应物（POMDP）已被人工智能社区广泛用于不确定性下的规划。POMDPs提供了一种丰富的语言来描述涉及域的不确定性、随机行为、噪声观测和各种可能的目标函数的情况。尽管最优解可能是简洁的，但使用动态规划的当前精确算法通常需要难以处理的空间量。POMDP近似算法可以在有限的内存下运行，但结果是它们提供了非常弱的理论保证。相比之下，我们描述了一种新的方法，解决了POMDP算法的空间要求，同时保持定义良好的最优性保证。
Since the early 1990's, Markov decision processes (MDPs) and their partially observable counterparts (POMDPs) have been widely used by the AI community for planning under uncertainty. POMDPs offer a rich language to describe situations involving uncertainty about the domain, stochastic actions, noisy observations, and a variety of possible objective functions. Even though an optimal solution may be concise, current exact algorithms that use dynamic programming often require an intractable amount of space. POMDP approximation algorithms can operate with a limited amount of memory, but as a consequence they provide very weak theoretical guarantees. In contrast, we describe a new approach that addresses the space requirement of POMDP algorithms while maintaining well-defined optimality guarantees.