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 pr...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of artificial intelligence research 2004-01, Vol.22, p.143-174
Main Authors: Goldman, C. V., Zilberstein, S.
Format: Article
Language:English
Subjects:
Algorithms
Artificial intelligence
Communication
Complexity
Control systems
Cooperative control
Decentralized control
Decision making
Mathematical analysis
Polynomials
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1076-9757
1076-9757
1943-5037
DOI:10.1613/jair.1427