Readers of your mailing list may be interested in the following article
recently published by JAIR:
Goldman, C.V. and Zilberstein, S. (2004)
"Decentralized Control of Cooperative Systems: Categorization and
Complexity Analysis",
Volume 22, pages 143-174.
For quick access via your WWW browser, use this URL:
http://www.jair.org/abstracts/goldman04a.html
<http://www.jair.org/abstracts/goldman04a.html>
Abstract:
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.
The article is available via:
-- comp.ai.jair.papers (also see comp.ai.jair.announce)
-- World Wide Web: The URL for our World Wide Web server is
http://www.jair.org/ <http://www.jair.org/>
For direct access to this article and related files try:
http://www.jair.org/abstracts/goldman04a.html
<http://www.jair.org/abstracts/goldman04a.html>
-- Anonymous FTP from Carnegie-Mellon University (USA):
ftp://ftp.cs.cmu.edu/project/jair/volume22/goldman04a.ps
<ftp://ftp.cs.cmu.edu/project/jair/volume22/goldman04a.ps>
The compressed PostScript file is named goldman04a.ps.Z
For more information about JAIR, visit our WWW or FTP sites, or contact
[EMAIL PROTECTED]
