A Formal Study of Coordination and Control of Collaborative Multi-Agent Systems
Shlomo Zilberstein, PI, Victor Lesser, CoPI
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.
- Learning to Communicate in a Decentralized Environment.
- Improved Memory-Bounded Dynamic Programming for Decentralized POMDPs.
- Bounded Dynamic Programming for Decetralized POMDPs.
- Solving POMDPs Using Quadratically Constrained Linear Programs.
- Memory-Bounded Dynamic Programming for DEC-POMDPs.
- Optimal Fixed-Size Controllers for Decentralized POMDPs.
- Analyzing Myopic Approaches for Multi-Agent Communication.
- 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.
- Decentralized Control of Cooperative Systems: Categorization and Complexity Analysis.
- Dynamic Programming for Partially Observable Stochastic Games.
- Decentralized Markov Decision Processes with Event-Driven Interactions.
- Dynamic Programming for Decentralized POMDPs.
- 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.
- The Complexity of Decentralized Control of Markov Decision Processes.