POMDPs under probabilistic semantics

DOI10.1016/j.artint.2014.12.009zbMath1329.90158arXiv1408.2058OpenAlexW2962776978MaRDI QIDQ2344358

Krishnendu Chatterjee, Martin Chmelík

Publication date: 15 May 2015

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1408.2058

zbMATH Keywords

POMDPsalmost-sure winninglimit-average objectives

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Markov and semi-Markov decision processes (90C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

What is decidable about partially observable Markov decision processes with \(\omega\)-regular objectives, Analyzing generalized planning under nondeterminism, Parameter-Independent Strategies for pMDPs via POMDPs, Randomness for free, Further improvements of determinization methods for fuzzy finite automata, CEGAR for compositional analysis of qualitative properties in Markov decision processes

Uses Software

• POMDP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Planning and acting in partially observable stochastic domains
• The complexity of two-player games of incomplete information
• On the undecidability of probabilistic planning and related stochastic optimization problems
• Optimal control of diffusion processes with reflection
• Automated analysis of real-time scheduling using graph games
• Complexity of finite-horizon Markov decision process problems
• Randomness for Free
• Qualitative Analysis of Partially-Observable Markov Decision Processes
• Probabilistic Automata on Finite Words: Decidable and Undecidable Problems
• The Complexity of Markov Decision Processes
• Biological Sequence Analysis
• Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study
• Symbolic Feedback Control for Navigation
• Algorithms for Omega-Regular Games with Imperfect Information
• Probabilistic automata
• Finding Shortest Witnesses to the Nonemptiness of Automata on Infinite Words