Planning with continuous resources for agent teams

ABSTRACT

Many problems of multiagent planning under uncertainty require distributed reasoning with continuous resources and resource limits. Decentralized Markov Decision Problems (Dec-MDPs) are well-suited to address such problems, but unfortunately, prior Dec-MDP approaches either discretize resources at the expense of speed and quality guarantees, or avoid discretization only by limiting agents' action choices or interactions (e.g. assumption of transition independence). To address these shortcomings, this paper proposes M-DPFP, a novel algorithm for planning with continuous resources for agent teams, with three key features: (i) it maintains the agent team interaction graph to identify and prune the suboptimal policies and to allow the agents to be transition dependent, (ii) it operates in a continuous space of probability functions to provide the error bound on the solution quality and finally (iii) it focuses the search for policies on the most relevant parts of this search space to allow for a systematic trade-off of solution quality for speed. Our experiments show that M-DPFP finds high quality solutions and exhibits superior performance when compared with a discretization-based approach. We also show that M-DPFP is applicable to solving problems that are beyond the scope of existing approaches.

REFERENCES

• 1: Raphen Becker , Shlomo Zilberstein , Victor Lesser, Decentralized Markov Decision Processes with Event-Driven Interactions, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.302-309, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.100]
• 2: R. Becker, S. Zilberstein, V. Lesser, and C. V. Goldman. Transition-Independent Dec-MDPs. In AAMAS, 2003.
• 3: E. Benazera. Solving decentralized continuous Markov decision problems with structured reward. In KI, 2007.
• 4: Daniel S. Bernstein , Shlomo Zilberstein , Neil Immerman, The Complexity of Decentralized Control of Markov Decision Processes, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.32-37, June 30-July 03, 2000
• 5: Aurélie Beynier , Abdel-Illah Mouaddib, An iterative algorithm for solving constrained decentralized Markov decision processes, proceedings of the 21st national conference on Artificial intelligence, p.1089-1094, July 16-20, 2006, Boston, Massachusetts
• 6: K. Decker and V. Lesser. Designing a Family of Coordination Algorithms. ICMAS-95, January 1995.
• 7: Zhengzhu Feng , Richard Dearden , Nicolas Meuleau , Richard Washington, Dynamic programming for structured continuous Markov decision problems, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.154-161, July 07-11, 2004, Banff, Canada
• 8: L. Li and M. Littman. Lazy approximation for solving continuous finite-horizon MDPs. In AAAI, 2005.
• 9: J. Marecki, S. Koenig, and M. Tambe. A fast analytical algorithm for solving MDPs with real-valued resources. In IJCAI, 2007.
• 10: Janusz Marecki , Milind Tambe, On opportunistic techniques for solving decentralized Markov decision processes with temporal constraints, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329389]
• 11: J. Marecki and M. Tambe. Towards faster planning with continuous resources in stochastic domains. In AAAI, 2008.
• 12: Mausam, E. Benazera, R. I. Brafman, N. Meuleau, and E. A. Hansen. Planning with continuous resources in stochastic domains. In IJCAI, 2005.
• 13: D. Musliner, E. Durfee, J. Wu, D. Dolgov, R. Goldman, and M. Boddy. Coordinated plan management using multiagent MDPs. In AAAI Spring Symposium, 2006.
• 14: R. Nair, M. Tambe, M. Yokoo, D. Pynadath, and S. Marsella. Taming decentralized POMDPs: Towards efficient policy computation for multiagent settings. In IJCAI, 2003.
• 15: R. Nair, P. Varakantham, M. Tambe, and M. Yokoo. Networked distributed POMDPs: A synergy of distributed constraint optimization and POMDPs. In IJCAI, 2005.
• 16: Leonid Peshkin , Kee-Eung Kim , Nicolas Meuleau , Leslie Pack Kaelbling, Learning to Cooperate via Policy Search, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.489-496, June 30-July 03, 2000
• 17: Pradeep Varakantham , Janusz Marecki , Yuichi Yabu , Milind Tambe , Makoto Yokoo, Letting loose a SPIDER on a network of POMDPs: generating quality guaranteed policies, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329388]
• 18: Håkan L. S. Younes , Reid G. Simmons, Solving generalized semi-Markov decision processes using continuous phase-type distributions, Proceedings of the 19th national conference on Artifical intelligence, p.742-747, July 25-29, 2004, San Jose, California

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
continuous resources, decentralized Markov decision process, multi-agent systems