We achieve collaboration between agents through the introduction of formations as a team structure. A formation decomposes the task space defining a set of roles. Formations include as many roles as there are agents in the team, so that each role is filled by one agent. In addition, formations can specify sub-formations, or units, that do not involve the whole team. A unit consists of a subset of roles from the formation, a captain, and intra-unit interactions among the roles.
For a team of n agents 
, any formation
is of the form 
where R is a set
of roles 
such that 
. Note that there are the same number of roles as there
are agents. Each unit 
is a subset of R: 
such that 
, 
and 
is the captain.
The map 
is not pre-specified: roles can be filled by
different homogeneous agents. A single role may be a part of any
number of units and formations.
Formations can affect the agent's external behaviors by specifying inter-role interactions. Since roles can be re-used among formations, their formation-specific interactions cannot be included in the role definitions. Instead these interactions are part of the formation specification.
Units are used to deal with local problem solving issues. Rather than involving the entire team in a sub-problem, the roles that address it are organized into a unit.
Roles and formations are introduced independently from the agents that
are to fill them. The locker-room agreement specifies an initial
formation, a map from agents to roles, and run-time triggers for
dynamic changing of formations. At any given time, each agent should
know what formation the team is currently using. Agents keep mappings
from teammates to roles in the current formation. All
this team structuring information is stored in the agent's internal
state. It can be altered via the agent's internal behaviors. Thus, in
all, the locker-room agreement is used to coordinate task
decomposition among agents, to coordinate dynamic team re-alignment
during time-critical stages, and for defining pre-compiled multi-agent
plans. The locker-room agreement can be hard-wired or it can be the
result of automatic deliberative multi-agent
planning. Figure 3 illustrates a team of agents smoothly
switching roles and formations over time.
Figure 3: Flexible roles and formations. Different roles are
represented as differently shaded circles. Formations are possibly
overlapping collections of roles. All roles and formations are known
to all players. A player's current role is indicated by the shaded
circle in its head and its current formation is indicated by an arrow
to the formation. The players first switch roles while staying in the
same formation; then they switch to an entirely new formation.
Since agents are autonomous and operating in a PTS domain, during the
periods of limited communication there is no guarantee that they will all
think that the team is using the same formation, nor that they have
accurate maps 
. In fact, the only guarantee is that each
agent knows its own current role. Efficient low-bandwidth
communication protocols allow agents to inform each other of their
roles periodically. Further details on our implemented low-bandwidth
communication protocol can be found in [23].
Similarly, communication can be used as an alternative to changing formations using run-time triggers, or as a back-up should an agent not observe a run-time trigger. Although communication can be useful, we create robust behaviors for team agents which ensure that the behaviors never absolutely depend upon having correct, up-to-date knowledge of teammates' internal states: they must degrade gracefully.