We achieve collaboration between agents through the introduction of formations. 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. However, it is possible to define
redundant roles such that the behavior specification of 
is
equivalent to that of 
( 
). Each unit 
is a subset
of R: 
such that 
, 
and 
is the
captain, or unit leader. The map 
is not fixed: roles
can be filled by different homogeneous agents. A single role may be a
part of any number of units and formations.
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. Captains are unit-members with special privileges in terms of directing the other unit members.
Roles and formations are introduced independently from the agents that
are to fill them. The locker-room agreement specifies an initial
formation; an initial map from agents to roles; and run-time triggers
for dynamic changing of formations. At any given time, each agent has
an opinion as to 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.
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. Thus, in our implementation of
the teamwork structure, we create robust behaviors for team agents
which do not depend upon having correct, up-to-date knowledge of
teammates' internal states: they degrade gracefully. When limited
communication is available, efficient low-bandwidth communication
protocols can allow agents to inform each other of their roles
periodically. Figure 3 illustrates a team of agents
smoothly switching roles and formations over time.
Figure 3: A team of agents smoothly switching roles and formations over
time. Different roles are represented as differently shaded circles.
Formations are possibly overlapping collections of roles. Units
within the formations are indicated within a dotted enclosure. The
definitions of all roles, formations, and units are known to all
agents. An agent'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 agents first switch roles while staying in the same
formation; then they switch to an entirely new formation.