David V. Pynadath and Milind Tambe
Multiagent research has made significant progress in constructing teams of distributed entities (e.g., robots, agents, embedded systems) that act autonomously in the pursuit of common goals. There now exist a variety of prescriptive theories, as well as implemented systems, that can specify good team behavior in different domains. However, each of these theories and systems addresses different aspects of the teamwork problem, and each does so in a different language. In this work, we seek to provide a unified framework that can capture all of the common aspects of the teamwork problem (e.g., heterogeneous, distributed entities, uncertain and dynamic environment), while still supporting analyses of both the optimality of team performance and the computational complexity of the agents’ decision problem. Our COMmunicative Muitiagent Team Decision Problem (COM-MTDP) model provides such a framework for specifying and analyzing distributed teamwork. The COM-MTDP model is general enough to capture many existing models of multiagent systems, and we use this model to provide some comparative results of these theories. We also provide a breakdown of the computational complexity of constructing optimal teams under various classes of problem domains. We then use the COM-MTDP model to compare (both analytically and empirically) two specific coordination theories (joint intentions theory and STEAM) against optimal coordination, in terms of both performance and computational complexity.