Multiagent teamwork

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Multiagent teamwork: analyzing the optimality and complexity of key theories and models

Full text

Pdf (195 KB)

Source

International Conference on Autonomous Agents archive
Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 2 table of contents

Bologna, Italy

SESSION: Session 7C: theories of agency, autonomy, and papers table of contents

Pages: 873 - 880

Year of Publication: 2002

ISBN:1-58113-480-0

Authors

David V. Pynadath	University of Southern California, Marina del Rey, CA
Milind Tambe	University of Southern California, Marina del Rey, CA

Sponsors

ACM: Association for Computing Machinery
SIGART: ACM Special Interest Group on Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 77, Citation Count: 18

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/544862.544946 What is a DOI?

ABSTRACT

Despite the significant progress in multiagent teamwork, existing research does not address the optimality of its prescriptions nor the complexity of the teamwork problem. Thus, we cannot determine whether the assumptions and approximations made by a particular theory gain enough efficiency to justify the losses in overall performance. To provide a tool for evaluating this tradeoff, we present a unified framework, the COMmunicative Multiagent Team Decision Problem (COM-MTDP) model, which is general enough to subsume many existing models of multiagent systems. We analyze use the COM-MTDP model to provide a breakdown of the computational complexity of constructing optimal teams under problem domains divided along the dimensions of observability and communication cost. We then exploit the COM-MTDP's ability to encode existing teamwork theories and models to encode two instantiations of joint intentions theory, including STEAM. We then derive a domain-independent criterion for optimal communication and provide a comparative analysis of the two joint intentions instantiations. We have implemented a reusable, domain-independent software package based COM-MTDPs to analyze teamwork coordination strategies, and we demonstrate its use by encoding and evaluating the two joint intentions strategies within an example domain.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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
	2	Craig Boutilier, Planning, Learning and Coordination in Multiagent Decision Processes, Proceedings of the Sixth Conference on Theoretical Aspects of Rationality and Knowledge, p.195-210, March 17-20, 1996
	3	P.R. Cohen & H.J. Levesque. Teamwork. Nous, 25(4):487--512, 1991
	4	D. Goldberg & M.J. Matarićć. Interference as a tool for designing & evaluating multi-robot controllers. AAAI, 637--642, 1997
	5	Barbara J. Grosz , Sarit Kraus, Collaborative plans for complex group action, Artificial Intelligence, v.86 n.2, p.269-357, Oct. 1996 [doi>10.1016/0004-3702(95)00103-4]
	6	Y.-C. Ho. Team decision theory & information structures. Proc. of the IEEE, 68(6):644--654, 1980
	7	N. R. Jennings, Controlling cooperative problem solving in industrial multi-agent systems using joint intentions, Artificial Intelligence, v.75 n.2, p.195-240, June 1995 [doi>10.1016/0004-3702(94)00020-2]
	8	J. Marschak & R. Radner. The Econ. Theory of Teams. Yale, 1971
	9	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
	10	Charles Rich , Candace L. Sidner, COLLAGEN: when agents collaborate with people, Proceedings of the first international conference on Autonomous agents, p.284-291, February 05-08, 1997, Marina del Rey, California, United States [doi>10.1145/267658.267730]
	11	R.D. Smallwood & E.J. Sondik. The optimal control of POMDPs over a finite horizon. Operations Research, 21:1071--1088, 1973
	12	I.A. Smith & P.R. Cohen. Toward a semantics for an ACL based on speech-acts. AAAI, 24--31, 1996
	13	E. Sonenberg, G. Tidhar, E. Werner, D. Kinny, M. Ljungberg, & A. Rao. Planned team activity. Tech. Rep. 26, Austral. AI Inst., 1994
	14	M. Tambe. Towards flexible teamwork. JAIR, 7:83--124, 1997
	15	M. Tambe , W. Zhang, Towards Flexible Teamwork in Persistent Teams, Proceedings of the 3rd International Conference on Multi Agent Systems, p.277, July 03-07, 1998
	16	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]
	17	J. Yen, J. Yin, T.R. Ioerger, M.S. Miller, D. Xu, & R.A. Volz. CAST: Collab. agents for simulating teamwork. IJCAI, 1135--1142, 2001

CITED BY 18

	Paul Scerri , David Pynadath , Lewis Johnson , Paul Rosenbloom , Mei Si , Nathan Schurr , Milind Tambe, A prototype infrastructure for distributed robot-agent-person teams, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia
	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
	Yu Zhang , Richard A. Volz , Thomas R. loerger , John Yen, A decision-theoretic approach for designing proactive communication in multi-agent teamwork, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
	Matthew E. Gaston , Marie desJardins, Agent-organized networks for dynamic team formation, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands
	Bharanee Rathnasabapathy , Prashant Doshi , Piotr Gmytrasiewicz, Exact solutions of interactive POMDPs using behavioral equivalence, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan
	Tad Hogg, Coordinating microscopic robots in viscous fluids, Autonomous Agents and Multi-Agent Systems, v.14 n.3, p.271-305, June 2007
	Blazej Bulka , Matthew Gaston , Marie Desjardins, Local strategy learning in networked multi-agent team formation, Autonomous Agents and Multi-Agent Systems, v.15 n.1, p.29-45, August 2007
	Niek J. E. Wijngaards , Hidde M. Boonstra , Frances M. T. Brazier, The role of trust in distributed design, Artificial Intelligence for Engineering Design, Analysis and Manufacturing, v.18 n.2, p.199-209, April 2004
	Sarvapali D. Ramchurn , Dong Huynh , Nicholas R. Jennings, Trust in multi-agent systems, The Knowledge Engineering Review, v.19 n.1, p.1-25, March 2004
	Iyad Rahwan , Sarvapali D. Ramchurn , Nicholas R. Jennings , Peter Mcburney , Simon Parsons , Liz Sonenberg, Argumentation-based negotiation, The Knowledge Engineering Review, v.18 n.4, p.343-375, December 2003
	Paul Scerri , Yang Xu , Elizabeth Liao , Justin Lai , Katia Sycara, Scaling Teamwork to Very Large Teams, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.888-895, July 19-23, 2004, New York, New York
	Dmitri Dolgov , Edmund Durfee, Graphical Models in Local, Asymmetric Multi-Agent Markov Decision Processes, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.956-963, July 19-23, 2004, New York, New York
	Christina Theocharopoulou , Ioannis Partsakoulakis , George A. Vouros , Kostas Stergiou, Overlay networks for task allocation and coordination in dynamic large-scale networks of cooperative agents, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii
	Joe Szabo , John Aycock , Randal Acton , Jörg Denzinger, The tale of the weather worm, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil
	Jumpol Polvichai , Paul Scerri , Michael Lewis, An approach to online optimization of heuristic coordination algorithms, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
	Chris Jones , Maja J. Mataric, Utilizing internal state in multi-robot coordination tasks, Proceedings of the 19th national conference on Artifical intelligence, p.958-959, July 25-29, 2004, San Jose, California
	Frans A. Oliehoek , Shimon Whiteson , Matthijs T. J. Spaan, Lossless clustering of histories in decentralized POMDPs, Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems, May 10-15, 2009, Budapest, Hungary
	David V. Pynadath , Stacy C. Marsella, PsychSim: modeling theory of mind with decision-theoretic agents, Proceedings of the 19th international joint conference on Artificial intelligence, p.1181-1186, July 30-August 05, 2005, Edinburgh, Scotland