将鲁棒部分可观测马尔可夫决策过程转化为博弈问题求解。
Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games
- 通过转化到部分可观测随机博弈，解决不确定环境下的复杂目标规划。
- 首次建立双向转换关系，证明两类模型在语义上等价。
- 适用于需要高可靠性的安全、导航等机器人任务场景。
鲁棒部分可观测马尔可夫决策过程（RPOMDP）将经典POMDP推广至转移概率未知的场景，仅知其属于某个不确定性集合。本文研究具有广义ω-正则目标的RPOMDP求解问题，该类目标包含可达性、安全性及线性时序逻辑（LTL）等。针对（s,a）-矩形的RPOMDP且不确定性集为多面体的情况，本文证明其求解问题可转化为部分可观测随机博弈（POSG）下的ω-正则目标求解。更重要的是，首次建立了双向转换关系，确立了二者在语义上的等价性。由此导出一系列新的计算复杂度结果，涵盖不同ω-正则目标下求解的上下界。作为推论，也获得了对鲁棒马尔可夫决策过程（RMDP）的新复杂度结论。
原文摘要 · Abstract (English)
Robust POMDPs (RPOMDPs) generalize classical POMDPs to the setting where exact transition probabilities are not known -- rather, they are only known to belong to some uncertainty set of values. In this work, we study the problem of solving RPOMDPs with general omega-regular objectives, which subsume a broad class of objectives such as reachability, safety, and linear temporal logic (LTL) objectives. We show that, for (s,a)-rectangular RPOMDPs with polytopic uncertainty sets, the problem of solving RPOMDPs under omega-regular objectives can be reduced to solving partially observable stochastic games (POSGs) under omega-regular objectives. Moreover, we show for the first time that reductions can be constructed in both directions, establishing the semantic equivalence between (s,a)-rectangular RPOMDPs with polytopic uncertainty sets and POSGs. This allows us to derive a range of new computational complexity results, including both upper and lower complexity bounds, on solving RPOMDPs with different omega-regular objectives. As a corollary, we also derive new computational complexity results for RMDPs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。