Team formation for reformation in multiagent domains like RoboCupRescue

Abstract:

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. They are very important issues in RoboCupRescue where many tasks need to be done jointly. While empirical comparisons (e.g., in a competition setting as in RoboCup) are useful, we need a quantitative analysis beyond the competition | to understand the strengths and limitations of dierent approaches, and their tradeos as we scale up the domain or change domain properties. To this end, we need to provide complexityoptimality tradeos, which have been lacking not only in RoboCup but in the multiagent eld in general. To alleviate these diculties, this paper presents R-COM-MTDP, a formal model based on decentralized communicating POMDPs, where agents explicitly take on and change roles to (re)form teams. R-COM-MTDP signicantly extends an earlier COM-MTDP model, by introducing roles and local states to better model domains like RoboCupRescue where agents can take on dierent roles and each agent has a local state consisting of the ob jects in its vicinity. R-COM-MTDP tells us where the problem is highly intractable (NEXP-complete) and where it can be tractable (P-complete), and thus understand where algorithms may need to tradeo optimality and where they could strive for near optimal behaviors. R-COM-MTDP model could enable comparison of various team formation and reformation strategies | including the strategies used by our own teams that came in the top three in 2001 | in the RoboCup Rescue domain and beyond.