A multi-agent system which involves several agents that collaborate towards the achievement of joint objectives is viewed as a team of agents. Most proposed teamwork structures (e.g. joint intentions, shared plans) rely on agents in a multi-agent system to negotiate and/or contract with each other in order to initiate team plans [4, 7, 8]. However, in dynamic, real-time domains with unreliable communication, complex negotiation protocols may take too much time and/or be infeasible due to communication restrictions.
Our work has been focused in time-critical environments in which agents in a team alternate between periods of limited and unlimited communication. This focus leads us to introduce the concept of Periodic Team Synchronization (PTS) domains. In PTS domains, during the limited (or no) communication periods, agents need to act autonomously, while still working towards a common team goal. Time-critical environments require real-time response and therefore eliminate the possibility of heavy communication between team agents. However, in PTS domains, agents can periodically synchronize in a safe, full-communication setting. In this paper, we introduce a flexible teamwork structure that allows for task decomposition and dynamic role assignment in PTS domains.
In PTS domains, teams are long-term entities so that it makes sense for them to have periodic, reliable, private synchronization intervals in which they can form off-line agreements for future use in unreliable, time-critical environments. This view of teams is complementary to teams that form on the fly for a specific action and keep communicating throughout the execution of that action as in [4]. Instead, in PTS domains, teams define coordination protocols during the synchronization opportunity and then disperse into the environment, acting autonomously with little or no communication possible.
It has been claimed that pre-determined team actions are not flexible or robust to failure [27]. A key contribution of our work is the demonstration that pre-determined multi-agent protocols can facilitate effective teamwork while retaining flexibility in PTS domains. We call these pre-determined protocols locker-room agreements. Formed during the periodic synchronization opportunities, locker-room agreements are remembered identically by all agents and allow them to coordinate efficiently. In the context of [3], locker-room agreements can be viewed as C-commitments, or commitments by team members to do the appropriate thing at the right time, as opposed to S-commitments with which agents adopt each other's goals. In the context of [5], the creation of a locker-room agreement is norm acceptance while its use is norm compliance.
In this paper, we introduce an agent architecture suited for team agents in PTS domains. The architecture allows for an agent to act appropriately based on locker-room agreements. Within the framework presented in [15], the architecture is for interactive software and hardware multi-agents.
Since the agents act autonomously and sense the world individually, they may have different views of what is best for the team. However, contrary to self-interested agents for which coordination may or may not be rational [2, 17], our agents have no individual incentives. Their performance is measured as a unit: each agent's highest goal is the success of the team.
A straightforward approach to PTS domains is to break the task at hand into multiple rigid roles, assigning one agent to each role. Thus each component of the task is accomplished and there are no conflicts among agents in terms of how they should accomplish the team goal. However such an approach is subject to several problems: inflexibility to short-term changes (e.g. one robot is non-operational), inflexibility to long-term changes (e.g. a route is blocked), and a lack of facility for reassigning roles.
We introduce instead formations as a team structure. A formation decomposes the task space defining a set of roles with associated behaviors. In a general scenario with heterogeneous agents, subsets of homogeneous agents can flexibly switch roles within formations, and agents can change formations dynamically. This flexibility increases the performance of the overall team. The homogeneous assumption underlying the desired flexible role-switching behavior creates a challenge in terms of determining if and when they should switch roles.
Within these PTS domains and our flexible teamwork structure, several challenges arise. For example, how to represent and follow locker-room agreements; how to determine the appropriate times for agents to change roles and/or formations; how to ensure that all agents are using the same formation; and how to ensure that all roles in a formation are filled. Since the agents are autonomous and do not share memory, they could easily become uncoordinated.
In a nutshell, the main contributions of this paper are: the introduction of the concepts of PTS domains and locker-room agreements; the definition of a general team agent architecture structure for defining a flexible teamwork structure; the facilitation of smooth transitions among roles and entire formations; and a method for using roles to define pre-compiled multi-step, multi-agent plans.
Our work is situated in an example of a PTS domain in which we conducted our research, robotic soccer [10]. In both simulated and robotic systems, teams can plan strategies before the game, at halftime, or at other breakpoints, but during the course of the game, communication is limited. There are several other examples of PTS domains, such as hospital/factory maintenance [6], multi-spacecraft missions [21], search and rescue, and battlefield combat [27].