Winning back the CUP for distributed POMDPs: planning over continuous belief spaces

ABSTRACT

Distributed Partially Observable Markov Decision Problems (Distributed POMDPs) are evolving as a popular approach for modeling multiagent systems, and many different algorithms have been proposed to obtain locally or globally optimal policies. Unfortunately, most of these algorithms have either been explicitly designed or experimentally evaluated assuming knowledge of a starting belief point, an assumption that often does not hold in complex, uncertain domains. Instead, in such domains, it is important for agents to explicitly plan over continuous belief spaces. This paper provides a novel algorithm to explicitly compute finite horizon policies over continuous belief spaces, without restricting the space of policies. By marrying an efficient single-agent POMDP solver with a heuristic distributed POMDP policy-generation algorithm, locally optimal joint policies are obtained, each of which dominates within a different part of the belief region. We provide heuristics that significantly improve the efficiency of the resulting algorithm and provide detailed experimental results. To the best of our knowledge, these are the first run-time results for analytically generating policies over continuous belief spaces in distributed POMDPs.

REFERENCES

• 1: M. L. Littman A. R. Cassandra and N. L. Zhang. Incremental pruning: A simple, fast, exact method for partially observable markov decision processes. In UAI, 1997.
• 2: Raphen Becker , Shlomo Zilberstein , Victor Lesser , Claudia V. Goldman, Transition-independent decentralized markov decision processes, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860583]
• 3: 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
• 4: I. Chadès, B. Scherrer, and F. Charpillet. A heuristic approach for solving decentralized-pomdp: Assessment on the pursuit problem. In SAC, 2002.
• 5: Zhengzhu Feng , Shlomo Zilberstein, Region-based incremental pruning for POMDPs, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.146-153, July 07-11, 2004, Banff, Canada
• 6: Claudia V. Goldman , Shlomo Zilberstein, Optimizing information exchange in cooperative multi-agent systems, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860598]
• 7: D. Bernstein; E. Hansen; and S. Zilberstein. Bounded policy iteration for decentralized pomdps. In IJCAI, 2005.
• 8: Eric A. Hansen, Daniel S. Bernstein, and Shlomo Zilberstein. Dynamic programming for partially observable stochastic games. In AAAI, 2004.
• 9: Leslie Pack Kaelbling , Michael L. Littman , Anthony R. Cassandra, Planning and acting in partially observable stochastic domains, Artificial Intelligence, v.101 n.1-2, p.99-134, May 1998 [doi>10.1016/S0004-3702(98)00023-X ]
• 10: R. E. Montemerlo, G. Gordon, J. Schneider, and S. Thrun. Approximate solutions for partially observable stochastic games with common payoffs. In AAMAS, 2004.
• 11: R. Nair, D. Pynadath, M. Yokoo, M. Tambe, and S. Marsella. Taming decentralized POMDPs: Towards efficient policy computation for multiagent settings. In IJCAI, 2003.
• 12: Ranjit Nair , Maayan Roth , Makoto Yohoo, Communication for Improving Policy Computation in Distributed POMDPs, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1098-1105, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.88]
• 13: Ranjit Nair , Milind Tambe , Stacy Marsella, Role allocation and reallocation in multiagent teams: towards a practical analysis, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860664]
• 14: R. Nair, P. Varakantham, M. Tambe, and M. Yokoo. Networked distributed POMDPs: A synthesis of distributed constraint optimization and POMDPs. In AAAI, 2005.
• 15: Pradeep Varakantham , Rajiv Maheswaran , Milind Tambe, Exploiting belief bounds: practical POMDPs for personal assistant agents, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082621]
• 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: D. V. Pynadath and M. Tambe. The communicative multiagent team decision problem: Analyzing teamwork theories and models. JAIR, 16:389--423, 2002.
• 18: Ping Xuan , Victor Lesser , Shlomo Zilberstein, Communication decisions in multi-agent cooperation: model and experiments, Proceedings of the fifth international conference on Autonomous agents, p.616-623, May 2001, Montreal, Quebec, Canada [doi>10.1145/375735.376469]

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
continuous initial beliefs, distributed POMDP, multi-agent systems, partially observable Markov decision process (POMDP)