Team Formation for Reformation
Ramjit Nair, Milind Tambe, Stacy Marsella · 2002
As tasks change and members of the team fail, the current team needs to evolve to handle the changes. In both the sensor network domain and RoboCup Rescue, each re-organization of the team requires time (e.g., fire-brigades may need to drive to a new location) and is hence expensive because of the need for quick response. Clearly, the current configuration of agents is relevant to how quickly and well they can be re-organized in the future. Each re-organization of the teams should be such that the resulting team is effective at performing the existing tasks but also flexible enough to adapt to new scenarios quickly. We refer to this reorganization of the team as "Team Formation for Reformation". In order to solve the ``Team Formation for Reformation'' problem, we present R-COM-MTDPs (Roles and Communication in a Markov Team Decision Process), a formal model based on communicating decentralized POMDPs, to address the above shortcomings. R-COM-MTDP significantly extends an earlier model called COM-MTDP, by making important additions of roles and agents' local states, to more closely model current complex multiagent teams. Thus, R-COM-MTDP provides decentralized optimal policies to take up and change roles in a team (planning ahead to minimize reorganization costs), and to execute such roles. R-COM-MTDPs provide a general tool to analyze role-taking and role-executing policies in multiagent teams. We show that while generation of optimal policies in R-COM-MTDPs is NEXP-complete, different communication and observability conditions significantly reduce such complexity. In this paper, we use the disaster rescue domain to motivate the ``Team Formation for Reformation'' problem. We present real world scenarios where such an approach would be useful and use the RoboCup Rescue Simulation Environment to explain the working of our model.