Reasoning about joint beliefs for execution-time communication decisions

ABSTRACT

Just as POMDPs have been used to reason explicitly about uncertainty in single-agent systems, there has been recent interest in using multi-agent POMDPs to coordinate teams of agents in the presence of uncertainty. Although multi-agent POMDPs are known to be highly intractable, communication at every time step transforms a multi-agent POMDP into a more tractable single-agent POMDP. In this paper, we present an approach that generates "centralized" policies for multi-agent POMDPs at plan-time by assuming the presence of free communication, and at run-time, handles the problem of limited communication resources by reasoning about the use of communication as needed for effective execution. This approach trades off the need to do some computation at execution-time for the ability to generate policies more tractably at plan-time. In our algorithm, each agent, at run-time, models the distribution of possible joint beliefs. Joint actions are selected over this distribution, ensuring that agents remain synchronized. Communication is used to integrate local observations into the team belief only when those observations would improve team performance. We show, both through a detailed example and with experimental results, that our approach allows for effective decentralized execution while avoiding unnecessary instances of communication.

REFERENCES

• 1: 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]
• 2: 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
• 3: A. R. Cassandra. POMDP solver software. http://www.cassandra.org/pomdp/code/index.shtml.
• 4: Rosemary Emery-Montemerlo , Geoff Gordon , Jeff Schneider , Sebastian Thrun, Approximate Solutions for Partially Observable Stochastic Games with Common Payoffs, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.136-143, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.67]
• 5: D. Goldberg, V. Cicirello, M. B. Dias, R. Simmons, S. Smith, T. Smith, and A. Stentz. A distributed layered architecture for mobile robot coordination: Application to space exploration. In International NASA Workshop on Planning and Scheduling for Space, 2002.
• 6: C. V. Goldman and S. Zilberstein. Decentralized control of cooperative systems: Categorization and complexity analysis. Journal of AI Research, 2004.
• 7: E. A. Hansen, D. S. Bernstein, and S. Zilberstein. Dynamic programming for partially observable stochastic games. In National Conference on Artificial Intelligence, 2004.
• 8: 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]
• 9: M. L. Littman, A. R. Cassandra, and L. P. Kaelbling. Learning policies for partially observable environments: Scaling up. In International Conference on Machine Learning, 1995.
• 10: R. Nair, D. Pynadath, M. Yokoo, M. Tambe, and S. Marsella. Taming decentralized POMDPs: Towards efficient policy computation for multiagent settings. In International Joint Conference on Artificial Intelligence, 2003.
• 11: 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]
• 12: R. Nair, M. Tambe, and S. Marsella. Team formation for reformation in multiagent domains like RoboCupRescue. In RoboCup-2002 International Symposium, 2003.
• 13: Christos Papadimitriou , John N. Tsisiklis, The complexity of Markov decision processes, Mathematics of Operations Research, v.12 n.3, p.441-450, August 1, 1987 [doi>10.1287/moor.12.3.441]
• 14: 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
• 15: Pascal Poupart , Luis E. Ortiz , Craig Boutilier, Value-Directed Sampling Methods for POMDPs, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.453-461, August 02-05, 2001
• 16: D. V. Pynadath and M. Tambe. The communicative multiagent team decision problem: Analyzing teamwork theories and models. Journal of AI Research, 2002.
• 17: M. Roth, D. Vail, and M. Veloso. A real-time world model for multi-robot teams with high-latency communication. In International Conference on Intelligent Robots and Systems, 2003.
• 18: S. Thrun. Monte Carlo POMDPs. In Neural Information Processing Systems, 2000.
• 19: Ping Xuan , Victor Lesser, Multi-agent policies: from centralized ones to decentralized ones, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 3, July 15-19, 2002, Bologna, Italy [doi>10.1145/545056.545078]
• 20: P. Xuan, V. Lesser, and S. Zilberstein. Formal modeling of communication decisions in cooperative multiagent systems. In Workshop on Game-Theoretic and Decision-Theoretic Agents, 2000.

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
POMDP, communication, distributed execution, robot teams