Definition: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
Input: Planning for distributed agents with partial state information is considered from a decision­ theoretic perspective. We describe generaliza­ tions of both the MDP and POMDP models that allow for decentralized control. For even a small number of agents, the finite-horizon prob­ lems corresponding to both of our models are complete for nondeterministic exponential time. These complexity results illustrate a fundamen­ tal difference between centralized and decentral­ ized control of Markov processes. In contrast to the MDP and POMDP problems, the problems we consider provably do not admit polynomial­ time algorithms and most likely require doubly exponential time to solve in the worst case. We have thus provided mathematical evidence corre­ sponding to the intuition that decentralized plan­ ning problems cannot easily be reduced to cen­ tralized problems and solved exactly using estab­ lished techniques.

The Complexity of Decentralized Control of Markov Decision Processes