文章基本信息

标题：What is Decidable about Partially Observable Markov Decision Processes with omega-Regular Objectives
本地全文：下载
作者：Krishnendu Chatterjee ; Martin Chmelik ; Mathieu Tracol 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2013
卷号：23
页码：165-180
DOI：10.4230/LIPIcs.CSL.2013.165
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We consider partially observable Markov decision processes (POMDPs) with omega-regular conditions specified as parity objectives. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, we establish decidability (with optimal EXPTIME-complete complexity) of the qualitative analysis problems for POMDPs with all parity objectives under finite-memory strategies. We also establish optimal (exponential) memory bounds.
关键词：POMDPs; Omega-regular objectives; Parity objectives; Qualitative analysis