The Complexity of Decision-Theoretic Planning for Distributed Agents
D. S. Bernstein, Shlomo Zilberstein · 2000
Planning for distributed agents with partial state information is considered from a decision-theoretic perspective. We describe \emph{decentralized Markov decision processes (DEC-MDPs)} and \emph{decentralized partially observable Markov decision processes (DEC-POMDPs)}, which are generalizations of MDPs and POMDPs, respectively, in which the process is controlled by multiple distributed agents. The finite-horizon version of a DEC-POMDP with at least two agents is shown to be NEXP-complete. In addition, the finite-horizon DEC-MDP with at least three agents is shown to be NEXP-complete. These complexity results illustrate a fundamental difference between centralized and decentralized control of a Markov process. We briefly discuss the connection between the finite-horizon case and the infinite-horizon case with ``synchronization'''' states, and we suggest a way of reducing this problem to a type of centralized planning problem.