Teamwork in Distributed POMDPs: Execution-time Coordination Under Model Uncertainty

Despite their worst-case NEXP-complete planning complexity, DEC-POMDPs remain a popular framework for multiagent teamwork. This paper introduces effective teamwork under model uncertainty (i. e. , potentially inaccurate transition and observation functions) as a novel challenge for DEC-POMDPs and presents MODERN, the first execution-centric framework for DEC-POMDPs explicitly motivated by addressing such model uncertainty. MODERN's shift of coordination reasoning from planning-time to execution-time avoids the high cost of computing optimal plans whose promised quality may not be realized in practice. There are three key ideas in MODERN: (i) it maintains an exponentially smaller model of other agents' beliefs and actions than in previous work and then further reduces the computation-time and space expense of this model via bounded pruning; (ii) it reduces execution-time computation by exploiting BDI theories of teamwork, and limits communication to key trigger points; and (iii) it limits its decision-theoretic reasoning about communication to trigger points and uses a systematic markup to encourage extra communication at these points - thus reducing uncertainty among team members at trigger points.

Authors

• Jun-young Kwak University of Southern California
• Rong Yang University of Southern California
• Zhengyu Yin University of Southern California
• Matthew E. Taylor University of Alberta Alberta Machine Intelligence Institute (Amii)
• Milind Tambe Harvard University Google Research

Keywords

• Distributed POMDPs
• Model Uncertainty
• Teamwork