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.

本文研究分散控制问题，发现可以通过独立转换、独立观测、面向目标函数的特征来解决该问题。在此基础上，研究了决策者之间的信息共享，提出了间接通信、直接通信和共享状态特征三种交换信息的方式，发现对于所有问题的类别，引入直接或间接通信不会改变最坏情况的复杂性。最终，提出了规划算法以解决这些问题。

协作系统的分散控制：分类和复杂性分析