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)
Markov decision processes; Stochastic optimization; Computability; Computational complexity; Undecidability; Discounted; Infinity-horizon; Partial observability; Probabilistic planning; Unobservability
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
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