@conference {1510286,
	title = {Team formation for reformation in multiagent domains like RoboCupRescue },
	booktitle = {International Symposium on RoboCup (RoboCup{\textquoteright}02)},
	year = {2002},
	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
signicantly 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.},
	author = {Ranjit Nair and Tambe, Milind and S. Marsella}
}
