1 Search Results for "Chmelik, Martin"

Document
DOI: 10.4230/LIPIcs.CSL.2013.165
What is Decidable about Partially Observable Markov Decision Processes with omega-Regular Objectives

Authors: Krishnendu Chatterjee, Martin Chmelik, and Mathieu Tracol

Published in: LIPIcs, Volume 23, Computer Science Logic 2013 (CSL 2013)

Abstract
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.
Cite as

Krishnendu Chatterjee, Martin Chmelik, and Mathieu Tracol. What is Decidable about Partially Observable Markov Decision Processes with omega-Regular Objectives. In Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 23, pp. 165-180, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.CSL.2013.165,
  author =	{Chatterjee, Krishnendu and Chmelik, Martin and Tracol, Mathieu},
  title =	{{What is Decidable about Partially Observable Markov Decision Processes with omega-Regular Objectives}},
  booktitle =	{Computer Science Logic 2013 (CSL 2013)},
  pages =	{165--180},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-60-6},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{23},
  editor =	{Ronchi Della Rocca, Simona},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2013.165},
  URN =		{urn:nbn:de:0030-drops-41962},
  doi =		{10.4230/LIPIcs.CSL.2013.165},
  annote =	{Keywords: POMDPs, Omega-regular objectives, Parity objectives, Qualitative analysis}
}
  • Refine by Author
  • 1 Chatterjee, Krishnendu
  • 1 Chmelik, Martin
  • 1 Tracol, Mathieu

  • Refine by Classification

  • Refine by Keyword
  • 1 Omega-regular objectives
  • 1 POMDPs
  • 1 Parity objectives
  • 1 Qualitative analysis

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2013

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact