Solving multiagent assignment Markov decision processes

ABSTRACT

We consider the setting of multiple collaborative agents trying to complete a set of tasks as assigned by a centralized controller. We propose a scalable method called "Assignment-based decomposition" which is based on decomposing the problem of action selection into an upper assignment level and a lower task execution level. The assignment problem is solved by search, while the task execution is solved through coordinated reinforcement learning. We show that this decomposition of the overall problem into two levels scales well and outperforms the state-of-the-art approaches including pure assignment-level search or pure coordinated reinforcement learning. We also show how this approach enables transfer learning from domains with few agents to domains with many agents.

REFERENCES

• 1: R. Becker, S. Zilberstein, and C. V. Goldman. Solving transition independent decentralized markov decision processes. JAIR, 22:423--455, 2004.
• 2: D. Dolgov and E. Durfee. Optimal resource allocation and policy formulation in loosely-coupled markov decision processes. In AAMAS '04, pages 315--324, June 2004.
• 3: C. V. Goldman and S. Zilberstein. Decentralized control of control of cooperative systems: Categorization and complexity analysis. JAIR, 22:143--174, 2004.
• 4: C. Guestrin, D. Koller, and R. Parr. Multiagent planning with factored MDPs. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, NIPS '01, pages 1523--1530. MIT Press, 2001.
• 5: Carlos Guestrin , Michail G. Lagoudakis , Ronald Parr, Coordinated Reinforcement Learning, Proceedings of the Nineteenth International Conference on Machine Learning, p.227-234, July 08-12, 2002
• 6: Carlos Guestrin , Shobha Venkataraman , Daphne Koller, Context-specific multiagent coordination and planning with factored MDPs, Eighteenth national conference on Artificial intelligence, p.253-259, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 7: Jelle R. Kok , Nikos Vlassis, Sparse cooperative Q-learning, Proceedings of the twenty-first international conference on Machine learning, p.61, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015410]
• 8: Jelle R. Kok , Nikos Vlassis, Collaborative Multiagent Reinforcement Learning by Payoff Propagation, The Journal of Machine Learning Research, 7, p.1789-1828, 12/1/2006
• 9: Rajbala Makar , Sridhar Mahadevan , Mohammad Ghavamzadeh, Hierarchical multi-agent reinforcement learning, Proceedings of the fifth international conference on Autonomous agents, p.246-253, May 2001, Montreal, Quebec, Canada [doi>10.1145/375735.376302]
• 10: Nicolas Meuleau , Milos Hauskrecht , Kee-Eung Kim , Leonid Peshkin , Leslie Pack Kaelbling , Thomas Dean , Craig Boutilier, Solving very large weakly coupled Markov decision processes, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.165-172, July 1998, Madison, Wisconsin, United States
• 11: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 12: S. Proper and P. Tadepalli. Scaling model-based average-reward reinforcement learning for product delivery. In ECML '06, pages 735--742, 2006.
• 13: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 14: Martin Wainwright , Tommi Jaakkola , Alan Willsky, Tree consistency and bounds on the performance of the max-product algorithm and its generalizations, Statistics and Computing, v.14 n.2, p.143-166, April 2004 [doi>10.1023/B:STCO.0000021412.33763.d5]
• 15: Jonathan S. Yedidia , William T. Freeman , Yair Weiss, Understanding belief propagation and its generalizations, Exploring artificial intelligence in the new millennium, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 16: Xinhua Zhang , Douglas Aberdeen , S. V. N. Vishwanathan, Conditional random fields for multi-agent reinforcement learning, Proceedings of the 24th international conference on Machine learning, p.1143-1150, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273640]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Algorithms, Experimentation

Keywords:
Markov decision processes, assignment problem, coordination graphs, reinforcement learning