提出离线求解大规模部分可观测马尔可夫决策过程的新算法，可生成可验证策略。
Partially Observable Monte-Carlo Graph Search
- 将搜索树动态折叠为策略图，减少计算量并支持离线规划
- 在最难的POMDP任务上生成策略，性能媲美顶尖在线算法
- 适用于连续状态空间，适合对实时性有要求的应用场景
当前大型部分可观测马尔可夫决策过程（POMDP）通常采用采样式在线方法求解，该方法在规划与执行间交替进行。然而，在时间或能量受限的应用中，预计算的离线策略更为理想。但以往离线算法难以扩展至大规模POMDP。本文提出一种新的采样式算法——部分可观测蒙特卡洛图搜索（POMCGS），用于离线求解大规模POMDP。与多数在线方法不同，POMCGS在模拟过程中动态折叠搜索树以构建策略图，大幅降低计算开销，并允许用户在嵌入和执行前分析与验证策略。此外，结合文中提出的动作渐进扩张与观测聚类方法，POMCGS可处理某些连续POMDP。实验表明，POMCGS能在以往离线算法无法计算的最挑战性POMDP上生成策略，其策略价值与当前最先进的在线算法相当。
原文摘要 · Abstract (English)
Currently, large partially observable Markov decision processes (POMDPs) are often solved by sampling-based online methods which interleave planning and execution phases. However, a pre-computed offline policy is more desirable in POMDP applications with time or energy constraints. But previous offline algorithms are not able to scale up to large POMDPs. In this article, we propose a new sampling-based algorithm, the partially observable Monte-Carlo graph search (POMCGS) to solve large POMDPs offline. Different from many online POMDP methods, which progressively develop a tree while performing (Monte-Carlo) simulations, POMCGS folds this search tree on the fly to construct a policy graph, so that computations can be drastically reduced, and users can analyze and validate the policy prior to embedding and executing it. Moreover, POMCGS, together with action progressive widening and observation clustering methods provided in this article, is able to address certain continuous POMDPs. Through experiments, we demonstrate that POMCGS can generate policies on the most challenging POMDPs, which cannot be computed by previous offline algorithms, and these policies' values are competitive compared with the state-of-the-art online POMDP algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。