Model for Team Formation for Reformation in Multiagent Systems
Ranjit Nair, Milind Tambe, Stacy Marsella, David V. Pynadath · 2002
Team formation, i.e., allocating agents to roles within a team or subteams of a team, and the reorganization of a team upon team member failure or arrival of new tasks are critical aspects of teamwork. We focus in par-ticular on a technique called ”Team Formation for Ref-ormation”, i.e., teams formed with lookahead to mini-mize costs of reformation. Despite significant progress, research in multiagent team formation and reorgani-zation has failed to provide a rigorous analysis of the computational complexities of the approaches proposed or their degree of optimality. This shortcoming has hin-dered quantitative comparisons of approaches or their complexity-optimality tradeoffs, e.g., is the team reor-ganization approach in practical teamwork models such as STEAM optimal in most cases or only as an excep-tion? To alleviate these difficulties, this paper presents R-COM-MTDP, a formal model based on decentral-ized communicating POMDPs, where agents explicitly take on and change roles to (re)form teams. R-COM-MTDP significantly extends an earlier COM-MTDP model, by analyzing how agents ’ roles, local states and reward decompositions gradually reduce the complex-ity of its policy generation from NEXP-complete to PSPACE-complete to P-complete. We also encode key role reorganization approaches (e.g., STEAM) as R-COM-MTDP policies, and compare them with a locally optimal policy derivable in R-COM-MTDP, thus, the-oretically and empirically illustrating the complexity-optimality tradeoffs.