Region-Based Incremental Pruning for POMDPs
Region-Based Incremental Pruning for POMDPs
复制标题
POMDP 基于区域的增量剪枝
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
S. Zilberstein
中科院分区：
文献类型：
--
作者：
Z. Feng;S. Zilberstein
我们对用于求解部分可观察马尔可夫决策过程的增量修剪算法进行了重大改进。我们的技术的目标交叉和步骤的动态规划（DP）更新，POMDP算法的复杂性的一个关键来源。我们的算法不是在修剪交叉和时对整个信念空间进行推理，而是将信念空间划分为更小的区域，并在每个区域中进行独立的修剪。我们评估的新技术的分析和实验的好处，并表明，它产生非常显着的性能增益。结果有助于POMDP算法的可扩展性域，不能处理的最好的现有技术。
We present a major improvement to the incremental pruning algorithm for solving partially observable Markov decision processes. Our technique targets the cross-sum step of the dynamic programming (DP) update, a key source of complexity in POMDP algorithms. Instead of reasoning about the whole belief space when pruning the cross-sums, our algorithm divides the belief space into smaller regions and performs independent pruning in each region. We evaluate the benefits of the new technique both analytically and experimentally, and show that it produces very significant performance gains. The results contribute to the scalability of POMDP algorithms to domains that cannot be handled by the best existing techniques.