A Formal Study of Coordination and Control of Collaborative Multi-Agent Systems
Sponsored by:
National Science Foundation,
Division of Information & Intelligent Systems
Shlomo Zilberstein, PI, Victor Lesser, CoPI
Project Description
This project is concerned with the development of a decision-theoretic framework for planning and control of multi-agent systems by formalizing the problem as a decentralized Markov process. It applies to a wide range of application domains in which decision-making must be performed by multiple collaborating agents such as information gathering, distributed sensing, coordination of multiple robots, as well as the operation of complex human organizations. While substantial progress has been made in planning and control of single agents using MDPs, a similar formal treatment of multi-agent systems has been lacking. Existing techniques tend to avoid a central issue: agents typically have different information about the overall system and they cannot share all this information all the time. Sharing information has a cost that must be factored into the overall decision process. Three approaches to communication are studied based on (1) a cost/benefit analysis of the amount of communication, (2) search in policy space, and (3) transformations of the more tractable centralized policies into decentralized policies. The resulting techniques are evaluated in the context of several realistic applications. This research facilitates a better understanding of the strengths and limitations of existing heuristic approaches to coordination and offers new approaches based on more formal underpinnings.
Related Publications
- Learning to Communicate in a Decentralized Environment.
C.V. Goldman, M. Allen, and S. Zilberstein. Autonomous Agents and Multi-Agent Systems, 15(1):47-90, 2007. [abs] [bib] [pdf]
- Improved Memory-Bounded Dynamic Programming for Decentralized POMDPs.
S. Seuken and S. Zilberstein. Proceedings of the Twenty Third Conference on Uncertainty in Artificial Intelligence (UAI), Vancouver, British Columbia, 2007. [abs] [bib] [pdf]
- Bounded Dynamic Programming for Decetralized POMDPs.
C. Amato, A. Carlin, and S. Zilberstein. AAMAS Workshop on Multi-Agent Sequential Decision Making in Uncertain Domains, Honolulu, Hawaii, May, 2007. [abs] [bib] [pdf]
- Solving POMDPs Using Quadratically Constrained Linear Programs.
C. Amato, D.S. Bernstein, and S. Zilberstein. Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI), 2418-2424, Hyderabad, India, 2007. [abs] [bib] [pdf]
- Memory-Bounded Dynamic Programming for DEC-POMDPs.
S. Seuken and S. Zilberstein. Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI), 2009-2015, Hyderabad, India, 2007. [abs] [bib] [pdf]
- Optimal Fixed-Size Controllers for Decentralized POMDPs.
C. Amato, D.S. Bernstein, and S. Zilberstein. AAMAS Workshop on Multi-Agent Sequential Decision Making in Uncertain Domains, Hakodate, Japan, May, 2006. [abs] [bib] [pdf]
- Analyzing Myopic Approaches for Multi-Agent Communication.
R. Becker, V. Lesser, and S. Zilberstein. Proceedings of Intelligent Agent Technology (IAT), 550-557, Compiègne, France, 2005. (Best Paper Award) [abs] [bib] [pdf]
- Bounded Policy Iteration for Decentralized POMDPs.
D.S. Bernstein, E.A. Hansen, and S. Zilberstein. Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI), 1287-1292, Edinburgh, Scotland, 2005. [abs] [bib] [pdf]
- MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs.
D. Szer, F. Charpillet, and S. Zilberstein. Proceedings of the Twenty First Conference on Uncertainty in Artificial Intelligence (UAI), 576-583, Edinburgh, Scotland, 2005. [abs] [bib] [pdf]
- Decentralized Control of Cooperative Systems: Categorization and Complexity Analysis.
C.V. Goldman and S. Zilberstein. Journal of Artificial Intelligence Research, 22:143-174, 2004. [abs] [bib] [pdf]
- Dynamic Programming for Partially Observable Stochastic Games.
E.A. Hansen, D.S. Bernstein, and S. Zilberstein. Proceedings of the Nineteenth National Conference on Artificial Intelligence (AAAI), 709-715, San Jose, California, 2004. [abs] [bib] [pdf]
- Decentralized Markov Decision Processes with Event-Driven Interactions.
R. Becker, S. Zilberstein, and V. Lesser. Proceedings of the Third International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS), 302-309, New York City, 2004. [abs] [bib] [pdf]
- Dynamic Programming for Decentralized POMDPs.
D.S. Bernstein, E.A. Hansen, S. Zilberstein, and C. Amato. AAAI Spring Symposium on Bridging the Multi-Agent and Multi-Robot Research Gap, Stanford, California, 2004. [abs] [>bib] [pdf]
- Transition-Independent Decentralized Markov Decision Processes.
R. Becker, S. Zilberstein, V. Lesser, and C.V. Goldman. Proceedings of the Second International Conference on Autonomous Agents and Multi Agent Systems (AAMAS), 41-48, Melbourne, Australia, 2003. (Best Paper Award) [abs] [bib] [pdf]
- Optimizing Information Exchange in Cooperative Multi Agent Systems.
C.V. Goldman and S. Zilberstein. Proceedings of the Second International Conference on Autonomous Agents and Multi Agent Systems (AAMAS), 137-144, Melbourne, Australia, 2003. [abs] [bib] [pdf]
- The Complexity of Decentralized Control of Markov Decision Processes.
D.S. Bernstein, R. Givan, N. Immerman, and S. Zilberstein. Mathematics of Operations Research, 27(4):819-840, 2002. [abs] [bib] [pdf]
