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