PTS Domains

 

We define periodic team synchronization domains as domains with the following characteristics:

• There is a team of autonomous agents A that collaborate towards the achievement of a joint long-term goal G.
• Periodically, the team can synchronize with no restrictions on communication: the agents can in effect inform each other of their entire internal states and decision-making mechanisms with no adverse effects upon the achievement of G. These periods of full communication can be thought of as times at which the team is ``off-line.''
• In general (i.e., when the agents are ``on-line''):
  • The domain is dynamic and real-time meaning that team performance is adversely affected if an agent ceases to act for a period of time: G is either less likely to be achieved, or likely to be achieved farther in the future. That is, consider agent . Assume that all other agent behaviors are fixed and that were to act optimally, G would be achieved with probability p at time t. If stops acting for any period of time and then resumes acting optimally, either:
    • G will be achieved with probability at time t with ; or
    • G will be achieved with probability p at time with .
  • The domain has unreliable communication, either in terms of transmission reliability or bandwidth limits. In particular:
    • If an agent sends a message m intended for agent , then m arrives with some probability q < 1; or
    • Agent can only receive x messages every y time units.

In the extreme, if q = 0 or if x = 0, then the periods of full communication are interleaved with periods of no communication, requiring the agents to act completely autonomously. In all cases, there is a cost to relying on communication. If agent cannot carry on with its action until receiving a message from , then the team's performance could suffer. Because of the unreliable communication, the message might not get through on the first try. And because of the dynamic, real-time nature of the domain, the team's likelihood of or efficiency at achieving G is reduced.

Robotic soccer is a PTS domain since teams can plan strategies before the game, at halftime, or at other breakpoints; but during the course of the game, communication is limited. For example, the soccer server's communication protocol involves a single, low-bandwidth, unreliable communication channel for all 22 agents [1].

In PTS domains, teams are long-term entities so that it makes sense for them to have periodic, reliable, private synchronization opportunities 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 [7]. Instead, in PTS domains, teams define coordination protocols during the synchronization opportunity and then disperse into the environment, acting autonomously with limited or no communication possible.

It has been claimed that pre-determined team actions are not flexible or robust to failure [39]. In the context of PTS domains, a key contribution of our work is the demonstration that pre-determined multi-agent protocols can facilitate effective teamwork while retaining flexibility. 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 this article, we present the team member agent architecture, an agent architecture suited for team agents in PTS domains. The architecture allows for an agent to act collaboratively based on locker-room agreements.

A first 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 teamwork structure within the team member agent architecture. 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.

Within these PTS domains and our flexible teamwork structure, several challenges arise. Such challenges include:

• 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.

Also within the team member agent architecture, we introduce a communication paradigm appropriate for agents in PTS domains with single-channel, low-bandwidth, unreliable communication during the dynamic, real-time (on-line) phases of operation. Not all PTS domains have such communication environments, but agents operating in those that do can implement this communication paradigm within their locker-room agreements.

In a nutshell, the contributions of this article are: the introduction of the concepts of PTS domains and locker-room agreements; the definition of a general team member agent architecture structure for defining a flexible teamwork structure; the facilitation of smooth transitions among roles and entire formations; a method for using roles to define pre-compiled multi-step, multi-agent plans; and techniques for dealing with the obstacles to inter-agent communication during the low-communication periods of PTS domains with single-channel, low-bandwidth, unreliable communication during the ``on-line'' periods.

In addition to simulated robotic soccer, there are several other examples of PTS domains, such as hospital/factory maintenance [9], multi-spacecraft missions [30], search and rescue, and battlefield combat [39]. There are also several other domains with similar communication requirements to the ones considered here. For example, aural communication in crowded settings is one. Both people and robots using aural sensors ( [11]) must contend with multiple simultaneous audible streams. They also have a limit to the amount of sound they can process in a given amount of time, as well as to the range within which communication is possible. Another example of such a communication environment is arbitrarily expandable systems. If agents aren't aware of what other agents exist in the environment, then all agents must use a single universally-known communication channel, at least in order to initiate communication.