On the undecidability of probabilistic planning and related stochastic optimization problems

By Omid Madani, Steve Hanks, Anne Condon. 2003

285 citations recorded by the source corpus.

Automated planning, the problem of how an agent achieves a goal given a repertoire of actions, is one of the foundational and most widely studied problems in the AI literature. The original formulation of the problem makes strong assumptions regarding the agent's knowledge and control over the world, namely that its information is complete and correct, and that the results of its actions are deterministic and known. Recent research in planning under uncertainty has endeavored te relax these assumptions, providing formal and computation models wherein the agent has incomplete or noisy information about the world and has noisy sensors and effectors. This research has mainly taken one of two approaches: extend the classical planning paradigm to a semantics that admits uncertainty, or adopt another framework for approaching the problem, most commonly the Markov Decision Process (MDP) model. This paper presents a complexity analysis of planning under uncertainty. It begins with the "probabilistic classical planning" problem, showing that problem to be formally undecidable. This fundamental result is then applied to a broad class of stochastic optimization problems, in brief any problem statement where the agent (a) operates over an infinite or indefinite time horizon, and (b) has available only probabilistic information about the system's state. Undecidability is established for policy-existence problems for partially observable infinite-horizon Markov decision processes under discounted and undiscounted total reward models, average-reward models, and state-avoidance models. The results also apply to corresponding approximation problems with undiscounted objective functions. The paper answers a significant open question raised by Papadimitriou and Tsitsiklis [Math. Oper. Res. 12 (3) (1987) 441-450] about the complexity of infinite horizon POMDPs.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Probabilistic ω-automata (2012, methodology): “Their proof is short, elegant, and only relies on the undecidability of emptiness for PFA with threshold 0 .”
A Framework for Sequential Planning in Multi-Agent Settings (2005, background): “4. The issue of computability of solutions to POMDPs has been a subject of much research (Papadimitriou & Tsitsiklis, 1987; Madani, Hanks, & Condon, 2003 ).”
Exploration from Generalization Mediated by Multiple Controllers (2013, background): “…models are becoming relatively commonplace (Beal et al. 2002; Neal 2000; Teh et al. 2006; Thibaux and Jordan 2007), doing long-run planning in the face of these uncertainties is known to be radically intractable (Kaelbling et al. 1998; Madani et al. 2003; Papadimitriou and Tsitsiklis 1987).”