Decentralized Control of Cooperative Systems: Categorization and
  Complexity Analysis
  Decentralized control of cooperative systems captures the operation of a
group of decision makers that share a single global objective. The difficulty
in solving optimally such problems arises when the agents lack full
observability of the global state of the system when they operate. The general
problem has been shown to be NEXP-complete. In this paper, we identify classes
of decentralized control problems whose complexity ranges between NEXP and P.
In particular, we study problems characterized by independent transitions,
independent observations, and goal-oriented objective functions. Two algorithms
are shown to solve optimally useful classes of goal-oriented decentralized
processes in polynomial time. This paper also studies information sharing among
the decision-makers, which can improve their performance. We distinguish
between three ways in which agents can exchange information: indirect
communication, direct communication and sharing state features that are not
controlled by the agents. Our analysis shows that for every class of problems
we consider, introducing direct or indirect communication does not change the
worst-case complexity. The results provide a better understanding of the
complexity of decentralized control problems that arise in practice and
facilitate the development of planning algorithms for these problems.
