On the undecidability of probabilistic planning and related stochastic optimization problems

DOI10.1016/S0004-3702(02)00378-8zbMath1082.68806MaRDI QIDQ814465

Anne Condon, Omid Madani, Steve Hanks

Publication date: 7 February 2006

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

zbMATH Keywords

Markov decision processes; Stochastic optimization; Computability; Computational complexity; Undecidability; Discounted; Infinity-horizon; Partial observability; Probabilistic planning; Unobservability

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C15: Stochastic programming

03D35: Undecidability and degrees of sets of sentences

68T37: Reasoning under uncertainty in the context of artificial intelligence

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

THE FRONTIER OF DECIDABILITY IN PARTIALLY OBSERVABLE RECURSIVE GAMES, On Decision Problems for Probabilistic Büchi Automata, Optimal cost almost-sure reachability in POMDPs, What is decidable about partially observable Markov decision processes with \(\omega\)-regular objectives, Exploiting symmetries for single- and multi-agent partially observable stochastic domains, Verification and control of partially observable probabilistic systems, On the computability of Solomonoff induction and AIXI, A survey of partial-observation stochastic parity games, POMDPs under probabilistic semantics, Distributed probabilistic input/output automata: expressiveness, (un)decidability and algorithms, Recursive Markov Decision Processes and Recursive Stochastic Games, Verification and Control of Partially Observable Probabilistic Real-Time Systems, Stochastization of Weighted Automata, The Effect of Tossing Coins in Omega-Automata, Probabilistic Acceptors for Languages over Infinite Words

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Planning for conjunctive goals
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• The complexity of stochastic games
• Optimal control of diffusion processes with reflection
• The computational complexity of propositional STRIPS planning
• On the complexity of partially observed Markov decision processes
• Undecidable problems for probabilistic automata of fixed dimension
• A subexponential randomized algorithm for the simple stochastic game problem
• Optimal control of Markov processes with incomplete state information
• Optimal control of partially observable Markovian systems
• STRIPS: A new approach to the application of theorem proving to problem solving
• Solving H-horizon, stationary Markov decision problems in time proportional to log (H)
• Complexity of finite-horizon Markov decision process problems
• The Complexity of Markov Decision Processes
• State of the Art—A Survey of Partially Observable Markov Decision Processes: Theory, Models, and Algorithms
• The Optimal Control of Partially Observable Markov Processes over the Infinite Horizon: Discounted Costs
• Finding Optimal Survey Policies via Adaptive Markov Decision Processes
• The Optimal Control of Partially Observable Markov Processes over a Finite Horizon
• Probabilistic automata
• A survey of computational complexity results in systems and control