Decentralized Control of Cooperative Systems:
Categorization and Complexity Analysis
Claudia V. Goldman
Shlomo Zilberstein
Abstract
Decentralized control of cooperative systems captures the operation of a
group of
decision-makers that share a single global objective. The diffculty 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.
Download
[pdf]