Communicative Multiagent Team Decision Problems (COM-MTDPs)

<body> <! bgcolor="#999999" TEXT="#000000" LINK="#B30E14" VLINK="#FFAF18" ALINK="#FFAF18"> <CENTER> <TABLE BGCOLOR="ffaf18" WIDTH="100%" BORDER="5" BORDERCOLOR="b30e14" BORDERCOLORDARK="a70208" BORDERCOLORLIGHT="bf1a20"> <TR><TD ALIGN="center"><FONT SIZE="+3" COLOR="b30e14"><STRONG>Communicative Multiagent Team Decision Problems (COM-MTDPs)</STRONG></FONT></TD></TR> </TABLE> <H3><A HREF="/~pynadath/">David V. Pynadath</A> and <A HREF="/~tambe/">Milind Tambe</A></H3> <A HREF="http://agents.usc.edu/"><IMG SRC="/teamcore/agents@usc.gif" WIDTH="173" HEIGHT="40"/></A> </CENTER> <hr> <P>This work is one of our many ongoing research threads in <A HREF="/teamcore/Teamwork" TARGET="main">agent teamwork</A>. </P> <H3>Abstract</H3> <P>Despite the significant progress in multiagent teamwork, existing research does not address the <EM>optimality</EM> of its prescriptions nor the <EM>complexity</EM> of the teamwork problem in a domain-independent fashion. Without a characterization of the optimality-complexity tradeoffs, it is impossible to 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 use by multiagent researchers in evaluating this tradeoff, we present a unified framework, the <EM>COMmunicative Multiagent Team Decision Problem (COM-MTDP)</EM> model, for analyzing agent teamwork. The COM-MTDP model is general enough to subsume many existing models of multiagent systems, and we can use it to analyze both the optimality of team performance and the computational complexity of the agents' decision problem. In analyzing complexity, we present a breakdown of the computational complexity of constructing optimal teams under various classes of problem domains, along the dimensions of observability and communication cost. In analyzing optimality, we 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 to analyze teamwork coordination strategies, and we demonstrate its use by encoding and evaluating the two joint intentions strategies within a testbed domain. </P> <A NAME="papers"> <H3>Publications</H3> <TABLE WIDTH="100%" CELLPADDING="15" BORDER="3"> <TR><TD> <A HREF="/~pynadath/">D.V. Pynadath</A> and <A HREF="/~tambe">M. Tambe</A>, 2002.<BR> <A HREF="http://www.jair.org/abstracts/pynadath02a.html"><STRONG>The Communicative Multiagent Team Decision Problem: Analyzing Teamwork Theories and Models</STRONG></A>.<BR> <EM><A HREF="http://www.jair.org/">Journal of Artificial Intelligence Research</A></EM>, Volume 16, pp. 389-423. </TD></TR> <TR><TD BGCOLOR="#c5c5c5"> <A HREF="/~pynadath/">D.V. Pynadath</A> and <A HREF="/~tambe">M. Tambe</A>, 2002.<BR> <A HREF="/teamcore/COM-MTDP/aamas02.pdf"><STRONG>Multiagent Teamwork: Analyzing the Optimality and Complexity of Key Theories and Models</STRONG></A>.<BR> In <EM>Proceedings of the <A HREF="http://www.autonomousagents.org/2002/">International Joint Conference on Autonomous Agents and Multi-Agent Systems</A></EM>, pp. 873-880. </TD></TR> <TR><TD> <A HREF="/~pynadath/">D.V. Pynadath</A> and <A HREF="/~tambe">M. Tambe</A>, 2002.<BR> <STRONG>Team Coordination among Distributed Agents: Analyzing Key Teamwork Theories and Models</STRONG>.<BR> In <EM>Proceedings of the AAAI Spring Symposium on Intelligent Distributed and Embedded Systems</EM>, pp. 57-62. </TD></TR> </TABLE> <A NAME="theory"> <H3>Theorems</H3> <P>The JAIR article includes all of the proofs for its theorems. The following are detailed proofs omitted from the <A HREF="aamas02.pdf">AAMAS-02 paper</A> (using that paper's earlier notation), available below as PDF documents:<UL> <LI> <A HREF="./theorem1.pdf">Theorem 1</A> </LI> <LI> <A HREF="./theorem2.pdf">Theorem 2</A> </LI> <LI> <A HREF="./theorem3.pdf">Theorem 3</A> </LI> <LI> <A HREF="./theorem4.pdf">Theorem 4</A> </LI> <LI> <A HREF="./theorem5.pdf">Theorem 5</A> </LI> <LI> <A HREF="./theorem6.pdf">Theorem 6</A> </LI> </UL> </P> <A NAME="software"> <H3>Software</H3> <P>We have implemented the COM-MTDP model as a <A HREF="http://www.python.org">Python</A> class, allowing one to instantiate a particular problem domain as an object of this class. The following class files support the setting up of the various components of an COM-MTDP: <UL> <LI> <A HREF="./COMMTDP.py">COMMTDP.py</A> </LI> <LI> <A HREF="./States.py">States.py</A> </LI> </UL> The following class file supports the construction of policies of behavior: <UL> <LI> <A HREF="./Policy.py">Policy.py</A> </LI> </UL> The following class file provides the code used to set up and evaluate the example domain from the article: <UL> <LI> <A HREF="./HeloScenario.py">HeloScenario.py</A> </LI> </UL> <A HREF="/teamcore/doc/COM-MTDP/">Documentation</A> is (or will soon be) available. If you have any comments, questions, or improvements, please <A HREF="mailto:pynadath@isi.edu">let us know</A>. Thanks and enjoy! </P> </body> </html>