Collaborative Plans for Group Activities
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Distributed AI. Pages 367-374.
© 1993 International Joint Conferences on Artificial Intelligence
Abstract
The original formulation of SharedPlans [Grosz and Sidner, 1990] was developed to provide a model of collaborative planning in which it was not necessary for one agent to have intentions toward an act of a different agent. This formulation provided for two agents to coordinate their activities without introducing any notion of jointly held intentions (or , ' weintentions') . However, it only treated activities that directly decomposed into single agents actions. In this paper we provide a revised and expanded version of SharedPlans that accommodates actions involving groups of agents as well as complex actions that decompose into multi-agent actions. The new definitions also allow for contracting out certain actions, and provide a model with the features required in Bratman's account of shared cooperative activity [Bratman, 1992]. A reformulation of the model of individual plans that meshes with the definition of SharedPlans is also provided .
- Pi})
- BEL(G,(3Ra)[Ra E Recipes(a) A {Pi,Pi} s;; Rail (I) ({Pi, pi} c Ra- (la) (36j,pj)[({Pi,Pi} u {hi, Pi}= Ra)A (lb) (3T 11 et, P 11 et, Rget) [Int.To(G, GET(G, {hj, Pi}), Tp, T 11 et, C 11 et/a)A (I c) CBA(G, GET(G, {6j, Pi}), R 11 et, T 11 et)A (ld) FIP(P 11 e~,G,GET(G,{6i,Pi}), Tp, Tger. Rget, C~et/a)]A (le) (Vhj E {6j,pj}3T6 1 )WCBA(G,6j,T6 1 )J)),Tp)) 1\ (2) set(Pi) = (set[,B~o] set[,Br])
- V Pr E set[Pr] 3T.Ilr ){ (2a1a) [Int.To(G, Pr, Tp, T.llr, C.llr/a)A (2alb) BEL(G, WCBA(G, .Br, T.llr ), Tp)] V (2a2) [(3Gl, 1'. T..,) (2a2a)
- BEL(G, GTD(G, 1', G1, .Br, Ttl., T..,), Tp)ll (2a2b) Int.To(G, 1', Tp, T..,, C..,/.llr/a)A (2a2c) Int.Th(G, (3R.Ilr) CBA( G1, .Br, R.llr, T.llr ), Tp, T.llr, C.llr/a)A (2a2d) BEL(G, WCBA(G, 1', T..,), Tp)]]} 1\
- V.B~o E set[,Bk] 3T.Ilk) (2bl) [Pot.Int.To( G, .8k, Tp, T.llk, C.llk ta)A (2b2) BEL(G, WCBA(G, .8k, T.llk ), Tp)]]
- PSP(
- P,G, a, Tp, Ta, Ca) (3{,8;' p;} )
- G,(3Ra)[{,B;,p;} ~ Ra ARa E Recipes(a)],Tp) A set(,B;) = set[.BA.] U set[.Br) 1\ (1) MB(G, (VGi E G) lnt.Th(Gj, Done(G, a, Ta, Ra), Tp, Ta, Ca), Tp)A (2) (V.Br E set[.Br ]s.t.singleagent(.Br )3Gk E G, T~.) (2a)
- G, Int. To( GAo, .Br, Tp, T~., C~rfa), Tp)A (2b) MB(
- G,WCBA(GA.,.Br,T~.)A (2c) (VGi E G, Gi ::/; Gk)lnt.Th(Gj, (3R~.) CBA(Gk, .Br, R~ •• T~. ), Tp, T~., Ccba/~.ta), Tp)) 1\
- V.Br E set[.Br] s.t. multiagent(.Br)3Gk C G,T~.) (3al) [MB(G, (3P~.)SP(P~ •• Gk, .Br, Tp, T~., C~rfa) , Tp)A (3a2) (3P~.)SP(P~., Gk, .Br, Tp, T~., C~./a)A (3b) MB(G,WCBAG(Gk,.Br,T~.)A (3c) (VGi E {G \ G"})lnt.Th(Gi, (3R~.) CBAG(Gk, .Br, R~., T~. ), Tp, T~., Ccbag/~.ta), Tp)) 1\
- V,B" E set[.BA.]) (3Telab) (4a)
- G, (VGi E G)Int.To(Gj, Make-SP /lnt( Gj, G, .8k, Ca ), Tp, Te~ab, Celabf~kfa )A (4b) WCBAG(G, .8k, T~k ), Tp)]) References
- [Allen and Perrault, 1980] J.F . Allen and C.R. Perrault. Anal~zing intention in utterances. Artificial Intelli- gence, 15(3) :143-178, 1980.
- [Balkanski, 1990] C. Balkanski. Modelling act-type rela- tions in collaborative activity. Tr-23-90, Harvard Uni- versity, 1990.
- [Bratman et a/., 1988] M. Bratman, D. Israel, and M. Pollack . Plans and resource-bounded practical rea- soning . Computational Intelligence, 4:349-355, 1988.
- [Bratman, 1987] Michael E. Bratman. Intention, Plans, and Practical Reason. Harvard University Press, Cam- bridge, Massachusetts and London, England, 1987.
- [Bratman , 1992] M. E. Bratman. Shared cooperative ac- tivity. The Philosophical Review, 101 :327-341, 1992.
- [Cohen and Leveque, 1991] P. Cohen and H. Leveque. Teamwork . Tr 503, SRI International, 1991.
- [Cohen and Levesque, 1990] P. R. Cohen and Hector Levesque . Rational interaction as the basis for com- munication . In Cohen et a/. 1990.
- [Cohen et al., 1990] P. R . Cohen, J. Morgan, and M. E. Pollack (editors) . Intentions in Communica- tion. MIT Press, 1990.
- [Grosz and Sidner, 1986] B.J. Grosz and C.L . Sidner. Attention, intentions, and the structure of discourse. Computational Linguistics, 12(3) , 1986.
- [Grosz and Sidner, 1990] B.J. Grosz and C.L . Sidner. Plans for discourse. In Cohen et a/. 1990. •
- [Kraus and Lehmann, 1988] S. Kraus and D. Lehmann. Knowledge, belief and time. Theoretical Computer Science, 58:155-174, 1988.
- [Kraus , 1993] S. Kraus. Agents contracting tasks in non- collaborative environments. In Proc. of AAAI-93, Washington, D.C ., 1993.
- [Lochbaum et al., 1990] K.E. Lochbaum, B.J . Grosz, and C .L. Sidner. Models of plans to support communi- cation: An initial report . In Proceedings of AAAI-90, Boston, MA, 1990.
- [Lochbaum, 1991] K. E. Lochbaum. An algorithm for plan recognition in collaborative discourse. In Proc. ACL-91, Berkeley, CA, 1991.
- [Pollack, 1990] M. Pollack. Plans as complex mental at- titudes. In Cohen et a/. 1990.
- [Rao et a/., 1992] A. S. Rao, M. P. Georgeff, and E. A Sonenberg. Social plans. In Decentralized Artificial Intelligence, Volume 3. Elsevier Science Pub., 1992.
- [Searle, 1990] J .R. Searle. Collective intentionality. In Cohen et a/. 1990.
- Grosz .and Kraus
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Collaboration in planning and acting is an essential in gredient of multi-agent cooperative problem solving. In this paper we present a model of collaborative planning that supports cooperative problem solving by teams con sisting of humans and computer systems. The model deals more completely with collaboration than previous theories did in meeting two criteria. First , collabora tive planning and activity cannot be analyzed simply in terms of the plans of individual agents, but require an integrated treatment of the beliefs and intentions of the different collaborating agents. Second, collaborative planning is a refinement process; a partial plan descrip tion is modified over the course of planning by the mul-
*We thank Joyce Friedman for many provoking questions, and Karen Lochbaum for the same and for helpful comments on many drafts. This research was initiated when the first author was a Harold Perlman Visiting Professor, Hebrew Uni versity, Jerusalem. Partial support for the first author was provided by US WEST Advanced Technologies. The second
author was supported by NSF Grant No. IRI-9123460.
Sarit Kraus
Dept. of Mathematics and Computer Science Bar Han University, Ramat Gan, 52900 Israel sarit@bimacs.cs. biu.ac.il
tiple collaborating agents. This model grew out of an attempt to provide an adequate treatment of the in tentional component of discourse structure [Grosz and Sidner, 1986]. However, many multi-agent situations re quire that agents have an ability to plan and act to gether; merely avoiding conflicting actions or situations is not sufficient . Thus, the model is applicable not only to natural language processing, but also to the general problem of the design of computer-based collaborating agents.
The original formulation of the SharedPlan model of collaborative planning [Grosz and Sidner, 1990] extended Pollack's mental state model of plans [Pollack, 1990] to the situation in which two agents jointly have a plan to perform some action requiring actions by both agents. Pollack's definition of the individual plan of an individ ual agent to do an action a includes four constituent mental attitudes: (1) belief that performance of certain actions {J; would entail performance of a; we will refer to the {J; as constituting "a recipe for a;" (2) belief that the agent could perform each of the {J;; (3) intentions to do each of the {J; ; ( 4) an intention to do a by do ing the {J;. To define Shared Plans, Grosz and Sidner modified these components to provide a specification of the set of beliefs and intentions required for collabora tive action. In subsequent work [Lochbaum et a/., 1990; Lochbaum, 1991], algorithms were provided for con structing and augmenting SharedPlans in the context of a dialogue.
Although this formulation overcame several problems of previous models of planning for discourse (e.g. the treatment of intentions of one agent toward another agent's actions in applications of speech act theory [Allen and Perrault, 1980]) , it had several problems that emerged when we attempted to apply it lLochbaum et a/., 1990; Lochbaum, 1991]. First, the original model presumed that every multi-agent action decomposed di rectly into single agent actions; a similar assumption underlies several alternative models (e.g. [Cohen and Levesque, 1990]). As a result, the model did not ad equately provide for complex activities involving joint activity at multiple levels or for meshing of individual plans for individual action with collaborative plans for joint activity. Second, the model did not account for the commitment of an agent to the success of a collaborative partner's actions . This omission combined with the first so that the model accepted some plans as collaborative that were not. 1 Third, the agents who undertake the development of a collaborative plan often do not know a complete recipe for accomplishing their joint action; the model did not provide a sufficient means of describing the mental state of agents in this situation.2 Each of these problems is addressed in this paper.
Collaborative activity must rest eventually on the ac tions of individual agents; thus, SharedPlans must in clude as constituents at some levels the individual plans of individual agents. But these individual plans may be more complex than those accounted for by Pollack's for mulation in two ways: the recipes require different types of relations [Balkanski, 1990] 3 , and an agent may not initially know a complete recipe. Hence, we also provide a revised definition of the plans of an individual agent.
We begin the description of the revised model with an overview of different types of intentional attitudes that play a role in collaborative planning. Then we provide a definition of individual plans that accommodates more complex recipes but still requires complete knowledge of the recipe. To describe these full individual plans re quires a specification of certain properties of intention, so we define the Int. To operator at this point . Next, we show how to ease the complete knowledge requirement, yielding a definition of partial individual plan. We then define SharedPlans recursively in terms of full and par tial SharedPlans. A full SharedP/an is the collaborative correlate of a full individual plan and includes full in dividual plans as constituents. To describe interactions among the intentions of the different agents requires that we introduce the notion of an agent intending that some proposition hold so we explain the Int. Th operator in this section. Finally, we provide a definition of partial SharedP/an. At each stage we discuss those aspects of the resulting theory that address the problems described above to provide a more adequate model of collaborative activity.
2 Attitudes of Intention
The definitions of individual and SharedPlans will use a first-order logic augmented with several modal oper ators. We introduce four different intention operators. Two of these, Int . To and Int . Th, represent intentions that have been adopted by an agent. The other two, Pot. Int. To and Pot. Int. Th, are variations of the first two that are used to represent potential intentions, i.e. inten tions an agent is considering adopting but to which it is not yet committed. Int. To and Pot. Int. To are action directed whereas Int . Th and Pot. Int. Th are proposition directed.
1 For example, joint activity like that in Searle's MBA counterexample [Searle, 1990], but involving actions that de composed at multiple levels would have been inaccurately characterized.
2 The notion of a partial SharedPlan, SharedPlan*, was intended to represent this kind of partiality, but. was never specified in any detail.
3 ln Pollack's simple plans the {3; and a were related only by the action relation of generation. .
An Int. To commits an agent to means-ends reason ing [Bratman, 1987] whereas an Int. Th does not directly engender such behavior. Int. Th's form the basis for meshing subplans, helping one's collaborator, and co ordinating status updates [Cohen and Leveque, 1991]. An Int. Th may, however, lead to adoption of an Int. To and thus indirectly to means-ends reasoning. Potential intentions are used to account for an agent's need to weigh different possible courses of actions [Bratman et a/., 1988]; they typically arise in the course of means ends reasoning. Attitudes of Pot. Int. To stem from an agent's deliberations about how to do some action it is committed to perform. Pot. Int. Th's arise in the course of collaborative planning and are needed to insure that agents' individual plans mesh correCtly [Bratman, 1992].
The difference among these operators can be illus trated with an example we will use throughout the pa per. Two agents, Jan and Sandy, have agreed to make dinner together. Their collaborative plan consists of Jan making an appetizer, Sandy the main course, and the two of them together making the dessert. Their Shared Plan to make dinner includes Jan having an intention to [Int. To] make the appetizer (and an individual plan for doing so), Sandy having an intention to [Int. To] make the main course (and an individual plan for doing so), and their having a SharedPlan to make the dessert . The SharedPlan for making dinner also includes Sandy's in tention that [Int. Th] Jan 'can make' the appetizer, and Jan's intention that [Int. Th] Sandy 'can make' the main course.
Jan may have decided to make cheese puffs for the appetizer, but not yet have chosen a recipe for doing so. If so, his individual plan will be partial. It will include an Int . To get a recipe for cheese puffs and a full individual plan for doing so. 4 In addition, he believes that he can perform all of the actions in the recipe once he gets it. As he determines the recipe and thus the actions he needs to perform (according to that recipe), he adopts potential intentions to [Pot.Int. To] perform these actions. The potential intentions will become part of a deliberation process [Bratman et a/., 1988] and through that process may become Int. To's.
In the definitions that follow, Int. To( G,Ot,Ti,Tcr,Ccr) represents the agent G's intention at time 1i to do ac tion Ot at time Tcr in the context Ccr, (the role of context will be discussed later); Int. Th{G,prop,Ji,Tprop,Cprop) represents an agent G's intention at time 1i that a cer tain proposition prop hold at time Tprop in the context Cprop. Adoption of an intention of either sort commits an agent to not adopting conflicting intentions, and may constrain replanning in case of failure [Bratman, 1987].
The definitions below make use of several opera tors that we can only define informally in this paper. GTD(Gl,"}',G2,0t,Tcr,T-y) (read "get to do") holds if G1's doing r at T-y will cause G2 to intend to do Ot at Tcr or (if G2 is a group of agents) have a SharedPlan to do Ot . The operator CBA (can bring about), associated with an agent, an action, a recipe, and a time, means that the afent either can do the action at th~ time usin_g the recipe or can get another agent to do 1t; CBAG 1s the analogous group operator. Done(G, a, T0 , Ro) holds when G (either a group or a single agent) has done a over time interval T0 using the recipe R0 ·
4 The requirement that the agent have a full plan for get ting the recipe may seem too strong, but it is necessary to avoid an infinite recursion.
In addition, we will use Ra to denote a recipe for a, i.e. a specification of a group of actions, which we will refer to as f3i, the doing of which under appropriate constraints, Pi, will constitute performance of a [Pollack, 1990; Balkanski, 1990; Lochbaum et a/., 1990]. A recipe may include uninstantiated variables (e.g. for the agent or time of an action) and constraints on these variables. We assume each agent has a library of recipes that it collects and updates over time. Agents' libraries may differ, and the successful completion of a SharedPlan may require integrating recipes from different libraries, i.e. from dif ferent agents.
3 Individual Plans and Intending To
3.1 Full Individual Plans
The definition of a full individual plan, FIP, is given in Figure 1. It specifies those conditions under which an in dividual agent G can be said to have a plan P, at time Tp, to do action a at time To using recipe Ro in the con text C01 · Full plans are distinguished by the requirement that the agent know a complete recipe for doing the ac tion; as a result Ro is a parameter of the operator. A full individual plan for a represents the mental state of an agent after he has completely determined the means by which he will do a and has full-fledged intentions to do the actions in R0 · Most typically an agent will not have a full plan until after he has done some or all of the actions in Ra; thus, most often agents have only partial plans. However, it is useful to understand the limiting case of the full plan before examining the partial version.
We will illustrate the FIP by showing its use in de scribing Sandy's individual plan for making the main course in the meals example. According to Clause (0), Sandy believes that a particular recipe, say his mother's recipe for lasagne, is a recipe for making a main course. The remaining clauses provide a specification of certain attitudes Sandy must hold with respect to the individual constituents of this recipe. In particular, for each action f3i in the recipe (e.g. making noodles, preparing sauce) , he must either intend to do the action ( 1) or believe that he can get someone else to do the action (2) . We will refer to the first case as the "core case" of the individual plan, and the second case as the "contracting case."
In the core case, the agent must believe either that the action is basic level and he can bring it about (1a), or that he has a recipe that will enable him to do the action and a full individual plan to carry out the actions in that recipe (1b). The Int. To operator in Clause (1) includes a context parameter, Cp;fo· that is used in any replan ning involving f3i. For the purposes of this paper, the important element of the context encoded in this param eter is a representation (using the Contributes relation FIP(P, G, a, Tp, Ta, Rc,, Ca)
5 1{ the action is basic level, this reduces to Pollack's EXEC operator. The connective V that we use in all the definitions is really exclusive or (XOR).
- Ra ={Pi, Pi} A BEL(G, RaE Recipes( a), Tp)A (VPi3Tp; ){
- (Int.To(G, Pi, Tp, Tp;, Cp;fa)A
- (I a) ([basic.level(Pi}A
- BEL(G, CBA(G, Pi, REmpt 11 , Tp;), Tp))v
- (I b) [-.basic.level(Pi) A (3Pp;, Rp.) (BEL(G, CBA(G, Pi, Rp;, Tp.), Tp)A FIP(Pp;, G, Pi, Tp, Tp;, Rp;, C.e;ta))])] V
- [3(G!,'"Y,T-,)
- [BEL(G, GTD(G, -y, G1, Pi, Tp;, T..,), Tp)A
- lnt.To(G, -y, Tp, T..,, C-,//3;/a)A
- Int.Th(G,(3Rp;) CBA(G1, Pi, Rp;, Tp.), Tp, Tp;, Cp;fa)A
- (2dl) ([basic.level('Y )A
BEL(G, CBA(G, -y, REmpt 11 , T..,), Tp))v
- (2d2) [-.basic.level('Y) A 3(R..,, P..,) (BEL(G, CBA(G, -y, R..,, T..,), Tp)A FIP(P..,, G, -y, Tp, T..,, R..,, C-,t.B;ta))])]]}
Figure 1: Full Individual Plan
lnt.To(G, a, Ti, Ta, Ca)
- ( 1) [basic.level( a )]V
- ( 2) [ -.basic.level( a )A
- [(3P, Ra)[FIP(P, G, a, Ti, Ta, Ra, Ca)A BEL(G, CBA(G, a, Ra, Ta), T;)]] V
- [(3P, Tach)[PIP(P, G, a, Tp, Ta, Ca)A lnt .To(G, Achieve((3Ra)FIP(P, G, a, Tp, Ta, Ra, Ca)), Ti, Tach, Cachfa)]JJ
Figure 2: The definition of Int. To
[Lochbaum eta/., 1990]) of the fact that G is doing /3i at time Tp; as part of G's performance of action a at time T0 ; this element is constructed recursively as an agent chooses recipes and constructs plans for the actions in them.
The definition of intending to do an action is given in Figure 2. 6 Within a full individual plan, Clause (2b) of this definition, does not apply. An Int. To do an action requires either ( 1) that the action be basic (in which case the agent is committed to doing the act [Bratman, 1987], something that we do not formalize here) or (2a) that the agent have a full individual plan to do the action. Thus, a full individual plan to do a requires intentions to do each of the actions, /3i, involved in a recipe for a which in turn require full individual plans for each of these /3i, until we get to basic level acts. 7
The contracting case for accomplishing /3i has not been discussed in previous work on multi-agent plans, but clearly arises in many cases. For example, someone who has a plan to renovate his house might include in that plan contracting out certain subtasks, e.g. the refinish ing of the floors. To contract out an action, the agent must believe there is some action r that he can use to get another agent to do {3; (Clause (2a) of Figure 1). Fur thermore, he must intend to do r (2b), believe he can bring about r, and if r is not basic-level (2d2), have a full plan for doing r. Clause (2c) represents agent G's commitment to the success of the contractor in doing {3;. Notice that contracting is not in and of itself col laborative [Kraus, 1993]; Clause (2c) is one way: the contractor does not have the kinds of Int.Th's we will require in the SharedPlan definitions later; only the con tracting agent does. Int. Th will be discussed in more detail under SharedPlans (Section 4.1), where there is such reciprocity.
6 Space constraints preclude inclusion of the basic axiom for avoiding the adoption of conflicting intentions as well as other related axioms.
7 This is the case that PoHack's definition covers, but it does so only for recipes in which actions are related by generation.
In the meals example, Sandy may decide that the most efficient way to make the lasagne is to get Tony to make the sauce and sell it to him. In this case, Sandy's in dividual plan would include an action r (e.g. making a sales agreement) that resulted in Tony's providing the sauce. For Sandy's plan to be complete, Sandy must believe that the action r that he will do either is a basic level action that he is able to do or is an action for which he knows a recipe and for which he has a full individ ual plan. As a consequence of Clause (2c), Sandy must be willing to assist in Tony's success, e.g. helping him find some of the raw ingredients if necessary. As a con sequence of this clause and an intention-conflict axiom, Sandy cannot intend to do anything that would make it impossible for Tony to make the sauce.
3.2 Partial Individual Plans
Individual plans may be partial in several ways. Each of these will lead to some Int . To in which Clause (2b) of the definition in Figure 2 applies. The Achieve function in this clause maps a proposition to a generalized action [Pollack, 1990]. 8 A typical way in which partial individ ual plans differ from full plans is in allowing an agent to have only a partial recipe for an action. As can be seen in the definition in Figure 3, the minimal requirement for the partial plan is that the agent believe there is a recipe for a (Clause (0)), believe that it is able to determine any constituents of that recipe not already known (lc), in tend to obtain that recipe (1b) and have a full individual plan for doing so (1d); a procedure associated with the GET operator will add potential intentions to do all the actions in this plan . 9 For example, if an agent is assem bling a bicycle from a kit, he must believe that the ac companying instructions are complete, that he can read the instructions, and that he can perform each of them at the requisite time. While reading the instructions, the agent will adopt potential intentions to do the actions .
Clause (2) represents the attitudes of the agent to-
8 This function may be seen as connected to an agenda of tasks maintained by the agent . Discussion of this component of the model is beyond the scope of this paper. Briefly, be cause the agent must be committed to completing his partial plan for a for the Int. To operator to hold, the agenda must include tasks for establishing any of the beliefs and intent.ions needed in a full plan but absent in the partial plan.
9 WCBA is a weaker version of the can bring about oper ator, one in which the agent may only believe it can find a recipe that it can use to do the action; WCBAG is a corre sponding group operator.
(3{Pi, Pi})[
(0) [BEL(G,(3Ra)[Ra E Recipes(a) A {Pi,Pi} s;; Rail
(I) ({Pi, pi} c Ra-
(la) (36j,pj)[({Pi,Pi} u {hi, Pi}= Ra)A
(lb) (3T11et, P11et, Rget)
[Int.To(G, GET(G, {hj, Pi}), Tp, T11et, C 11 et/a)A
(I c) CBA(G, GET(G, {6j, Pi}), R11et, T11et)A
(ld) FIP(P11e~,�,�ET(�,{6i,Pi}),
(le) (Vhj E {6j,pj}3T6 1 )WCBA(G,6j,T6 1 )J)),Tp)) 1\
Tp, Tger. Rget, C~et/a)]A
(2) set(Pi) = (set[,B~o] U set[,Br])fl
( 2a) (V Pr E set[Pr] 3T.Ilr ){
(2a1a) [Int.To(G, Pr, Tp, T.llr, C.llr/a)A (2alb) BEL(G, WCBA(G, .Br, T.llr ), Tp)] V
(2a2) [(3Gl, 1'. T..,)
(2a2a) [BEL(G, GTD(G, 1', G1, .Br, Ttl., T..,), Tp)ll
(2a2b)
Int.To(G, 1', Tp, T..,, C..,/.llr/a)A
(2a2c)
Int .Th(G, (3R.Ilr)
CBA( G1, .Br, R.llr, T.llr ), Tp, T.llr, C.llr/a)A
(2a2d) BEL(G, WCBA(G, 1', T..,), Tp)]]} 1\
(2b) (V.B~o E set[,Bk] 3T.Ilk)
(2bl) [Pot.Int .To( G, .8k, Tp, T.llk, C.llk ta)A
- (2b2) BEL(G, WCBA(G, .8k, T.llk ), Tp)]]
Figure 3: Core of Definition of Partial Individual Plan
wards those portions of the recipe for a that he has al ready obtained (i.e., {/3;, pi} ) 10 . This part of his plan · may still be partial in several ways; we discuss this case only informally here and give a more extensive discus sion for the SharedPlan analogue. First, an agent may only have Int. To's for some of the {3; 's in his recipe for a (2a1a) . In addition, for some of those /3; 's that he in tends, he may not have recipes. In this case, the agent must have on its agenda the task of finding a recipe for any {3; for which it does not have a recipe . . In the con tracting case (2a2), a plan is partial if the agent only has a partial plan for r. Finally (2b), an individual plan may be partial because the agent has potential intentions that still need to be reconciled. In particular, when an agent selects a recipe for a, it directly adopts Pot.Int. To do the actions {3; in that recipe. However, these poten tial intentions must be reconciled with other intentions. If the agent discovers a conflict between adopting the intentions required for that recipe and intentions it al ready has, the reconciliation process may lead either to its dropping previous intentions or to its looking for a different recipe for the current action. The choice will depend on contextual factors captured in the context ar gument of the intention operator.
When an agent with only a partial individual plan needs to find a recipe for an action, there are two options: research (e.g. looking in an instruction manual, asking an expert) and contracting out the doing of the action. In contrast, agents engaged in SharedPlans can enlist the aid of their collaborators in such situations.
10 This clause is not applicable if the agent has not obtained any portion of the recipe, i.e. {.Bi, Pi} = 0.
4 SharedPlans and Intending That
Both the belief and the intention components of collab orative plans are more complex than those of individual plans. The collaborating agents must establish mutual belief of the ways in which they will perform their joint activity and must agree on the agent or agents who will do each action. Actions requiring multiple agents engen der subsidiary SharedPlans of groups of agents; those re quiring only a single agent lead to subsidiary individual plans. The agents also need to establish mutual belief of their individual intentions to act.
There are several important properties of these belief and intention components that are captured in the def initions that follow. First, agents do not need to know recipes for any actions that they are not personally com mitted to doing. In our meals example, Jan and Sandy need to establish mutual belief of the recipe for making dinner, namely that this will comprise Jan's making the appetizer, Sandy the main course, and the two of them together making the dessert. Only Jan needs to know the recipe for the appetizer; but Sandy needs to share mutual belief that Jan has such a recipe and can carry it out. The analogous case holds for Sandy and a recipe for the main course. In contrast, Sandy and Jan need mutual belief of the recipe for making dessert . Second, an agent only has Int. To's to acts of which it is the agent . However, it has Int. Th's that the actions of other agents be successfully done. More generally, the ways in which the belief and intention operators are used differ . In the following definitions we presume the usual definition of mutual belief [Kraus and Lehmann, 1988] which requires infinite nestings of individual beliefs, but utilizes only a single belief operator, BEL. In contrast, to handle the intentions that arise in SharedPlans, we need two opera tors- Int. To and Int . Th- but there is no need for infinite embeddings of these operators (either in themselves or within one another). However, both operators may be embedded within the mutual belief operator, MB.
The SharedPlan operator, representing that a group of agents G has a plan to collaboratively perform some action a, is defined recursively in terms offull a.nd partial SharedPlans as follows:
SP(P, GR, a, Tp, Tex, Cex)
(1) [(3Rex)FSP(P, GR, a, Tp, Tex, Rex, Cex)] V
- [PSP(P, GR, a, Tp, Tex, Cex) 1\ (3Pach, Tach) SP(Pach, GR, Achieve[(3Rex)FSP(P, GR, a, r,_., Tex, Rex, Cex)J, Tp, Tach· Cachjex)]
A group of agents will be said to have a SharedPlan just in case either (1) they have a full SharedPlan for doing a or (2) they have a partial SharedPlan, and a SharedPlan to complete that partial plan. As will be seen from the definitions of these two types of Shared Plans, each of these possibilities leads eventually to in dividual intentions to do actions, including actions of elaborating or extending partial plans.
4.1 Full SharedPlans
We will use the formula FSP(P,G,o,Tp,T0 ,Rex,Cex) to represent the situation in which a group of agents G has a full shared plan P at time Tp to do action o at FSP(P, G, o, Tp, Ta, Ra, Ca)
Ra = {.B;,p;} 1\ MB(G,Ra E Recipes(o),Tp)l\ (1) MB(G, [(VGj E G) lnt.Th(Gi, Done(G, o, Ta, Ra), Tp, Ta, Ca)], Tp)l\ (2) [(V.B; s.t. singleagent(/3;) 3G,. E G,Ttl;)[ (2a) MB(G, Int.To(G,, .8;, Tp, T/3;, C13;~a), Tp)l\ (2b) ([basic.level(/3;)1\ MB(G, CBA(G,, {3;, REmpt 11 , T/3; ), Tp))v (2cl) [-.basic.level(.B; )A MB(G, (3Ptl;, Rtl;) (2cla) [CBA(G,, {3;, Rtl;, Ttl;)/\ (2clb) FIP(Ptl; , G,, {3;, Tp, Ttl;, Rtl;, CtJi!a)], Tp)l\ (2c2) (3P/3;, Rtl;) (2c2a) [BEL(G,, CBA(G,, {3;, Rtl;, Ttl;), Tp)l\ (2c2b) FIP(P/3;, G,, {3;, Tp, Ttl;, Rtl;, CMa)]])A (2d) MB(G, (VGi E G, Gi f:. G,)Jnt.Th(Gj, (3Rtl;) CBA(G,, {3;, R13;, T13; ), Tp, T13;. Ccbaff3;fa), Tp)]] 1\ (3) [(V.B; s.t. multiagent(/3;) 3G,. C G)[ (3a1) MB(G,(3Pf3,,R/3;) (FSP(P/3;, Gk, {3;, Tp, T13;, R/3;, Ctl;/a)A CBAG(Gk, {3;, R13;, T13.)], Tp)l\ (3a2) (3PI3;, Rtl;) [FSP(Ptl;, Gk, {3;, Tp. Ttl;, Rtl;, CMa)A CBAG(Gk, .8;, R/3; ,Tf3; )]A (3b) MB(G, ('v'Gi E G \ Gk)Int .Th(Gj, (3RI3;) CBAG(Gk, {3;, Rtl;· Ttl;), Tp, Ttl;, Ccba/13;/a), Tp)]]
time Tex using recipe Rex in context Cex . 11 Figure 4 gives the clauses in the core portion of the definition of this operator. 12 As in the case of full individual plans, a full SharedPlan represents the mental state of agents when they have completely determined their course of action, a state which usually does not obtain until many actions in Rex have been done. Clause ( 1) states that all agents in the group collaborating in the SharedPlan have an in tention that they succeed in performing a . This Int. Th corresponds to Bratman 's requirement that the agents each "intend that we" a. The other portions of the defi nition address the need for the agents' subplans to mesh.
Clause (2) of the definition covers those situations in which a single agent is needed to perform an action {3; in the recipe for a. In this case, the group's Shared Plan includes (2a) mutual belief by all members in the group that one member, Gk, has an individual intention to do {3;; from this mutual belief, it can be inferred 13
11 The different group members may have different rea sons for engaging in the collaborative activity. For exam ple, hunger might underlie Jan's making dinner with Sandy, whereas a desire for social interaction underlies Sandy's mak ing dinner with Jan. (cf. [Bratman, 1992])
12 For space reasons, we have omitted the contracting out cases of FSP and PSP; they are similar to those for individual plans but with modifications for group knowledge and action.
13 This inference is based on the th.eorem that for every o, (·)BEL(G,Int.To(G, o,Tp,Ta,Ca),Tp) lnt.To(G,o, T., Ta, Ca) . The proof is based on (1) mutual belief axioms 6<raus and Lehmann, 1988] and on (2) the ax ioms that if o is a basic level action then (*) is true, (3) similar axioms as (*) for Pot.lnt .To, and for lnt.Th and
that �~c actually does have an Int. To. If {3; is basic level then (2b) the group must believe that �~c is able to bring about the action. Otherwise, the SharedPlan has embedded within it an individual plan. The group members must mutually believe (2cl) that there is some recipe which �~c knows and can use to bring about {3;. Clause (2c2) represents the fact that �~c does know a recipe that he believes will enable him to bring about {3,, and has a FIP for. doing f3.a using this recipe. Thus, the different scopings of (2cl) and (2c2) accurately cap ture an important distinction. �~c must know the recipe he will use to do [3,. The other members of the group do not need to know this recipe; however, all members of the group need to mutually believe that there is some recipe that �~c can use.
The Int. Th in Clause (2d) represents commitment on the part of all other agents in the group to ensuring that �~c can do {3; . 14 Although the preceding clauses have some analogue in the definition of FIP, this does not. This clause, along with Clauses (1) and (2a), dis tinguishes this situation from the contracting situation. All of the agents in G are committed to the performance of a and the {3; , and (through the context parameter) to the {3; as part of doing a.
We have developed several axioms that are needed to support the role of the Int. Th operator in coordinating the intentions and actions of different agents in collabo rative activities. We can provide only one example here, an axiom of helpful behavior in the Shared Plan context . This axiom applies whenever an intention of the type represented in Clause (2d) is held; such Int. Th's always arise from Gj and �~c collaborating. The axiom states that Gj will adopt a potential intention to do an action r that he believes will assist �~: in being able to do {3; (which in this . context is contributing to the joint ac- · tion a) if the group saving from this r is worth more to Gj than the cost of doing r. The axiom also addresses Bratman's requirement of minimally cooperatively sta ble intentions. For example, while chopping onions for the lasagne, Sandy may chop an extra one to assist Jan in making the cheese puffs. These axioms combined with the intention-conflict avoidance axiom provide the basis for agents adopting meshing subplans. Jan's individ ual plan for making the appetizer cannot produce inten tions that conflict with his intention that Sandy succeed in making the main course. For example, Jan cannot Int. To an action that would make it impossible for Sandy to boil the lasagne noodles. If potential intentions lead to consideration of adopting such conflicting intentions, the reconciliation axioms will cause one intention to be dropped; some portion of the SharedPlan will then be come, or remain, partial.
Clause (3) of the FSP is the extension to cover the case when a constituent in the recipe for a is a group ac tion. From (3a) group G's full SharedPlan for a is seen to include as a component the full SharedPlan of a sub group �~c to do {3;. As in the case of individual action, there is a distinction between members of this subgroup �~c who must know the recipe for {3; and have the FSP (3a2), and other members of the group who only need to believe there is some such recipe known to the sub group (3al); again the scoping difference captures this distinction. The context parameter of the FSP includes the information that {3; is being done as part of doing a. The first group can-bring-about clause (3al) repre sents the mutual belief of the group in the ability of the subgroup to do {3, at the appropriate time. The second group can-bring-about clause (3a2) is needed to ensure that the subgroup can actually bring about the FSP ac cording to the given recipe. Again, there is an Int. Th clause (3b) that represents a commitment on the part of all members of the group not in �~c to insuring that the members of �~c find a recipe for doing {3; 'that they can succeed in using.
Pot.Int.Th for any proposition.
14 Bratman [Bratman, 1992] and others [Cohen and Lev- · eque, 1991] provide arguments that mutual belief of individ ual intentions is not sufficient.
4.2 Partial SharedPlans
Like partial individual plans, partial SharedPlans differ from full ones in allowing agents to have only a partial recipe for action. And, analogously to the individual case, the minimal requirements for a group of agents having a partial Shared Plan are ( 1) that the agents mu tually believe there is a recipe for a that they can ob tain, (2) that they have a full SharedPian to obtain that recipe, and (3) that every member of the group have an individual intention for elaborating the recipe.
Figure 5 shows the portion of the definition of a par tial SharedPlan that represents the mental state of the agents when they have a recipe for a, but recipes for only some of the {3; 's involved in doing a . The {3; have been divided into two subgroups: the f3r are actions for which the group has done some deliberation and elaboration, including a decision of who will do the action; the f3~c are those actions for which it has not.
Clause (2) gives the conditions that must pertain for single agent f3r. According to Clause (2a), the group must agree on the agent of the action and mutually be lieve that this agent, G 1c, intends to do f3r. That G 1c does intend to do f3r may be concluded based on the ap propriate BEL and Int .To axioms and theorems. This Int. To operator may fulfill Clause (2b) of the definition in Figure 2; the agent may have only a partial plan for doing f3r , but it must have an intention to complete that plan.
Clause (2b) is a weaker form of the the can-bring about constraints in FSPs (Figure 4); notice that there is no clause corresponding to (2clb) and (2c2b) of FSPs, reflecting the partiality of PSPs. Clause (2c) of the PSP corresponds to (2d) in the FSP; it states that the other agents must all have an intention that the agent be able to perform f3r according to the appropriate recipe. This intention is a commitment on the part of the other agents to assisting G 1c .
Clause (3) shows that a similar situation pertains for those f3r that require a subgroup of agents. In this case, however, the subgroup must have a SharedPian to do the action; this SharedPian may be either a FSP or a PSP. Again (Clause (3c)), the other members of G must have an intention that the subgroup succeed. Finally ( 4), PSP(P,G, a, Tp, Ta, Ca)
(3{,8;' p;} )[
- MB(G,(3Ra)[{,B;,p;} ~ Ra ARa E Recipes(a)],Tp) A set(,B;) = set[.BA.] U set[.Br) 1\
- MB(G, (VGi E G) lnt.Th(Gj, Done(G, a, Ta, Ra), Tp, Ta, Ca), Tp)A
- (V.Br E set[.Br ]s.t.singleagent(.Br )3Gk E G, T~.)
- [MB(G, Int. To( GAo, .Br, Tp, T~., C~rfa), Tp)A
- MB(�,WCBA(�A.,.Br,T~.)A
- (VGi E G, Gi ::/; Gk)lnt.Th(Gj, (3R~.) CBA(Gk, .Br, R~ ·· T~. ), Tp, T~., Ccba/~.ta), Tp)) 1\
- (V.Br E set[.Br] s.t. multiagent(.Br)3Gk C �,T~.)
- (3al) [MB(G, (3P~.)SP(P~ ·· Gk, .Br, Tp, T~., C~rfa) , Tp)A
- (3a2) (3P~.)SP(P~., Gk, .Br, Tp, T~., C~./a)A
- MB(�,WCBA�(�k,.Br,T~.)A
- (VGi E {G \ G"})lnt.Th(Gi, (3R~.) CBAG(Gk, .Br, R~., T~. ), Tp, T~., Ccbag/~.ta), Tp)) 1\
- (V,B" E set[.BA.]) (3Telab)
- [MB(G, (VGi E G)Int .To(Gj,
- Make-SP /lnt( Gj, G, .8k, Ca ), Tp, Te~ab, Celabf~kfa )A (4b) WCBAG(G, .8k, T~k ), Tp)])
Figure 5: Core of Definition of Partial SharedPlan
there are the actions /3~.:. For these we require intentions on the part of every group member to find a recipe and decide who (sub-group or single agent) will do the ac tion. The Make-SP /Int operator corresponds to a group decision making process about who will do /3~.: and how if the whole group is doing it; discussion of this process is beyond the scope of this paper. Once they have elab orated the plan at least partially, the /3r case holds-.
5 Conclusions and Future Work
To provide an account of collaborative activity, Searle [Searle, 1990] introduced the notion of 'we-intention.' Grosz and Sidner [Grosz and Sidner, 1990] argued that such a notion should not be necessary and their initial formulation of SharedPlans avoids use of one. How ever, the definitions provided in that formulation could only accommodate group activity that directly decom posed into actions of individual agents. Subsequent work in AI on formalizing the plans and intentions of mul tiple agents has, like Searle's proposal, included some notion of joint intention [Cohen and Levesque, 1990; Rao et a/., 1992]. In this paper, we have provided a formulation that again avoids the need for a notion of joint intention , In this work, SharedP1ans serve two ma jor roles. They summarize the set df beliefs and inten tions needed for collaborative activity, and also provide the rationale for the process of revising beliefs and in tentions; consequently, they motivate the collaborative correlate of means-ends reasoning in the plans of an in dividual agent. SharedPlans ground out in the individ ual intentions of individual agents and the individual plans that they engender. This formulation accommo dates the properties of shared cooperative activity pro posed by Bratman [Bratman, 1992]. Intentions to do constituent actions form the basis of each individual's actions. Intentions-that directed toward other agents abilities to act and success in acting, as well as toward the success of the joint activity, ensure .cooperation in subplans and helpful behavior.
@inproceedings{ijcai1993p52,
title = {Collaborative Plans for Group Activities},
author = {Grosz, Barbara J. and Kraus, Sarit},
booktitle = {Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence, {IJCAI-93}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ruzena Bajcsy},
pages = {367--374},
year = {1993},
note = {Distributed AI},
url = {https://ijcai.org/proceedings/1993/52},
}
TY - CPAPER TI - Collaborative Plans for Group Activities AU - Grosz, Barbara J. AU - Kraus, Sarit T2 - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93 PB - International Joint Conferences on Artificial Intelligence PY - 1993 SP - 367 EP - 374 UR - https://ijcai.org/proceedings/1993/52 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: