Journal of Arti cial Intelligence Research 7 (1997) 83-124

Submitted 6/97; published 9/97

Towards Flexible Teamwork
Milind Tambe
Information Sciences Institute and Computer Science Department University of Southern California 4676 Admiralty Way Marina del Rey, CA 90292, USA tambe@isi.edu Many AI researchers are today striving to build agent teams for complex, dynamic multi-agent domains, with intended applications in arenas such as education, training, entertainment, information integration, and collective robotics. Unfortunately, uncertainties in these complex, dynamic domains obstruct coherent teamwork. In particular, team members often encounter di ering, incomplete, and possibly inconsistent views of their environment. Furthermore, team members can unexpectedly fail in ful lling responsibilities or discover unexpected opportunities. Highly exible coordination and communication is key in addressing such uncertainties. Simply tting individual agents with precomputed coordination plans will not do, for their in exibility can cause severe failures in teamwork, and their domain-speci city hinders reusability. Our central hypothesis is that the key to such exibility and reusability is providing agents with general models of teamwork. Agents exploit such models to autonomously reason about coordination and communication, providing requisite exibility. Furthermore, the models enable reuse across domains, both saving implementation e ort and enforcing consistency. This article presents one general, implemented model of teamwork, called STEAM. The basic building block of teamwork in STEAM is joint intentions (Cohen & Levesque, 1991b); teamwork in STEAM is based on agents' building up a (partial) hierarchy of joint intentions (this hierarchy is seen to parallel Grosz & Kraus's partial SharedPlans, 1996). Furthermore, in STEAM, team members monitor the team's and individual members' performance, reorganizing the team as necessary. Finally, decision-theoretic communication selectivity in STEAM ensures reduction in communication overheads of teamwork, with appropriate sensitivity to the environmental conditions. This article describes STEAM's application in three di erent complex domains, and presents detailed empirical results.

Abstract

1. Introduction teamwork: cooperative e

ort by the members of a team to achieve a common goal. { American Heritage Dictionary

Teamwork is becoming increasingly critical in many multi-agent environments, such as, virtual training (Tambe et al., 1995; Rao et al., 1993), interactive education (for instance, in virtual historical settings, Pimentel & Teixeira, 1994), internet-based information integration (Williamson, Sycara, & Decker, 1996), RoboCup robotic and synthetic soccer (Kitano et al., 1995, 1997), interactive entertainment (Hayes-Roth, Brownston, & Gen, 1995; Reilly, 1996), and potential multi-robotic space missions. Teamwork in such complex, dynamic domains is more than a simple union of simultaneous coordinated activity. An illustrative c 1997 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.

Tambe

example provided by Cohen and Levesque (1991b) | worth repeating, given that the di erence between simple coordination and teamwork is often unacknowledged in the literature | focuses on the distinction between ordinary tra c and driving in a convoy. Ordinary tra c is simultaneous and coordinated by tra c signs, but it is not considered teamwork. Driving in a convoy, however, is an example of teamwork. The di erence in the two situations is that while teamwork does involve coordination, in addition, it at least involves a common team goal and cooperation among team members. This article focuses on the development of a general model of teamwork to enable a team to act coherently, overcoming the uncertainties of complex, dynamic environments. In particular, in these environments, team members often encounter di ering, incomplete and possibly inconsistent views of the world and (mental) state of other agents. To act coherently, team members must exibly communicate to avoid miscoordination. Furthermore, such environments can often cause particular team members to unexpectedly fail in ful lling responsibilities, or to discover unexpected opportunities. Teams must thus be capable of monitoring performance, and exibly reorganizing and reallocating resources to meet any contingencies. Unfortunately, implemented multi-agent systems often fail to provide the necessary exibility in coordination and communication for coherent teamwork in such domains (Jennings, 1994, 1995). In particular, in these systems, agents are supplied only with preplanned, domain-speci c coordination. When faced with the full brunt of uncertainties of complex, dynamic domains, the in exibility of such preplanned coordination leads to drastic failures | it is simply di cult to anticipate and preplan for all possible contingencies. Furthermore, in scaling up to increasingly complex teamwork situations, these coordination failures continually recur. In addition, since coordination plans are domain speci c, they cannot be reused in other domains. Instead, coordination has to be redesigned for each new domain. The central hypothesis in this article is that providing agents with a general model of teamwork enables them to address such di culties. Such a model enables agents to autonomously reason about coordination and communication, providing them the requisite exibility in teamwork. Such general models also allow reuse of teamwork capabilities across domains. Not only does such reuse save implementation e ort, but it also ensures consistency in teamwork across applications (Rich & Sidner, 1997). Fortunately, recent theories of teamwork have begun to provide the required models for exible reasoning about teamwork, e.g., joint intentions (Cohen & Levesque, 1991b; Levesque, Cohen, & Nunes, 1990), SharedPlan (Grosz, 1996; Grosz & Kraus, 1996; Grosz & Sidner, 1990) and joint responsibility (Jennings, 1995), are some of the prominent ones among these. However, most research e orts have failed to exploit such teamwork theories in building practical applications (Jennings, 1994, 1995). This article presents an implemented general model of teamwork, called STEAM (simply, a Shell for TEAMwork).1 At its core, STEAM is based on the joint intentions theory (Levesque et al., 1990; Cohen & Levesque, 1991b, 1991a); but it also parallels and in some cases borrows from the SharedPlans theory (Grosz, 1996; Grosz & Kraus, 1996; Grosz & Sidner, 1990). Thus, while STEAM uses joint intentions as the basic building block of teamwork, as in the SharedPlan theory, team members build up a complex hierarchical structure of joint intentions, individual intentions and beliefs about others' intentions. In STEAM,
1. STEAM code (with documentation/traces) is available as an online Appendix.

84

Towards Flexible Teamwork

communication is driven by commitments embodied in the joint intentions theory | team members may communicate to attain mutual belief while building and disbanding joint intentions. Thus, joint intentions provide STEAM a principled framework for reasoning about communication, providing signi cant exibility. STEAM also facilitates monitoring of team performance by exploiting explicit representation of team goals and plans. If individuals responsible for particular subtasks fail in ful lling their responsibilities, or if new tasks are discovered without an appropriate assignment of team members to ful ll them, team reorganization can occur. Such reorganization, as well as recovery from failures in general, is also driven by the team's joint intentions. STEAM's operationalization in complex, real-world domains (described in the next section) has been key in its development to address important teamwork issues discussed above. It has also led STEAM to address some practical issues, not addressed in teamwork theories. One key illustration is in STEAM's detailed attention to communication overheads and risks, which can be signi cant. STEAM integrates decision theoretic communication selectivity | agents deliberate upon communication necessities vis-a-vis incoherency in teamwork. This decision theoretic framework thus enables improved exibility in communication in response to unexpected changes in environmental conditions. Operationalizing general models of teamwork, such as STEAM, necessitates key modications in the underlying agent architectures. Agent architectures such as Soar (Newell, 1990), RAP (Firby, 1987), PRS (Rao et al., 1993), BB1 (Hayes-Roth et al., 1995), and IRMA (Pollack, 1992) have so far focused on individual agent's exible behaviors via mechanisms such as commitments and reactive plans. Such architectural mechanisms need to be enhanced for exible teamwork. In particular, an explicit representation of mutual beliefs, reactive team plans and team goals is essential. Additional types of commitments, suitable for a team context, may need to be embodied in the architectures as well. Without such architectural moorings, agents are unable to exploit general models of teamwork, and reason about communication and coordination. This view concurs with Grosz (1996), who states that \capabilities for teamwork cannot be patched on, but must be designed in from the start". Our operationalization of STEAM is based on enhancements to the Soar architecture (Newell, 1990), plus a set of about 300 domain-independent Soar rules. Three di erent teams have been developed based on this operationalization of STEAM. These teams have a complex structure of team-subteam hierarchies, and operate in complex environments | in fact, two of them operate in a commercially-developed simulation environment for training. This article presents detailed experimental results from these teams, illustrating the bene ts of STEAM in their development. STEAM is among just a very few implemented general models of teamwork. Other models include Jennings' joint responsibility framework in the GRATE* system (Jennings, 1995) (based on Joint Intentions theory), and Rich and Sidner's COLLAGEN (Rich & Sidner, 1997) (based on the SharedPlans theory), that both operate in complex domains. While Section 7 will discuss these in greater detail, STEAM signi cantly di ers from both these frameworks, via its focus on a di erent (and arguably wider) set of teamwork capabilities that arise in domains with teams of more than two-three agents, with more complex team organizational hierarchies, and with practical emphasis on communication costs.
85

Tambe

The rest of the article begins with a concrete motivation for our research via a description of key teamwork problems in real-world domains (Section 2). Section 3 discusses theories of teamwork and sketches their implications for STEAM. Section 4 next describes STEAM, our implemented model of teamwork. Section 5 discusses STEAM's selective communication. Section 6 presents a detailed experimental evaluation. Section 7 discusses related work. Finally, Section 8 presents summary and future work. This investigation focuses on three separate domains. Two of the domains are based on a real-world distributed, interactive simulator commercially developed for military training (Calder et al., 1993). The simulator enables | via networking of several computers | creation of large-scale, 3D synthetic battle elds, where humans, as well as hundreds or even thousands of intelligent and semi-intelligent agents can co-participate (Tambe et al., 1995). The rst domain, Attack (Figure 1), involves pilot agents for a company of (up to eight) synthetic attack helicopters. The company starts at the home-base, where the commander pilot agent rst sends orders and instructions to the company members. The company processes these orders and then begins ying towards their speci ed battle position, i.e., the area from which the company will attack the enemy. While enroute to the battleposition, depending on the orders, the company members may y together or dynamically split into pre-determined subteams. Once the company reaches a holding point, it halts. One or two scout helicopters y forward and rst scout the battle position. Based on communication from the scouts, other company members y forward to the battle position. Here, individual pilots repeatedly mask(hide) their helicopters and unmask to shoot missiles at enemy targets. Once the attack completes, the helicopters regroup and return to their home-base. While enroute to the home-base (or initially towards the battle-position), if any company member spots enemy vehicles posing a threat to the company, it alerts others. The company then evades and bypasses the enemy vehicles, while also protecting itself using guns. When the company returns safely to home-base, it rearms and refuels, readying itself for the next mission. An overview of the overall research and development e ort in this domain, simulation infrastructure, milestones, and agent behaviors is presented in (Hill et al., 1997).
HOLDING POINT HOME BASE RIDGE

2. Illustrative Domains and Motivations

BATTLE POSITION

ENEMY VEHICLES

Figure 1: Attack domain: company ying in subteams In the second domain, Transport (Figure 2), synthetic transport helicopters protected by escort helicopters y synthetic troops to land. In a typical mission, two or four escort helicopters and four to twelve transport helicopters take o from separate ships at sea to rendezvous at a link-up point. The escorts then provide a protective cover to the transport helicopters during the entire ight to and from their pre-speci ed landing zone (where the
86

Towards Flexible Teamwork

synthetic troops dismount). This domain may involve teams of up to sixteen synthetic pilot agents (the largest team we have encountered); although Figure 2 shows twelve.
LANDING ZONE
SEA
ESCOR

T

LAND

ESCOR

T

TRANS

PORTS TRANS PORTS

ESCOR

T

ESCOR

T

Figure 2: Transport domain with synthetic escort and transport helicopters. Our third domain is RoboCup synthetic soccer (Kitano et al., 1995). RoboCup is an international soccer tournament for robots and synthetic agents, aimed at promoting research in multi-agent systems. In the synthetic agent track, over 30 teams will participate in the rst RoboCup'97 tournament at IJCAI'97 in Japan. The snapshot in Figure 3 shows two competing teams: CMUnited (Stone & Veloso, 1996) versus our ISI team.2 The Attack domain is illustrative of the teamwork challenges. In our initial, pre-STEAM implementation, the helicopter pilot agents were developed in the Soar integrated agentarchitecture (Newell, 1990; Rosenbloom et al., 1991). Each pilot agent was based on a separate copy of Soar. For each such pilot, an operator hierarchy was de ned. Figure 4 shows a portion of this hierarchy (Tambe, Schwamb, & Rosenbloom, 1995). Operators are very similar to reactive plans commonly used in other agent architectures, such as the architectures described in Section 1. Each operator consists of (i) precondition rules for selection; (ii) rules for application (a complex operator subgoals); and (iii) rules for termination. At any one point, only one path through this hierarchy is active, i.e., it governs an individual's behavior. For teamwork among individuals, domain-speci c coordination plans were added, as commonly done in other such e orts in this type of domain (Rajput & Karr, 1995; Tidhar, Selvestrel, & Heinze, 1995; Laird, Jones, & Nielsen, 1994; Coradeschi, 1997), including our own (Tambe et al., 1995). For instance, after scouting the battle position, a scout executes a plan to inform those waiting behind that the battle position is scouted (not shown in Figure 4). Initially, with two-three pilot agents and few enemy vehicles, limited behaviors and controlled agent interaction, carefully preplanned coordination was adequate to demonstrate desired behaviors. However, as the numbers of agents and vehicles increased, their behaviors were enriched, and domain experts (human pilots) began to specify complex missions, signi cant numbers of unanticipated agent interactions surfaced. Faced with the full brunt
2. Since March 1997, a team of graduate students at the Information Sciences Institute (ISI) has joined in in further research and maintenance of the ISI team. While the author continues to be responsible for the teamwork in the player agents, others have made signi cant contributions to individual agent behaviors.

87

Tambe

Figure 3: The Robocup synthetic soccer domain.
EXECUTE−MISSION
Fly−flight−plan Engage Prepare−to return−to−base return to control point

Fly cntrl route

Select point

Select route

Mask

Unmask

Employ weapons

Initialize hover

Dip High level Low level Contour NOE

Initialize Maintain hover masked position Select− Mask

Goto new−mask location

Popup

Employ−missile ............

Figure 4: Attack domain: Portion of a pilot agent's operator hierarchy. of the uncertainties in this complex, dynamic environment, the carefully hand-coded, preplanned coordination led to a variety of teamwork failures in the various demonstrations and exercises in 1995-96. Figure 5 lists a small sample of the teamwork failures, roughly in the order they were encountered. One approach to address these failures is a further addition of domain-speci c coordination plans; and indeed, this was the rst approach we attempted. However, there are several di culties. First, there is no overarching framework that would enable anticipation of teamwork failures; the teamwork failures just appear to arise unexpectedly. As a result,
88

Towards Flexible Teamwork

1. Upon abnormally terminating engagement with the enemy, the company commander returned to home base alone, abandoning members of its own company at the battle position. 2. Upon reaching the holding area, the company waited, while a single scout started ying forward. Unfortunately, the scout unexpectedly crashed into a hillside; now, the rest of the company just waited inde nitely for the scout's scouting message. 3. One pilot agent unexpectedly processed its initial orders before others. It then ew towards the battle position, while its teammates were left behind at the home base. 4. Only a scout made it to the holding area (all other helicopters crashed or got shot down); but the scout scouted the battle position anyhow, and waited inde nitely for its non-existent company to move forward. 5. When the initial orders unexpectedly failed to allocate the scouting role to team members, the company members waited inde nitely when they reached the holding point. 6. Instructions sent by the commander pilot agent to some company members were lost, because the commander unexpectedly sent them while the members were busy with other tasks. Hence, these members were unable to select appropriate actions. 7. While evading an enemy vehicle encountered enroute, one helicopter pilot agent unexpectedly destroyed the vehicle via gun re. However, this pilot agent did not inform others; and thus an unnecessary, circuitous bypass route was planned. 8. In an extreme case, when all company members ran out of ammunition, the company failed to infer that their mission could not continue. 9. Two separate companies of helicopters were accidentally allowed to use the same radio channels, leading to interference and loss of an initial message from one of the company commanders | its company hung inde nitely.

Figure 5: Some illustrative examples of breakdown in teamwork. coordination plans have to be added on a case-by-case basis | a di cult process, since failures have to be rst encountered in actual runs. Furthermore, as the system continues to scale up to increasingly complex teamwork scenarios, such failures continually recur. Thus, a large number of special case coordination plans are potentially necessary. Finally, it is di cult to reuse such plans in other domains. Given these di culties, we have pursued an alternative approach | provide agents with a general model of teamwork. The agents can then themselves reason about their coordination/communication responsibilities as well as anticipate and avoid (or recover from) teamwork failures. Such an approach also requires an explicit representation of agents' team goals and team plans; for that is the very basis for reasoning about teamwork. Unfortunately, the agent's operator hierarchy shown in Figure 4 represents its own activities. Thus, although the agent is provided information about its teammates, their participation in particular activities is not explicit (but rather, implicit in the coordination plans). As a result, the agent remains ignorant as to which operators truly involve teamwork and the teammates involved in them. For instance, execute-mission and engage are in reality team activities involving the entire company; while mask and unmask involve no teamwork. Furthermore, in some team tasks only subteams are involved, adding to the di culty of relying on implicit
89

Tambe

representations since the teammates involved in team tasks vary. Even more problematic for implicit representation are team tasks where the team members perform non-identical activities. For instance, consider team tasks such as travelling overwatch (where one subteam travels while the other overwatches), or wait while battle position scouted (where scouts scout the battle position while the non-scouts wait). In such tasks, no single agent performs the team activity, and yet it is important to represent and reason about the combined activity that results. This di culty in representation is not speci c to the Soar architecture, but the entire family of architectures mentioned in Section 1. More importantly, concomitant with the explicit team goals and plans are certain commitments and coordination responsibilities towards the team, based on the general model of teamwork employed. In the absence of both the explicit representation of team goals and plans, as well as commitments and responsibilities they engender, agents are often forced to rely on the problematic domain-speci c coordination plans, leading to aforementioned teamwork failures.

3. Models of Teamwork
Several teamwork theories have been proposed in the literature (Cohen & Levesque, 1991b; Grosz & Kraus, 1996; Jennings, 1995; Kinny et al., 1992). The theories are not intended to be directly implemented (say via a theorem prover), but to be used as a speci cation for agent design. They often prescribe general, rather than domain-speci c, reasoning processes or heuristics for teamwork. Di erent types of operational teamwork models could potentially emerge from these theories | the space of such models remains to be fully explored and understood. In developing STEAM, we have focused on the joint intentions theory (Cohen & Levesque, 1991b; Levesque et al., 1990; Cohen & Levesque, 1991a), given its detailed formal speci cation and prescriptive power. The joint intentions theory is brie y reviewed in Section 3.1. STEAM ultimately builds on joint intentions in a way that parallels the SharedPlan theory (Grosz & Sidner, 1990; Grosz, 1996; Grosz & Kraus, 1996). The SharedPlans theory is very brie y reviewed in Section 3.2. Section 3.3 sketches the implications of the theories for STEAM. It outlines the rationale for the design decisions in STEAM | in the process, it brie y compares the capabilities provided by the joint intentions and SharedPlan theories. STEAM is later presented in detail in Sections 4 and 5. The joint intentions framework (Cohen & Levesque, 1991b, 1991a; Levesque et al., 1990) focuses on a team's joint mental state, called a joint intention. A team jointly intends a team action if team members are jointly committed to completing that team action, while mutually believing that they were doing it. A joint commitment in turn is de ned as a joint persistent goal (JPG). The team 's JPG to achieve p, where p stands for completion of a team action, is denoted JPG( , p, q). q is an irrelevance clause | as described below, it enables a team to drop the JPG should they mutually believe q to be false. JPG( , p, q) holds i three conditions are satis ed:
1. All team members mutually believe that p is currently false. 90

3.1 Joint Intentions Theory

Towards Flexible Teamwork

2. All team members have p as their mutual goal, i.e, they mutually know that they want p to be eventually true. 3. All team members mutually believe that until p is mutually known to be achieved, unachievable or irrelevant they mutually believe that they each hold p as a weak goal (WAG).3 WAG( , p, , q), where is a team member in , implies that one of the following holds: achievement goal); or

believes p is currently false and wants it to be eventually true, i.e., p is a normal

Having privately discovered p to be achieved, unachievable or irrelevant (because q is false), has committed to having this private belief become 's mutual belief.

JPG provides a basic change in plan expressiveness, since it builds on a team task p. Furthermore, a JPG guarantees that team members cannot decommit until p is mutually believed to be achieved, unachievable or irrelevant. Basically, JPG( , p, q) requires team members to each hold p as a weak achievement goal (WAG). WAG( , p, , q), where is a team member in , requires to adopt p as its goal if it believes p to be false. However, should privately believe that p has terminated | i.e., p is either achieved, unachievable or irrelevant | JPG( ,p, q) is dissolved, but is left with a commitment to have this belief become 's mutual belief. To establish mutual belief, must typically communicate with its teammates about the status of the team task p. The commitment to attain mutual belief in the termination of p is a key aspect of a JPG. This commitment ensures that team members stay updated about the status of team activities, and thus do not unnecessarily face risks or waste their time. For instance, consider the rst failure presented in Section 5, where the commander returned to home base alone, abandoning its teammates to face a risky situation. Such failures can be avoided given the commitments in a JPG. In our example, the commander would have communicated with its teammates to establish mutual belief about the termination of the engagement. To enter into a joint commitment (JPG) in the rst place, all team members must establish appropriate mutual beliefs and commitments. An explicit exchange of request and con rm speech acts is one way that a team can achieve appropriate mutual beliefs and commitments (Smith & Cohen, 1996). Since this exchange leads to establishment of a JPG, we will refer to it in the following as the establish commitments protocol. The key to this protocol is a persistent weak achievement goal (PWAG). PWAG( i, p, ) denotes commitment of a team member i to its team task p prior to the team's establishing a JPG.4 initiates the protocol while its teammates in , 1,., i.. n, respond:
1. executes a Request( , , p), cast as an Attempt( , , ). That is, 's ultimate goal is to both achieve p, and have all i adopt PWAG( i, p, ). However, is minimally committed to , where denotes achieving mutual belief in that has the PWAG to achieve . With this Request, adopts the PWAG. 2. Each i responds via con rm or refuse. Con rm, also an Attempt, informs others that i has the PWAG to achieve p.
3. WAG was originally called WG in (Levesque et al., 1990), but later termed WAG in (Smith & Cohen, 1996). 4. The PWAG also includes an irrelevance clause q, but we will not include it here to simplify the following description.

91

Tambe

3. If 8 i, i con rm, JPG( , p) is formed.

In establishing a JPG, this protocol synchronizes . In particular, with this protocol, members simultaneously enter into a joint commitment towards a current team activity p. While the JPG is the end product of the establish commitment protocol, important behavioral constraints are enforced during execution via the PWAGs. In step 1, the adoption of a PWAG implies that if after requesting, privately believes that p is achieved, unachievable or irrelevant, it must inform its teammates. Furthermore, if believes that the minimal commitment is not achieved, it must retry (e.g., if a message did not get through it must retransmit the message). Step 2 similarly constrains team members i to inform others about p, and to rebroadcast. As step 3 indicates, all team members must consent, via con rmation, to the establishment of a JPG. A JPG is not established if any one agent refuses. Negotiations among team members may ensue in such a case; however, that remains an open issue for future work. In contrast with joint intentions, the concept of SharedPlans (SP) is not based on a joint mental attitude (Grosz, 1996; Grosz & Kraus, 1996; Grosz & Sidner, 1990). Instead, SP relies on a novel intentional attitude, intending that, which is similar to an agent's normal intention to do an action. However, an individual agent's intention that is directed towards its collaborator's actions or towards a group's joint action. Intention that is de ned via a set of axioms that guide an individual to take actions, including communicative actions, that enable or facilitate its teammates, subteam or team to perform assigned tasks (Grosz & Kraus, 1996). An SP is either a full SharedPlan (FSP) or a partial SharedPlan(PSP). We will begin with a de nition of an FSP, and then follow with brief remarks about a PSP. An FSP to do represents a situation where every aspect of a joint activity is fully determined. This includes mutual belief and agreement in the complete recipe R to do . R is a speci cation of a set of actions i , which when executed under speci ed constraints, constitutes performance of . FSP(P, GR, , Tp , T , R ) denotes a group GR's plan P at time Tp to do action at time T using recipe R . Very brie y, FSP(P, GR, , Tp, T , R ) holds i the following conditions are satis ed:5
1. All members of group GR mutually believe that they each intend that the proposition Do(GR, , T ) holds i.e., that GR does over time T . 2. All members of GR mutually believe that R is the recipe for . 3. For each step i in R : A subgroup GRk (GRk GR) has an FSP for i , using recipe R i . (GRk may only be an individual, in which case, it must have a full individual plan, an analogue of FSP for individuals.) Other members of GR believe that there exists a recipe such that GRk can bring about i and have an FSP for i (but other members may not know R i).
5. For the sake of brevity, a context clause C is deleted from this de nition. Also, in this article, we will not address the contracting case discussed in (Grosz & Kraus, 1996).

3.2 Shared Plans Theory

92

Towards Flexible Teamwork

Other members of GR intend that GRk can bring about i using some recipe.

The SharedPlan theory aspires to describe the entire web of a team's intentions and beliefs when engaged in teamwork. In this endeavor, an FSP represents a limiting case; usually, when engaged in a team activity, a team only has a partial SharedPlan (PSP). The PSP is a snapshot of the team's mental state in a particular situation in their teamwork, and further communication and planning is often used to ful ll the conditions of an FSP (although, in dynamic domains, the team may never actually form an FSP). We focus on three relevant arenas in which partiality may exist in a PSP. First, the recipe R may be only partially speci ed. Certainly, in dynamic environments, such as the ones of interest in our work, recipes could be considered to evolve over time, as teams reactively decide the next step based both on the context and the current situation. For instance, in the Attack domain, the helicopter company may react to enemy vehicles seen enroute, thus evolving their recipe. According to SP theory, team member must arrive at mutual belief in their next step(s) i . For each step i in the recipe, the relevant subgroup must form a SharedPlan. Second, the team's task allocation may be unreconciled, e.g., the agent or group to perform particular task may not be determined. In this situation, team members intend that there exist some individual or subgroup to do the task. Among actions considered as a result of the intending that, individuals may volunteer to perform the unreconciled task, or persuade/order others to take over the task. Third, individuals or subgroups may not have attained appropriate mutual beliefs for forming an FSP, leading to communication within the team. Communication may also arise due to agents' \intention that" attitude both towards their team goal and towards teammates' activities. For instance, a team member's intention that its team do an action i , and its belief that communication of some particular information will enable the team to do i , will lead it to communicate that information to the team (as long as such communication does not con ict with previous commitments). In STEAM, joint intentions are used as building blocks of teamwork. Several advantages accrue due to this use. First, the commitments in a joint intention begin to provide a principled framework for reasoning about coordination and communication in teamwork. Thus, this framework begins to address teamwork failures such as those in Figure 5. Second, the joint commitments in joint intentions provide guidance for monitoring and maintenance of a team activity, i.e., agents should monitor conditions that cause the team activity to be achieved or unachievable or irrelevant, and maintain the team activity at least until one of these conditions arises. Third, a joint intention leads to an explicit representation of a team activity, and thus facilitates reasoning about teamwork. In particular, as shown later, agents can reason about the relationship between their team activity and an individual's or subteam's contributions to it. However, a single joint intention for a high-level team goal is insu cient to provide all of these advantages. To guarantee coherent teamwork, four additional issues must be addressed. Here, the SharedPlans theory helps in analysis of STEAM's approach, and in one case, STEAM directly borrows from SharedPlans. A key observation is that analogous
93

3.3 The In uence of Teamwork Theories on STEAM

Tambe

to partial SharedPlans, STEAM builds up snapshots of the team's mental state, but via joint intentions. The rst issue involves coherence in teamwork | team members must pursue a common solution path in service of their joint intention for the high-level team goal . Indeed, as Jennings (1995) observes, without such a constraint, team members could pursue alternative solution paths that cancel each other, so no progress is made towards . The SharedPlan theory addresses such coherence by stepping beyond the team members' \intentions that" towards . In addition, SharedPlans mandates mutual belief in a common recipe (even if partial) and SharedPlans for individual steps i in the common recipe, thus generating a recursive hierarchy to ensure coherence. STEAM's approach here parallels that of SharedPlans; however, it builds on joint intentions rather than SharedPlans. That is, STEAM uses joint intentions as a building block to hierarchically build up the mental attitude of individual team members, and ensure that team members pursue a common solution path. In particular, as mentioned earlier, in dynamic domains, given reactive plans, a recipe R may evolve step by step during execution. In STEAM, as the recipe evolves, if a step i requires execution by the entire team, STEAM requires that the entire team agree on i , and form joint intentions to execute it. To execute a substep of i , other joint intentions are formed, leading to a hierarchy. During the expansion of this hierarchy, if a step involves only a subteam then that subteam must form a joint intention to perform that step. If only an individual is involved in the step, it must form an intention to do that step. In general, the resulting intention hierarchy evolves dynamically, depending on the situations the team encounters. Second, Grosz and Kraus (1996) discuss the tradeo s in the amount of information team members must maintain about teammates' activities, particularly when a step i involves only a subteam, or an individual. Grosz and Kraus address this tradeo in SharedPlans as shown in step 3b in Section 3.2, requiring that team members know only that a recipe exists to enable a teammate(s) to perform its actions, but not the details of the recipe. Similarly, STEAM requires that in case a step i is performed by a subteam (or just an individual team member), remaining team members track the subteam's joint intention (or the relevant team member's intention) to perform the step. This intention tracking need not involve detailed plan recognition, e.g., as in our previous work (Tambe, 1995, 1996). Instead, a team member must only be able to infer that its teammates intend (or cannot or do not intend) to execute the step i . This minimal constraint is necessary because otherwise, team members may be unable to monitor the current status of the team activity, e.g., that their team activity has fallen apart. In addition, some information about the dependency relationship among team members' actions is useful in monitoring, as discussed in Section 4.2. A third issue is the analogue of the \unreconciled" case in SharedPlans. STEAM forms a joint intention to replan whenever a team's joint intention for a step i is seen to be unachievable. Replanning may lead the team to rst analyze the cause of the initial unachievability. Among other possibilities, the cause could be the absence of assignment of a subtask to a subteam or individual, or the failure of the relevant individual or subteam in performing the subtask. In such a case, each team member acts to determine the appropriate agent or subteam for performing the relevant task. As a result, an agent can volunteer itself, or suggest to other individuals or subteams to perform the unassigned task.
94

Towards Flexible Teamwork

Of course, the unachievability may be the result of other causes besides lack of assignment; replanning must then address this other cause (further discussion in Section 4.2). A nal issue is generalization of STEAM's communication capabilities via a hybrid approach that combines the prescriptions of the joint intentions approach with some aspects of SharedPlans. A key observation based on (Grosz & Kraus, 1996) is that the communication in joint intentions could potentially be arrived at in SharedPlans via axioms de ning intention that. For instance, consider that a team member has obtained private information about the achievement of the team's current team action 1 . In joint intentions, this team member will seek to attain mutual belief in the achievement of 1 , leading to communication. In contrast, in SharedPlans, the team member's communication would arise because: (i) it intends that the team do some action 2 which follows 1 , and (ii) the team cannot do 2 without all team members being aware of achievement of 1 . Thus, further rst principles reasoning, based on interrelationships among actions, is required to derive relevant communication in SharedPlans; but in this instance, joint intentions provide for such communication without the reasoning. In general, if the team's termination of one action 1 is essential for the team to perform some following action 2 , the prescription in joint intentions | to attain mutual belief in termination of team actions | is adequate for relevant communication. However, in some cases, additional communication based on speci c information-dependency relationships among actions is also essential. For instance, the scouts in the Attack domain not only inform all company members of completion of their scouting activity (so the company can move forward), but also the precise coordinates of enemy location to enable the company to occupy good attacking positions (information-dependency). Such communication could also be potentially derived from the axioms of intention that in SharedPlans, but at the cost of further reasoning. STEAM does not rely on the rst-principles reasoning from intention that for its communication, relying on the prescriptions of joint intentions instead. However, STEAM exploits explicit declaration of information-dependency relationships among actions, for additional communication. Thus, when communicating the termination of a team action i , STEAM checks for any inferred or declared information-dependency relationships with any following action j . The information relevant for j is also communicated when attaining mutual belief in the termination of i . As a result, based on the speci c information-dependency relationship speci ed, di erent types of information are communicated, when terminating i . Thus, the scouts can communicate the location of enemy units when communicating the completion of their scouting { given the information-dependency relationship with the planning of attacking positions. If no such relationship is speci ed, or if other relationships are speci ed, the scouts would communicate di erent information. STEAM thus starts with joint intentions, but then builds up hierarchical structures that parallel the SharedPlans theory, particularly, partial SharedPlans. The result could be considered a hybrid model of teamwork, that borrows from the strengths of both joint intentions (formalization of commitments in building and maintaining joint intentions) and SharedPlans (detailed treatment of team's attitudes in complex tasks, as well as unreconciled tasks). This is of course not the only possible hybrid. As mentioned earlier, further exploration in the space of teamwork models is clearly essential.
95

Tambe

4. STEAM
STEAM's basis is in executing hierarchical reactive plans, in common with architectures mentioned in Section 1. The novel aspects of STEAM relate to its teamwork capabilities. The key novelty in STEAM is team operators (reactive team plans). When agents developed in STEAM select a team operator for execution, they instantiate a team's joint intentions. Team operators explicitly express a team's joint activities, unlike the regular \individual operators" which express an agent's own activities. In the hierarchy in Figure 6, operators shown in ] such as Engage] are team operators, while others are individual operators. Team activities such as travelling overwatch or waiting while battle position scouted are now easily expressed as team operators, as shown in Figure 6, with activities of individuals or subteams expressed as children of these operators. (Team operators marked with \*" are typically executed by subteams in this domain.)
[ EXECUTE−MISSION ] [ Fly−flight−plan ]
............ ............

[ Engage ]

[ Wait−while− battle−position−scouted ] [ Mask & ]* [ Scout ] Observe forward *
............ ............

[Fly−control ] route
[ Travelling ]
High level Low Contour NOE level

[ Travelling ] Overwatch [Travelling ] [Travelling ] Lead Cover
*
............

Employ weapons

wait−for scouting
............

Unmask

Mask

* popup Employ− missile
............

High level

Low Contour NOE level

Initialize Maintain Select− Goto−new mask−location Dip hover position Mask

Figure 6: Attack domain: Portion of modi ed operator hierarchy with team operators. As with individual operators, team operators also consist of: (i) precondition rules; (ii) application rules; and (iii) termination rules. Whether an operator is a team operator or an individual operator is dynamically determined. In particular, when an agent i invokes an operator for execution, the operator is annotated with an \executing agent", which may be dynamically determined to be an individual, or subteam, or a team. If the \executing agent" is a particular team or subteam, the operator is determined to be a team operator. If the \executing agent" is the agent i itself, then an individual operator results. Thus, precise team executing a team operator is not compiled in, but can be exibly determined at execution time. Figure 6 thus illustrates the con guration of operators that is typical in the Attack domain. Given an arbitrary team operator OP, all team members must simultaneously select OP to establish a joint intention (joint intention for OP will be denoted as OP] ). In Figure 6, at the highest level, the team forms a joint intention for execute-mission] . In service of this joint intention, the team may form a joint intention engage] . In service of engage] , individual team members all select individual operators to employ-weapons, thus forming individual intentions. An entire hierarchy of joint and individual intentions is thus formed when an agent participates in teamwork.
96

Towards Flexible Teamwork

A STEAM-based agent maintains its own private state for the application of its individual operators; and a \team state" to apply team operators. A team state is the agent's (abstract) model of the team's mutual beliefs about the world, e.g., in the Transport domain, the team state includes the coordinates of the landing zone. The team state is usually initialized with information about the team, such as the team members in the team, possible subteams, available communication channels for the team, the pre-determined team leader and so forth. STEAM can also maintain subteam states for subteam participation. There is of course no shared memory, and thus each team member maintains its own copy of the team state, and any subteam states for subteams it participates in. To preserve the consistency of a (sub)team state, one key restriction is imposed for modi cations to it | only the team operators representing that (sub)team's joint intentions can modify it. Thus, the state corresponding to a subteam can only be modi ed in the context of a joint intention OP] . Thus, at minimum, STEAM requires the following modi cations to the architectures such as Soar, RAP, PRS and others mentioned in Section 1 to support teamwork: (i) generalization of operators (reactive plans) to represent team operators (reactive team plans); (ii) representation of team and/or subteam states, and (iii) restrictions on team state modi cations (only via appropriate team operators). While these team operators and team states are at the foundation of STEAM, as a general model of teamwork, STEAM also involves agents' commitments in teamwork, monitoring and replanning capabilities, and more. Hard-wiring this entire teamwork model within the agent architectures could potentially lead to unnecessary rigidity in agent behaviors. Instead, the STEAM model is maintained as a domain-independent, operational module (e.g., in the form of rules) to guide agents' behaviors in teamwork. In the future, appropriate generalizations of these capabilities could begin to be integrated in agent architectures. The following subsections now discuss key aspects of STEAM in detail. Section 4.1 discusses team operator execution in STEAM. Section 4.2 describes STEAM's capabilities for monitoring and replanning. Detailed pseudo-code for executing STEAM appears in Appendix A.

4.1 Team Operator Execution

To execute a team operator, agents must rst establish it as a joint intention. Thus, when a member selects a team operator for execution, it rst executes the establish commitments protocol described below (introduced in Section 3.1):
1. Team leader broadcasts a message to the team to establish PWAG to operator OP. Leader now establishes PWAG. If OP] not established within time limit, repeat broadcast. 2. Subordinates i in the team wait until they receive leader's message. Then, turn by turn, broadcast to establishment of PWAG for OP; and establish PWAG. 3. Wait until 8 i, i establish PWAG for OP; establish OP] .

With this establish commitment protocol, agents avoid problems of the type where just one member ies o to the battle position (item 3, Figure 5). In particular, a team member cannot begin executing the mission without rst establishing a joint intention executemission] . During execution of the establish commitment protocol, PWAGs address several
97

Tambe

contingencies | if an OP is believed achieved, unachievable or irrelevant prior to OP] , agents inform teammates. Other contingencies are also addressed, e.g., even if a subordinate initially disagrees with the leader, it will conform to the leader's broadcasted choice of operators. In general, resolving disagreements among team members via negotiation is a signi cant research problem in its own right (Chu-Carroll & Carberry, 1996), which is not addressed in STEAM. Instead, currently STEAM relies on a team leader to initiate the request, and thus resolve disagreements. After establishing a joint intention OP] , a team operator can only be terminated by updating the team state (mutual beliefs). This restriction on team operator termination avoids critical communication failures of the type where the commander returned to homebase alone | instead, agents must now inform teammates when terminating team operators. Furthermore, with each team operator, multiple termination conditions may be speci ed, i.e., conditions that make the operator achieved, unachievable or irrelevant. Now, if an agent's private state contains a belief that matches with a team operator's termination condition, and such a belief is absent in its team state, then it creates a communicative goal, i.e., a communication operator. This operator broadcasts the belief to the team, updating the team state, and then terminating the team operator. As mentioned earlier, during teamwork, an agent may be a participant in several joint intentions, some involving the entire team, some only a subteam. Thus, an agent may be participating in a joint intention involving the entire company, such as execute-mission] , as well as one involving just a subteam, such as mask-and-observe] . When the termination condition of a speci c team operator is satis ed, a STEAM-based agent will aim to attain mutual belief in only the relevant subteam or team, e.g., facts relevant to mask-andobserve] may only be communicated among . During the broadcast of the communication message, STEAM checks for informationdependency relationships with any following tasks; if one exists, relevant information is extracted from the current world state and broadcast as well. The information-dependency relationship may be speci ed individually per speci c termination condition. For instance, suppose a company member 4 sees some enemy tanks on the route while ying to home base. It recognizes that this fact causes the team's current joint intention y- ight-plan] to be unachievable. If this fact is absent in the team state, then a communication operator is executed, resulting in a message broadcast indicating termination of the y- ight-plan team operator. In addition, STEAM uses the explicitly speci ed information-dependency relationship with a following operator evade to extract the x,y location and direction of the tank. As a result, the following communication is generated:
4 terminate-JPG y- ight-plan evade tank elaborations 61000 41000 right.

This message identi es the speaker ( 4), and informs team members to terminate yight-plan] in order to evade a tank. Thus, 4 informs others; it does not evade tanks on its own. The part of 4's message that follows the key word elaborations is due to the information-dependency relationship. This information | the x,y location and direction of the tank | enables team members to evade appropriately. Separating out the information98

Towards Flexible Teamwork

dependency component in this fashion provides additional communication exibility, as explained earlier in Section 3.3.6 One major source of teamwork failures, as outlined in Section 2, is agents' inability to monitor team performance. STEAM facilitates such monitoring by exploiting its explicit representation of team operators. In particular, STEAM allows an explicit speci cation of monitoring conditions to determine achievement, unachievability or irrelevancy of team operators. In addition, STEAM facilitates explicit speci cation of the relationship between a team operator and individuals' or subteam's contributions to it. STEAM uses these speci cations to infer the achievement or unachievability of a team operator. These speci cations are based on the notion of a role. A role is an abstract speci cation of the set of activities an individual or a subteam undertakes in service of the team's overall activity. Thus, a role constrains a team member i (or a subteam ) to some suboperator(s) op i of the team operator OP] . For instance, suppose a subteam is assigned the role of a scout in the Attack domain. This role constrains the subteam to execute the suboperator(s) to scout the battle position in service of the overall team operator wait-while-battle-position-scouted (see Figure 6). Based on the notion of roles, three primitive role-relationships (i) AND-combination (ii) OR-combination and (iii) Role-dependency can currently be speci ed in STEAM. These primitive role-relationships | called role-monitoring constraints | imply the following relationships between a team operator OP] and its suboperators:
1. AND-combination: OP] () n=1 op i W i 2. OR-combination: OP] () n=1 op i i 3. Role dependency: op i =) op j (op i dependent on op j )

4.2 Monitoring and Replanning

V

These primitive role-monitoring constraints may be combined, to specify more complex relationships. For instance, for three agents i, j and k, with roles op i , op j and W V op k , a combination AND-OR role relationship can be speci ed as ((op i op j ) op k ). STEAM-based agents can now infer that the role non-performance of k (:op k ) makes OP unachievable; but the role non-performance of just one of i or j is not critical to OP . Similarly, for two agents i and j, both an OR-combination plus role-dependency W V may be speci ed as ((op i op j ) (op i =) op j )). Role monitoring constraints may be speci ed in terms of individuals' roles, or subteam's roles. The mechanisms for tracking teammates' role performance or inferring their role nonperformance is partly domain dependent. As mentioned in Section 3.3, in some domains, an agent need not know its teammate's detailed plan or track that in detail, but may rely on high-level observations. For instance, in the Attack domain, if a helicopter is destroyed, team members infer role non-performance for the a ected team member. In other cases, such as the RoboCup Soccer domain, no such high-level indication is available. Instead,
6. In the future, to enable STEAM-based agents to communicate with non-STEAM-based agents, a generic communication language may be necessary. While generating natural language is currently outside the scope of STEAM, STEAM does not preclude such a possibility. Alternatively, an arti cial communication language, such as (Sidner, 1994) may be used.

99

Tambe

agents need to obtain role performance information via agent tracking (plan recognition) (Tambe, 1995, 1996), e.g., is a player agent in the RoboCup simulation dashing ahead to receive a pass? Communication may be another source of information regarding role nonperformance. First, as discussed below, STEAM leads individuals to announce role-changes to the team, and thus other team members indirectly infer role-performance information. Second, as discussed in Section 5.1, STEAM may lead individuals to directly communicate their role non-performance. Additionally, a few domain-independent mechanisms for inferring role performance are provided in STEAM. Thus, role non-performance is inferred if no individual or subteam is speci ed for performance of a role (as in item 5, Figure 5). Also, if all individuals within a subteam are found incapable of performing their roles, STEAM infers the entire subteam cannot perform its role. If, based on the role-monitoring constraints and the role performance information about teammates, STEAM infers team operator OP] to be unachievable, it invokes repair] for replanning. By casting repair as a team operator, agents automatically ensure the entire team's commitment for their replanning (the entire team is a ected if OP] is unachievable). Furthermore, agents inform teammates not only about possible repair results, but also repair unachievability or irrelevancy. The actions taken in service of repair] depend on the context. If repair] was invoked due to OP] 's domain-speci c unachievability conditions, domain-speci c repair is triggered. In contrast, if repair] was invoked due to role-monitoring constraint failures, STEAM leads each agent to rst analyze the failure. The analysis may reveal a critical role failure | a single role failure causing the unachievability of OP] | which may occur in an AND-combination if any agent or subteam fails in its role; or an OR-combination when all team members are role-dependent on a single individual or a single subteam. For instance, when agents are ying in formation via travelling] (OR-combination), everyone is role-dependent on the lead helicopter. Thus, should the lead crash, a critical role failure occurs. The action taken in cases of a critical role failure is team recon guration, to determine a team member, or subteam, to substitute for the critical role. As mentioned earlier, this situation corresponds to the \unreconciled case" in SharedPlans, discussed in Section 3.2. The steps taken in STEAM in this case are as follows:
1. Determine candidates for substitution: Each team member rst matches it own capabilities or those of other agents or subteams with the requirements of the critical role. Matching currently relies on domain-speci c knowledge. Of course, agents or subteams that are the cause of the critical role failure cannot be candidates for substitution. 2. Check for critical con icting commitments: Once an agent determines possible candidate(s), including itself, it checks for con icts with candidate's existing commitments to the team. If these commitments are already critical, the candidate is eliminated from consideration. For instance, if the candidate is a participant in a team operator which is an AND-combination, its responsibilities to the team are already critical | even if it possesses relevant capabilities, it cannot take over the role in question. Similarly, the candidate is ruled out if all other team members are role-dependent on it. 3. Announce role-substitution to the team: Candidate(s) not ruled out in step 2 can substitute for the role. This could mean an individual volunteering itself, or a team leader volunteering its subteam for the critical role. Since repair] is a team operator, and since role-substitution implies its achievement, any role-substitution is announced to . 100

Towards Flexible Teamwork

4. Delete non-critical con icting commitments: After assuming the new role in the team activity, the relevant individual or subteam members delete their old roles and old commitments.

In the Attack domain, team members can follow the above procedure when recovering from critical role failures such as item 5 in Figure 5. There, since a scouting subteam is not speci ed, and the relevant operator wait-while-battle-position-scouted involves an ANDcombination of the scouting role with the non-scouts, a critical role failure occurs. A subteam in the rest of the company is located to possess the capabilities of scouting. The leader of this subteam determines that it can volunteer its subteam for scouting, and announces this change in role to the rest of the team. Members of this subteam then delete con icting commitments. wait-while-battle-position-scouted] is now executed with this new role assignment. (Since such new role assignments are con ned to the local context of individual team operators, and since step 2 explicitly checks for critical con icts, they do not lead to any global side-e ects.) The entire repair procedure above can invoked in the context of a subteam , rather than the team . In this case, repair] will be invoked as a team operator. STEAM follows an identical repair procedure, in this case enabling individuals or sub-subteams to take over particular critical roles. Furthermore, any repair communication here is automatically restricted within . In case the failure is a pure role dependency failure, only a single dependent agent i is disabled from role performance (because op i =) op j ). Here, i must locate another agent k such that op i =) op k . Role dependency failure could involve a subteam i instead of an individual; and the subteams engage in an identical repair. If failure type is all roles failure, no agent performs its role; this state is irreparable. In this situation, or in case no substitution is available for a critical role, repair] is itself unachievable. Since the repair of OP] is itself unachievable, a complete failure is assumed, and complete-failure] is now invoked. For instance, in the Attack domain, complete failure implies returning to home base. By casting complete-failure as a team operator, STEAM ensures that team members will not execute such drastic actions without consulting teammates. If only a subteam or an individual i encounters complete-failure, they infer inability to perform their roles in the team 's on-going activity.

5. STEAM: Selective Communication
STEAM agents communicate to establish and terminate team operators. Given the large number of team operators in a dynamic environment, this communication is a very signi cant overhead (as Section 6 shows empirically), or risk (e.g., in hostile environments). Therefore, STEAM integrates decision-theoretic communication selectivity. Here, STEAM takes into consideration communication costs and bene ts, as well as the likelihood that some relevant information may be already mutually believed. While this pragmatic approach is a response to the constraints of real-world domains, it is not necessarily a violation of the prescriptions of the joint intentions framework. In particular, the joint intentions framework does not mandate communication, but rather a commitment to attain mutual belief. Via its decision-theoretic communication selectivity, STEAM attempts to follow the most cost-e ective method of attaining mutual belief relevant in joint intentions.
101

Tambe

Figure 7 presents the decision tree for the decision to communicate a fact F, indicating the termination of OP] . Rewards and costs are measured to the team, not an individual. The two possible actions are NC (not communicate, cost 0) or C (communicate, cost Cc). If the action is NC, two outcomes are possible. With probability (1- ), F was commonly known anyway, and the team is rewarded B for terminating OP] . With probability , however, F was not known, and thus there is miscoordination in terminating OP] (e.g., some agents come to know of F only later). Given a penalty Cmt for miscoordination, the reward reduces to B-Cmt . If the action is C, assuming reliable communication, F is known.
Rewards

NC
Cost: 0 Decision node Chance node

(1−

)

(F known)

B B

(F unknown) B − Cmt 1 0 (F known)

C
Cost: Cc

(F unknown) B − Cmt

Figure 7: Decision tree for communication. EU(C), the expected utility of option C, is B-Cc . EU(NC) of option NC is B- *Cmt . To maximize expected utility, an agent communicates i EU(C) > EU(NC), i.e., i :
Cmt > Cc

Thus, for instance, in the Attack domain, when ying with high visibility, pilot agents do not inform others of achievement of waypoints on their route, since is low (high likelihood of common knowledge), and Cmt is low (low penalty). However, they inform others about enemy tanks on the route, since although is low, Cmt is high. The communication cost Cc could vary depending on the situation as well, and team members may exibly reduce (increase) communication if the cost increases (decreases) during their team activity. Interestingly, if only a single agent is left in a team, drops to zero, and thus, no communication is necessary. Expected utility maximization is also used for selectivity in the establish commitments protocol. If is the probability of lack of joint commitments, and Cme the penalty for executing OP] without joint commitments from the team, then an agent communicates i EU(C) > EU(NC), i.e., i :
Cme > Cc

Further generalization in communication is required to handle uncertainty in the termination criteria for joint intentions. For instance, a team member 4 may be uncertain that an enemy tank seen enroute causes y- ight-plan] to be unachievable | the tank's threat may not be clearcut. Yet not communicating could be highly risky. The decision tree for communication is therefore extended to include , the uncertainty of an event's threat to the joint intention (Figure 8). Since agents may now erroneously inform teammates to terminate team operators, a nuisance cost -Cn is introduced.
102

5.1 Further Communication Generalization

Towards Flexible Teamwork

(Terminates) (1− ) (1 −

Rewards B B−Cmt

) (Not Terminate) 0 (Terminates) (Not Terminate) 0 (Terminates)

NC
Cost: 0 (1 − )

C
Cost: Cc

B −Cn

1 0

(1 − [Irrelevant]

)

(Not Terminate)

Figure 8: Extended decision tree with . Again, an agent communicates i EU(C) > EU(NC), i.e., i * *Cmt > (Cc + (1- )Cn). If is 1, i.e., a team operator has terminated, this equation reduces to | *Cmt > Cc | seen previously. If Cc propose-operator Communicate(terminate-jpg( ), f, ) with high priority; /* See Section 5 and 4.1*/ iii. if no other higher priority operator, in parallel Execute-individual-operator(Communicate(terminate-jpg( ), f, ), self, /C, f 1, 2,...g); iv. Update-state (team-state( ), f); v. Update-status( ] );
2

(b) if agent-status-change( ), where f g

i. Evaluate role-monitoring constraints; /* See Section 4.2. */ ii. if role-monitoring constraint failure cf such that (satis es (Unachievability-conditions( ), cf) then update-status( ] );

(c) if receive communication of terminate-jpg( ) and fact f f g

if (W satis es (Achievement-conditions( ), f) satis es (Unachievability-conditions( ), f) satis es (Irrelevance-conditions( ), f)) i. Update-state (team-state( ), f); ii. Update-status( ] );

f

W

(d) Update-state(team-state( ), actions( )); /* execute domain-speci c actions to modify team state of */ 117

g g

Tambe

(e) if children operator 1, 2,... n of proposed as candidates f i. i select-bestf 1... ng; V ii. if (teamtype(Agent( i)) ( = Agent( i))) then in parallel Execute-team-operator( i, V, /C, f 1, 2...g); iii. if (teamtype(Agent( i)) (Agent( i)) ) then in parallel f iv. if self(Agent( i)) then in parallel f g

A. Execute-team-operator( i, Agent( i), /C, f 1, 2...g); B. Instantiate role-monitoring constraints; A. Execute-individual-operator( i, self, /C, 1...); B. Instantiate role-monitoring constraints;

g g

/* End while statement in 4 */ 5. terminate joint intention ] ; 6. if status( ] , Unachievable) g f f

if ( != Repair) /* If is not itself Repair */

/* Repair is explained in detail in Section 4.2. Cause-of-unachievability, passed as a parameter to Repair, may be role-monitoring constraint violation as in case 4b, or the domain-speci c unachievability conditions. */ g else f Execute-team-operator(Complete-Failure, , C, f , cause-of-unachievability,...g) /* If Repair is itself unachievable, complete-failure results, as in Section 4.2 */ g g g

Execute-team-operator(Repair, , C, f , cause-of-unachievability,...g)

/* end procedure execute-team-operator */

Individual Operator Execution f Execute-individual-Operator( , self, C, f 1, 2,..., ng)

1. establish as an individual intention; W W 2. While NOT(status( , Achieved) status( , Unachievable) status( , Irrelevant)) Do f (a) if (W satis es (Achievement-conditions( ), f) satis es (Unachievability-conditions( ), f) satis es (Irrelevance-conditions( ), f)) f W

i. Update-state (state(self), f); 118

Towards Flexible Teamwork

ii. Update-status( ); (b) Update-state(state(self), actions( )); /* execute domain-speci c actions to modify private state */ (c) if new children operator f 1... ng of proposed f g

i. i select-bestf 1... ng; ii. Execute-individual-operator( i, self, /C, f 1...g)

g

/* end while statement in 2 */ 3. if status( , Unachievable) g f

if ( != Repair)
Execute-individual-operator(Repair, self, C, f , cause-of-unachievability,...g) /* Repair is explained in detail in Section 4.2. Cause-of-unachievability is only domain-speci c unachievability condition. This is passed as a parameter to repair. */ g else f Execute-individual-operator(Complete-Failure, self, C, f , cause-of-unachievability,...g) /* If Repair is itself unachievable, complete-failure results, as in Section 4.2 */ g g g f

/* end procedure execute-individual-operator */

The sample rules described below follow the description of STEAM provided in this article, and essentially help encode the algorithm described in Appendix A. The rules, as with the algorithm in Appendix A, are based on execution of hierarchical operators, or reactive plans. While the sample rules below are described in simpli ed if-then form, the actual rules are encoded in Soar, and are available as an online Appendix.
/* This rule focuses on generating a communicative goal if an agent's private state contains a belief that satis es the achievement condition of a team operator OP] . See section 4.1. */ IF agent i's private state contains a fact F AND fact F matches an achievement condition AC of a team operator OP] AND fact F is not currently mutually believed AND a communicative goal for F is not already generated THEN 119

Appendix B: STEAM Sample Rules

SAMPLE:RULE:CREATE-COMMUNICATIVE-GOAL-ON-ACHIEVED

Tambe

create possible communicative goal CG to communicate fact F to team to terminate OP] . /* This rule is similar to the one above. */ IF agent i's private state contains a fact F AND fact F matches an unachievability condition UC of a team operator OP] AND fact F is not currently mutually believed AND a communicative goal for F is not already generated THEN create possible communicative goal CG to communicate fact F to team to terminate OP] . /* This rule estimates *Cmt for non-communication given a communicative goal, using the formula from Section 5.*/ IF CG is a possible communicative goal to communicate fact F to team to terminate OP] AND Cmt is estimated high AND is estimated low THEN Estimated value of non-communication is medium.

SAMPLE:RULE:CREATE-COMMUNICATIVE-GOAL-ON-UNACHIEVABLE

SAMPLE:RULE:ESTIMATE-VALUE-FOR-NON-COMMUNICATION

/* This rule makes the communication decision using the formula * with *Cmt and Cc from Section 5.*/ IF CG is a possible communicative goal to communicate fact F to team to terminate OP] AND Estimated value of non-communication for CG is medium AND Estimated value of communication for CG is low THEN post CG as a communicative goal to communicate fact F to team to terminate OP] /* This rule checks for unachievability of role-monitoring constraints involving an AND-combination. See section 4.2. / 120

SAMPLE:RULE:DECISION-ON-COMMUNICATION

SAMPLE:RULE:MONITOR-UNACHIEVABILITY:AND-COMBINATION

Towards Flexible Teamwork

IF A current joint intention OP] involves an AND-combination AND i is a member performing role to execute sub-operator op AND no other member j is also performing role to execute sub-operator op AND i cannot perform role THEN Current joint intention OP] is unachievable, due to a critical role failure of i in performing op

Barbuceanu, M., & Fox, M. (1996). The architecture of an agent building shell. In Wooldridge, M., Muller, J., & Tambe, M. (Eds.), Intelligent Agents, Volume II: Lecture Notes in Arti cial Intelligence 1037. Springer-Verlag, Heidelberg, Germany. Calder, R. B., Smith, J. E., Courtemanche, A. J., Mar, J. M. F., & Ceranowicz, A. Z. (1993). Modsaf behavior simulation and control. In Proceedings of the Conference on Computer Generated Forces and Behavioral Representation. Chu-Carroll, J., & Carberry, S. (1996). Con ict detection and resolution in collaborative planning. In Wooldridge, M., Muller, J., & Tambe, M. (Eds.), Intelligent Agents, Volume II: Lecture Notes in Arti cial Intelligence 1037. Springer-Verlag, Heidelberg, Germany. Cohen, P. R., & Levesque, H. J. (1991a). Con rmation and joint action. In Proceedings of the International Joint Conference on Arti cial Intelligence. Cohen, P. R., & Levesque, H. J. (1991b). Teamwork. Nous, 35. Coradeschi, S. (1997). A decision mechanism for reactive and coordinated agents. Tech. rep. 615, Linkoping University. (Licentiate Thesis). Decker, K., & Lesser, V. (1995). Designing a family of coordination algorithms. In Proceedings of the International Conference on Multi-Agent Systems. Durfee, E., & Lesser, V. (1991). Partial global planning: a coordination framework for distributed planning. IEEE transactions on Systems, Man and Cybernetics, 21 (5). Firby, J. (1987). An investigation into reactive planning in complex domains. In Proceedings of the National Conference on Arti cial Intelligence (AAAI). Gmytrasiewicz, P. J., Durfee, E. H., & Wehe, D. K. (1991). A decision theoretic approach to co-ordinating multi-agent interactions. In Proceedings of International Joint Conference on Arti cial Intelligence. Grosz, B. (1996). Collaborating systems. AI magazine, 17 (2).
121

References

Tambe

Grosz, B., & Kraus, S. (1996). Collaborative plans for complex group actions. Arti cial Intelligence, 86, 269{358. Grosz, B. J., & Sidner, C. L. (1990). Plans for discourse. In Cohen, P. R., Morgan, J., & Pollack, M. (Eds.), Intentions in Communication, pp. 417{445. MIT Press, Cambridge, MA. Halpern, J. Y., & Moses, Y. (1990). Knowledge and common knowledge in a distributed environment. Journal of the ACM, 37 (3), 549{587. Hayes-Roth, B., Brownston, L., & Gen, R. V. (1995). Multiagent collaboration in directed improvisation. In Proceedings of the International Conference on Multi-Agent Systems (ICMAS-95). Hill, R., Chen, J., Gratch, J., Rosenbloom, P., & Tambe, M. (1997). Intelligent agents for the synthetic battle eld: a company of rotary wing aircraft. In Proceedings of the Innovative Applications of Arti cial Intelligence. Jennings, N. (1994). Commitments and conventions: the foundation of coordination in multi-agent systems. The Knowledge Engineering Review, 8. Jennings, N. (1995). Controlling cooperative problem solving in industrial multi-agent systems using joint intentions. Arti cial Intelligence, 75. Kaminka, G. A., & Tambe, M. (1997). Social comparison for failure monitoring and recovery in multi-agent settings. In Proceedings of the National Conference on Arti cial Intelligence, p. (Student abstract). Kinny, D., Ljungberg, M., Rao, A., Sonenberg, E., Tidhard, G., & Werner, E. (1992). Planned team activity. In Castelfranchi, C., & Werner, E. (Eds.), Arti cial Social Systems, Lecture notes in AI 830. Springer, NY. Kitano, H., Asada, M., Kuniyoshi, Y., Noda, I., & Osawa, E. (1995). Robocup: The robot world cup initiative. In Proceedings of IJCAI-95 Workshop on Entertainment and AI/Alife. Kitano, H., Tambe, M., Stone, P., Veloso, M., Noda, I., Osawa, E., & Asada, M. (1997). The robocup synthetic agents' challenge. In Proceedings of the International Joint Conference on Arti cial Intelligence (IJCAI). Laird, J. E., Jones, R. M., & Nielsen, P. E. (1994). Coordinated behavior of computer generated forces in tacair-soar. In Proceedings of the Fourth Conference on Computer Generated Forces and Behavioral Representation. Orlando, Florida: Institute for Simulation and Training, University of Central Florida. Levesque, H. J., Cohen, P. R., & Nunes, J. (1990). On acting together. In Proceedings of the National Conference on Arti cial Intelligence. Menlo Park, Calif.: AAAI press. Lochbaum, K. E. (1994). Using collaborative plans to model the intentional structure of discourse. Ph.D. thesis, Harvard University.
122

Towards Flexible Teamwork

Mitchell, T. M., Keller, R. M., & Kedar-Cabelli, S. T. (1986). Explanation-based generalization: A unifying view. Machine Learning, 1 (1), 47{80. Newell, A. (1990). Uni ed Theories of Cognition. Harvard Univ. Press, Cambridge, Mass. Pimentel, K., & Teixeira, K. (1994). Virtual reality: Through the new looking glass. Windcrest/McGraw-Hill, Blue Ridge Summit, PA. Pollack, M. (1992). The uses of plans. Arti cial Intelligence, 57, 43{68. Rajput, S., & Karr, C. R. (1995). Cooperative behavior in modsaf. Tech. rep. IST-CR-95-35, Institute for simulation and training, University of Central Florida. Rao, A. S., Lucas, A., Morley, D., Selvestrel, M., & Murray, G. (1993). Agent-oriented architecture for air-combat simulation. Tech. rep. Technical Note 42, The Australian Arti cial Intelligence Institute. Reilly, W. S. (1996). Believable Emotional and Social Agents. Ph.D. thesis, School of Computer Science, Carnegie Mellon University. Rich, C., & Sidner, C. (1997). COLLAGEN: When agents collaborate with people. In Proceedings of the International Conference on Autonomous Agents (Agents'97). Rosenbloom, P. S., Laird, J. E., Newell, A., , & McCarl, R. (1991). A preliminary analysis of the soar architecture as a basis for general intelligence. Arti cial Intelligence, 47 (1-3), 289{325. Sen, S. (1996). Proceedings of the Spring Symposium on Adaptation, Coevolution and Learning. American Association for Arti cial Intelligence, Menlo Park, CA. Sidner, C. (1994). An arti cial discourse language for collaborative negotiation. In Proceedings of the National Conference on Arti cial Intelligence (AAAI). Smith, I., & Cohen, P. (1996). Towards semantics for an agent communication language based on speech acts. In Proceedings of the National Conference on Arti cial Intelligence (AAAI). Sonenberg, E., Tidhard, G., Werner, E., Kinny, D., Ljungberg, M., & Rao, A. (1994). Planned team activity. Tech. rep. 26, Australian AI Institute. Stone, P., & Veloso, M. (1996). Towards collaborative and adversarial learning: a case study in robotic soccer. In Sen, S. (Ed.), AAAI Spring Symposium on Adaptation, Coevolution and Learning in multi-agent systems. Tambe, M. (1995). Recursive agent and agent-group tracking in a real-time dynamic environment. In Proceedings of the International Conference on Multi-agent systems (ICMAS). Tambe, M. (1996). Tracking dynamic team activity. In Proceedings of the National Conference on Arti cial Intelligence (AAAI).
123

Tambe

Tambe, M. (1997a). Agent architectures for exible, practical teamwork. In Proceedings of the National Conference on Arti cial Intelligence (AAAI). Tambe, M. (1997b). Implementing agent teams in dynamic multi-agent environments. Applied Arti cial Intelligence. (to appear). Tambe, M., Johnson, W. L., Jones, R., Koss, F., Laird, J. E., Rosenbloom, P. S., & Schwamb, K. (1995). Intelligent agents for interactive simulation environments. AI Magazine, 16 (1). Tambe, M., & Rosenbloom, P. S. (1995). RESC: An approach for real-time, dynamic agent tracking. In Proceedings of the International Joint Conference on Arti cial Intelligence (IJCAI). Tambe, M., Schwamb, K., & Rosenbloom, P. S. (1995). Building intelligent pilots for simulated rotary wing aircraft. In Proceedings of the Fifth Conference on Computer Generated Forces and Behavioral Representation. Tidhar, G., Selvestrel, M., & Heinze, C. (1995). Modeling teams and team tactics in whole air mission modeling. Tech. rep. Technical Note 60, The Australian Arti cial Intelligence Institute. Williamson, M., Sycara, K., & Decker, K. (1996). Executing decision-theoretic plans in multi-agent environments. In Proceedings of the AAAI Fall Symposium on Plan Execution: Problems and Issues.

124