Online planning algorithms for POMDPs
Online planning algorithms for POMDPs
复制标题
DOI：
10.1613/jair.2567
复制
发表时间：
2008-01-01
影响因子：
5
通讯作者：
Chaib-draa, Brahim
中科院分区：
文献类型：
--
作者：
Ross, Stephane;Pineau, Joelle;Chaib-draa, Brahim
部分可观察马尔可夫决策过程 (POMDP) 为随机域中不确定性下的顺序决策提供了丰富的框架。然而，由于 POMDP 的复杂性，除了小问题外，求解 POMDP 通常很棘手。在这里，我们关注在线方法，通过在执行过程中的每个决策步骤计算良好的本地策略来减轻计算复杂性。在线算法通常包括前瞻搜索，以找到在环境中的每个时间步骤执行的最佳操作。我们的目标是调查现有的各种在线 POMDP 方法，分析它们的特性并讨论它们的优缺点；并在不同环境下根据各种指标（回报、误差界限减少、下限改进）彻底评估这些在线方法。我们的实验结果表明，最先进的在线启发式搜索方法可以有效地处理大型 POMDP 域。
Partially Observable Markov Decision Processes (POMDPs) provide a rich framework for sequential decision-making under uncertainty in stochastic domains. However, solving a POMDP is often intractable except for small problems due to their complexity. Here, we focus on online approaches that alleviate the computational complexity by computing good local policies at each decision step during the execution. Online algorithms generally consist of a lookahead search to find the best action to execute at each time step in an environment. Our objectives here are to survey the various existing online POMDP methods, analyze their properties and discuss their advantages and disadvantages; and to thoroughly evaluate these online approaches in different environments under various metrics ( return, error bound reduction, lower bound improvement). Our experimental results indicate that state-of-the-art online heuristic search methods can handle large POMDP domains efficiently.