A Scheme for Agent Collaboration in Open Multiagent Environments

1 Introduction

In multiagent planning, agents try to achieve goals, which can be independent, shared, or competitive. Re­ searchers have attempted to address the problem of coordinating interacting plans so as to increase effi­ ciency. The subject of coordination has been of continu­ ing interest in multiagent planning [Corkill 79, Georgeff 83, Zlotkin and Rosenschein 90, Martial 90, Osawa and Tokoro 92, Ephrati and Rosenschein 92, Kinny et al. 92]. Martial has investigated how planning agents can positively cooperate in distributed environments [Mar­ tial 90]. Many previous papers on distributed coordi­ nated planning mainly focused on how to resolve con­ flicts [Corkill 79, Georgeff 83]. Martial, however, studies situations where a positive effect can be reached, as mod­ eled by his favor relation. We also focus on the positive effect of cooperation in terms of collaborative plan con­ struction, and have developed a scheme for constructing collaborative plans among agents based upon their, pos­ sibly incorrect, beliefs and partial (incomplete) knowl­ edge of the world [Osawa and Tokoro 92]. The partiality of agents' skills and inconsistencies among agents' beliefs in open multiagent environments are not well treated in

2 Collaborative Plan Scheme Outline

Large, multiagent systems can be viewed as open dis­ tributed environments. Thus, agents have inconsistent and partial world views. In multiagent cooperative plan construction, several agents mutually generate collabo­ rative plans by inference based on their own beliefs and partial knowledge about the world. Therefore, mutual planning is confounded by disparities in agents' world knowledge.

In a multiagent system, an agent may have a goal or task which it cannot do alone. Contract-net proto­ col [Davis and Smith 83] provides a way for an agent who needs help (the requestor) to dynamically decom­ pose the task into subtasks, and to allocate the subtasks to other agents ( requestees) through negotiation. The contract-net protocol also provides dynamic and oppor­ tunistic control.

In open distributed environments, services, process­ ing capacity, and the connection topology of computing elements are continuously changing. At the same time, the granularity of agents and plans are changing dynami­ cally. Also agents are heterogeneous. Although contrac_t­ net type organization schemes are usually preferable m open distributed environments because of their dynamic nature a multiagent system embodies additional com­ plexit; which makes application of the contract-net dif­ ficult.

Two such problems in the contract-net occur in de­ composition and task allocation. When the requestor first decomposes the task, its fixed decomposition of the task may not suit the open distributed environment. Not only may it not know what agents are currently available, but it also may not know the changing skills of poten­ tial requestees. The requestor then selects one agent per subtask through negotiation, and allocates the subtask to that agent. No single agent may have a plan to achieve the subtask alone. Even though subcontracting is pos­ sible, this fixed task allocation strategy, which assigns a subtask to only one agent, may result in an ineffective hierarchy of subcontracts. .

If we apply the contract-net protocol to hierarchical multiagent planning, the problems become more seri­ ous. The requestor wants some agent to accomplish a goal, but if it does not have sufficient knowle~ge _to de­ compose a complex goal properly in an open dtstnbuted environment, it cannot ask any single agent to achieve the goal. Its task allocation strategy fails. Therefore, we need a more flexible strategy for selecting requestees.

Suppose that the requestor can somehow select sev­ eral agents as collaborative requestees. This raises some questions. What information should the requestor pro­ vide to those requestees? In other words, what informa­ tion is necessary for the requestees to mutually construct collaborative plans? Also, how should the mutual plan construction be coordinated and organized?

The scheme proposed in [Osawa and Tokoro 92] is designed to provide flexible decomposition of goals, availability-based assignment of goals to agents, and op­ portunistic collaboration to distributed planning par­ tially based on the contract net proposed by Davis and Smith [Davis and Smith 83]. These features of the scheme are designed to cope with uncertainty and the dynamic nature of open multiagent environments.

In the collaborative plan scheme, an agent who needs help dynamically organizes a. group. The agent first announces a. request for proposals (RFP) by sending a message to a bulletin board agent. Agents who read the RFP and can construct an individual plan for the request, even if incomplete, send their individual plans to the originating agent, hereafter referred to as the re­ questor. The requestor then investigates possible col­ laboration among potential requestees. If collaboration seems possible, the requestor gives collaborative awards, along with suggestions for collaboration, to the reques­ tees. A suggestion for collaboration given to a reques­ tee agent contains: ( 1) Explicit obstacles of the other collaborating agents which the agent may possibly re­ solve; (2) Actions which collaborating agents may per­ form. The suggestions set up a partial model for pre­ dicting the other agent's actions. Using these sugges­ tions, along with its initial individual plan and beliefs, each collaborating agent constructs a collaborative plan through inference. In collaborative plan construction, each agent decides on the actions it should perform, the actions the other agents would perform, and the actions both agents will achieve jointly. In the process, each agent takes three factors into account: the elimination of obstacles of other agents, balancing of the workload among agents, and cost effectiveness. This whole process can be summarized as follows.

1. Requestor sends a request for proposal (RFP) to the bulletin board agent
2. Free agents 1 request the bulletin board to provide a stored RFP
3. Bulletin board sends RFP to requesting free agents
4. Free agents generate individual plans
5. Free agents send individual plans, if any, to the re­ questor
6. Requestor investigates the possibility of collabora­ tion (computes suggestions for collaboration)
7. Requestor sends collaborative awards to requestees (out of free agents)
8. Requestees construct collaborative plans

3 Individual Planning of Rational Agent

In this section, we present a model for individual plan generation by rational agents. In the model, the beliefs of an agent at time t are modeled by a first-order ax­ iomatic system, which is called a world. Operators are represented by a transition from one world to another. Therefore, a plan can be viewed as a chain of operators which connect several worlds. This model is based on the Multi- World Model [Nagao 93].

3.1 Belief Model of Agent

Definition 1 (Belief) The set of beliefs of agent a at time t, w~, is a first-order axiomatic system.

Definition 2 (Entailment) w~ 1- p means that world w~ entails proposition p.

1 A free agent is one without a current task.

1- is used for entailment from a single world. Later, we introduce entailment based on consistent inheritance of propositions from previous worlds, which is called en­ tailment with consistent inheritance.

3.2 Operator

Each agent maintains a library of operators that it may execute. Operators in the library are generic functions that are represented in the following form:

where pre1, · · · ,pren (ef fi, · · ·, ef fm) are propositions that hold before (after) the operator is executed. Pre­ conditions and effects are sometimes written as preconds and effects. Also, each operator is associated with a tem­ poral variable T, and an execution time cost T which is the expected cost of the operator. The cost of the oper­ ator is predicted from an agent's working environment.

The arguments of an operator in the library, Agent, Parameters, T, preconds, and effects, are instantiated when the operator is invoked.

The functions agt,pars, time, cost, pre, and ef f, which are used in the following definitions, are functions that take an instantiated operator and return its respec­ tive argument, agent, parameters, t, T, preconds, and ef­ fects.

Operators are defined as follows.

Definition 3 (Operator (definition attempt)) Operator op of agent a is a transition from world w~ to world w~+r, if and only if worlds w~ and w~+r satisfy the following.

3.3 Abduction

Abduction is a special kind of transition between worlds. An operation that translates a world into another world by introducing an hypothesis p (p is atomic) is called abduction.

Definition 4 (Abduction) Abduction ab(a,p, t, a) of agent a is a transition from world w~ to world w~+u, which entails proposition p.

The difference between an operator and an abduc­ tion is that the former is obtained by instantiating some generic function in the library, while the latter is not lim­ ited in that way. Abduction is used to introduce unsatis­ fied operator proposition preconds into a world 2 · These resulting propositions are called hypotheses. The hy­ pothesis introduced by abduction is associated with its cost, since the hypothesis will be achieved by executing some operator. The semantics of the cost will be dis­ cussed in Subsection 3.6 of this section.

2 If we allow abduction, an agent may introduce arbitrary hypotheses, some of which might be irrelevant to the agent's goal. In order to avoid abducting these irrelevant hypotheses, agents need to have a control strategy for abduction. This is done based on the cost of subplans, including abducted hypotheses, computed dynamically in the course of planning. With the cost, agents are able to calculate the utility of the goal. The details of this are discussed in Subsection 3.6

3.4 Operator Sequence

A transition from one world to another by way of a chain of operators and abductions is called an operator sequence.

Definition 5 (Operator Sequence) An Operator se­ quence [xi ]( i=l,-··,nl that translates world w~ into world w~ is called an operator sequence and is represented by w~ ===> w~.

Now, we define entailment with consistent inheritance and extend the definition of the operator. In the previ­ ous definition of the operator, the preconds .of the opera­ tor are restricted to be solely entailed from the world in which the operator will be applied. However, if there is a chain of several worlds which a.re connected through a sequence of operators, not only the world in which the operator will be applied, but. also some previous world in the chain, will entail a proposition in preconds. There­ fore, we need to extend the definition of operators. For that purpose, we first define entailment with consistent inheritance. This inference rule is analogous to the de­ fault rules in nonmonotonic reasoning [Reiter 80].

Definition 6 (Entailment with Consistent Inher­ itance) Proposition p is entailed from world w~ with consistent inheritance, w~ 11- p, if and only if

where there is some operator sequence w~' ===> w~, ex­ cept in the case where world w~ is identical to world w~. Also, w~' is a world which exists in the chain of worlds linking w~ and w~.

With this definition, we redefine the operators.

Definition 7 (Operator) Operator op of agent a is a transition from world w~ to another world w~+.,., and satisfies the following condition.

3.5 Plan

Definition 8 (Goal) Goal g of agent a is a set of first­ order atomic formulae that agent a wants to satisfy.

Definition 9 (Plan) Let w~ 0 be the initial beliefs of agent a, and g be the goal of agent a. The plan of agent a that satisfies goal g, plan( a, g), is the sequence of op­ erators that satisfies the following condition.

Definition 10 (Incomplete Plan) Let plan(a,g)(= [xi](i=l,-··,n)) be a plan that satisfies goal g of agent a. If at least one Xi is abduction, plan( a, g) is called an incomplete plan.

Let I denote a unary predicate over plans that is true if and only if its argument is incomplete.

In general, there can be several plans, including in­ complete ones, that satisfy goal g of agent a. Let PLAN (a, g) denote the set of these plans.

3.6 Cost, Worth, and Utility

We will now define the cost of plans, worth of goals, and utility of goals.

Definition 11 (Cost of Plan) The

cost of plan plan(a,g)(= [xi](i=l,···,n)), cost(plan(g)), is calculated as follows:

where cost(xi) is the cost of operator x;. If Xi IS an abduction, cost(xi) is the abduction cost.

Now, we more precisely characterize the abduction cost. Individual plans in the collaborative planning scheme can be incomplete [Osawa and Tokoro 92]. As we stated above, an incomplete plan is a plan which in­ cludes hypotheses introduced by abduction. The cost of hypothesis can be viewed as the maximum expected cost that the agent will pay to satisfy the proposition. In other words, the cost of abducted hypothesis for agent a can be viewed as the worth. of p for agent a. Worth can be given to any goal as well as any hypothesis.

Definition 12 (Worth of Goal) The worth of a goal for an agent is the maximum expected cost that the agent will pay to satisfy the goal3. Function worth. is a binary function over agents and goals (or hypotheses) that des­ ignates the worth of the goal (or hypotheses) for the agent.

If we know the worth of a goal, we can define the utility of the goal.

Definition 13 (Utility of Goal) The utility of goal g for agent a is calculated by the following formula.

3. 7 Best Plan

Definition 14 (Best plan) The plan in PLAN(a,g) that has the minimal cost is called the best plan for goal g of agent a.

Definition 15 (Rational agent) Rational agent a chooses the best plan out of PLAN (a, g) for goal g as long as the utility of the goal is positive. If there is no best plan, rational agents abandon trying to achieve the goal.

If a rational agent is asked to propose a plan for the goal, it will choose the best plan, and propose it as its own individual plan.

(Example) We will use the following example through­ out this paper (see figure 1). The goal in this example is for agent a3 to have block bin room r3. We assume that agent a3 knows that by performing trans( Agent, a3 , b), it can hold block b. However, since some parts of the precondition of the action, i.e. (holding( Agent, b) 1\ in(Agent,r3)), don't hold at this moment, it needs to ask other agents to achieve this goal, conditioned by the fact that block b is not in room r 3 at this moment. There­ fore, the agent sends a RFP, which includes asking 9ex

3 This view of worth is discussed in [Zlotkin and Rosen­ schein 89). We generally follow their idea. Also, we assume that such an upper bound exists.

= (holding( Agent, b) 1\ in( Agent, r 3)) to be satisfied, to the bulletin board agent.

We assume that agent a1 believes that agent a1 and block b are in room r 1, and room r1 and r2 are adjacent, and the door between these two rooms, namely d12 , is open, and door d23 is closed. Also, we assume that agent a1 can execute oper­ ations pickup(a1, Object) , move(a1 , Object, From, To), and trans( a1, Object, Recipient).

Suppose agent a1 sends a request to the bulletin board agent, and receives the RFP. One possible plan agent a1 may generate is [pickup(a1,b), move(a1,b,rl,r2), open(door23), move(a1 , b,r2 , r3)], where terms in italics indicate hypotheses introduced by abduction.

This plan is incomplete, since it includes hypothesis open(door23) which is introduced by abduction. The hypothesis is a part of the preconditions of operator move(a1,b,r2,r3)

4 Investigating and A warding Collaboration

In this section, we formalize the process of investigat­ ing the possibility of collaboration among possible con­ tractors described in Section 2. Throughout this sec­ tion, we assume that for goal g of the requesting agent several bid plans plan( a;, g) are proposed. The set of proposed individual plans for goal g is denoted as PPLAN(g)(= {plan(a;,g)}).

4.1 Filter

In collaborative planning, the requesting agent wants to choose the best plan, or best collaborative plan, out of PPLAN(g). However if PPLAN(g) includes many individual plans, the computational cost of choosing a plan may cause combinatorial explosion. Therefore, it is preferable to select promising plans from P P LAN(g ). Plan filter, defined below, provides the mean to do this. Definition 16 (Plan Filter) Plan filter filter is a bi­ nary function over a set of plans P and a unary predicate n that designates a subset of P , each of which satisfies

predicate n.

With this filter, requesting agent a first chooses the set of plans out of PPLAN(g) whose costs are lower than agent a's worth for goal g. The subset, FPLAN(g), is obtained as follows:

where leq(X, Y) - X :::; Y.

Let CFPLAN(g) be the set of complete plans in FPLAN(g).

4.2 Investigating he Possibility of . Collaboration

Definition 17 (Collaborative Plan) Let w! 0 be the initial belief of requesting agent a, and g be the goal that the agent requires to be satisfied. Collaborative plan (plan(ai,g);plan(aj,g)) lc of two agents ai,aj('i ::/= j) for goal g is defined as follows.

where plan(ai,g),plan(aj,g) E PPLAN(g) and c rep­ resents a partial order of operators in plan ( ai, g) and plan(aj,g).

Let CP LAN(g) denote the set of collaborative plans, both of which belong to PPLAN(g). Also, let CC P LAN(g) denote the set of complete collaborative plans in CPLAN(g).

4.3 Selecting the Best Plan

Requesting agent a selects the best individual plan or the best collaborative plan by means of the following procedure.

If FPLAN(g) = </> then return null plan else if CCPLAN U CFPLAN ::/= <P then return p, s.t. cost(p) = min cost(q) qECCPLANUCFPLAN else return p, s.t. cost(p) = min cost(q) qECPLANUFPLAN

4.4 Requesting Collaboration (Collaborative Award)

If the best plan is the null plan, agent a abandon trying to achieve goal g. If it is a single individ­ ual plan plan(ai,g), agent a requests ai to execute plan(ai, g). If the best plan is a collaborative plan (plan(ai,g);plan(aj,g)) lc, agent a requests two agents, ai and aj, to collaborate with each other. This is called a collaborative award. In this case, agent a informs both ai and aj of the collaborative plan (plan(ai,g);plan(aj,g)) lc as collaborative awards.

(Example) Looking back at the example given in the previous section, suppose three agents a1, a2, and a4 4 propose the following plans plan( a1, gex), plan( a2, gex), plan( a4, gex), respectively, for gex = (holding( Agent, b), in( Agent, r 3)) (agents a2 and a4 don't know the location of block b) . We also assume that the worth of gex for agent a3 is equal to 7, and the cost of all operators and the worth of all hypotheses in the following plans are equal to 1, for simplicity.

4 Although agent a4 doesn't appear in the previous exam­ ple, we assume the existence of the agent for convenience.

plan( a!, gex) = [pickup( a1, b ),move(a1. b. r1, r2 ), open(door23),move(a1, b, r2. r3)] plan(a2, Yex) = (open(a2, door23 ),move(a2 , nil, r2, ri), onfloor(b, r 1 ),pickup(a2, b), move(a2, b, r 1, r2),move(a2. b, r2, r3)] plan(a4, gex) = (open(a4 , door23 ),holding(Agent, b), ·in( Agent, r3 ),trans(b, Agent, a4), . move(a4, b, r 1, r2 ),move(a4, b, r2, r3 )]

After reception of all of these plans, agent a3 needs to select the best plan(s). In this case, F PLAN, CPLAN, CCPLAN, and CFPLAN are given as follows.

F PLAN = {plan( a1, gex), plan( a2, gex), plan( a4, gex)} CPLAN = {(plan(al,Yex);plan(a2,gex)) lc 1 J CCPLAN = {(plan(al,gex);plan(a2,gex)) lc 12 } CFPLAN = </>

Therefore, agent a3 selects collaborative plan (plan(al,Yex);plan(a2,gex)) lc 12 , according to the procedure described in Subsection 4.3.

5 Rational Choice of Subplans from Individual Plan in Collaboration

Au agent who is given a collaborative award tries to construct its contribution according to the collabora­ tive plan by refining the individual plan which it pro­ posed. The refinement mainly consists of choosing sub­ plans from the individual plan. A formal model of ra­ tional decision with which agents can effectively choose their actions is presented in this section. We first define two meta-operations, hypothesize and commit, on opera­ tors in plans. Second, we show criteria with which agents decide what actions they will execute. With these meta­ operations and criteria, we finally present how agents rationally choose their actions in collaborative planning.

5.1 Hypothesizing and Committing

We define two operations, hypothesize and commit, which are utilized in collaborative planning.

Definition 18 (Hypothesizing)

Operation hypothes·ize takes operator op (w! --+ w!+r) and makes it an abduction ab with zero cost.

Suppose a certain operator is included in both individ­ uals' plans. If one of the collaborating agents executes the operator, the other agent can view the cost of the operator as zero.

Definition 19 (Committing) The commit operation (commit( a, op)) commits agent a to execute operation op.

Committing will be applied to an operator which sup­ ports a hypothesis of the other collaborating agents. Op­ erators which are committed cannot be hypothesized.

5.2 Criteria for Choosing Actions from Individual Plan

The following two criteria are taken into account when agents choose actions from their initial individual plans.

• Obstacle detection and elimination: Hypothe­ ses included in individual plans can be regarded as explicit obstacles to the agent's plan, since they can

be unsatisfied preconditions of a certain operator. The subplan of the other collaborating agent, which achieves the hypotheses, needs to be chosen by the agent. If the subplan is not chosen, the hypothe­ ses remain unsatisfied, and the overall collaborative plan remains incomplete. If the collaborative plan is incomplete, a new collaborative plan is formed among agents using the the same protocol. The goal of this plan is the unsatisfied hypotheses of the first collaborative plan, in other words other agents help to complete the first plan. Since this entire process can be expensive, it would be better for the collaborating agent, whose subplan supports the hy­ potheses of the other agent, to choose the su bplan to be executed. The choice can be regarded as ob.~tacle elimination.

• Workload balancing: Each collaborating agent estimates the worth of the goal which collaborating agents are trying to achieve. Collaborating agents are willing to expend effort to achieve the goal, however the effort should not exceed the worth of the goal for the particular agent. Therefore, the workload of each collaborating agent should be bal­ anced according to the utility which each agent will gain from the achievement of the goal. This should be done based on the utility equalization principle, which is defined below.

[Utility Equalization Principle] In collaboration among agents, the utility which each agent will gain from the collaborative goal should be as equal as possible.

To make this principle operational, collaborating agents need to know the worth of the goal to the partner. In the following discussion, we assume that the worth of the goal for each agent, worth(a2,g) and worth(a1,g), are known to both collaborating agents, a1 and a2.

5.3 Choosing Actions from Individual Plan

We describe how the collaborating agents choose opera­ tors from their initial individual plans. In the following description, agent a1 's choice is described. The choice process of agent a2 is identical. We assume that the col­ laborating plan is denoted as (plan( a1, g); plan( a2, g)) I c. and each plan pl"an(a1,g) = [xni=1.-··,nl·Plan(a2,g) = [x~](j=l ,···,m)·

Agent a1 's choice of operators from its initial individ­ ual plan is· done through the following two steps:

1. Committing operators that support the hypotheses of the other agents
2. 2 .. Identifying interchangeable subplans (defined below) and making choices (committing) .

Definition 20 (Interchangeable Plans) Two plans l l (. t t') [ l ( t' t" Xi (i;:::l,···,n) w ===? w and Yi (i=l,.···,m) w ===? w ) are said to be interchangeable, if and only if wt' = wt" and pre( xi) = pre(yt).

Let I./liT denote a binary predicate over operators that is true if and only if its arguments are iuterchauge­ a:l'>le plans.

(Example). For the following collaborative plans given in the previou::; example,

interchangeable subplaus are [pickup( a1 , b), move( a1, b, r1, r2), move( at. b, r2, r 3 )] and [pickup( a2, b), move(a2 , b, r1, r2 ), move( n2, b, r2, ra )].

5.3.1 Committing Operators

Let ABV denote a unary predicate over operators that is true if and only if its argument is au abduction.

Operators in plan [xt ](i=l ... ·,nl which support a2 's hy­ potheses are committed according to the following pro­ cedure.

(Example) For plan(n1, g · .,) and plan(~ , g · .,), since the effect of operator open(a2,door23) in plan(a2,g · .,) in­ cludes hypothesis open( door23) in plan( a1, g · .,) , agent a2 commits itself to execute operator open(door23).

5.3.2 Choice of Subplans

Let CMT denote a unary predicate over operators that is true if and only if its argument contains com­ mitted operators.

Agent a1 's choice of subplaus from its initial individual plan is done according to the following procedure:

1. From the last operators in plans [xt ](i=l , .. ·,n) and [x]J(j=l ... ·,m), identify all the subplans YL ( C [x;](i=l, .. ·,n)) and y~(C [x]J(j=l , .. ·,m)) which satisfy I.NT(yL,y~ ). The identified subplans of one agent are not allowed to have shared operators. (We as­ sume that the number of these interchangeable op­ erators is N)
2. For all YL(k = 1, · · ·, N), evaluate the utility equal­ ization condition defined below. If the condition is satisfied, commit all the operators in subplan YL· Otherwise, apply the hypothes·ize operation to all operators in YL that are not committed (CMT(yt) is not true). The hypothesized oper­ ators are supported by the subplan of the other collaborating agent, y~. If CMT(yt) is true, then all operators preceding the last committed opera­ tor are committed. The remaining operators are hypothesized.
3. Agent a1 chooses all the committed operators in [x;](i=l , .. ·,nY

[Utility Equalization Condition]

where if an committed operator is included in Yl ( or y~), the cost of the operator is omitted in the calculation of the cost of yl{or y~)-

(Example) Assume that worth( a1, 9ex) = 6 and worth(a2,9ex) = 6. For plan(a1,9ex) and plan(a2,9exl. the first interchangeable plans are [pickup(a1,b), move(a1, b, r1, r2), move(a1. b, r2, r3 )] and [pickup( a2, b), move( a2, b, r1, r2), move( a2, b, r2, r3) ]. Since agent a2 has already committed itself to operator open( a2, door23) in plan(a2,9ez), the current utility of agent a2 is equal to 5 (= 6-1). Meanwhile, the current utility of agent a1 is equal to 6, since agent a1 has not committed it­ self to any operator. Therefore, agent a1 commits it­ self to execute sub plan [pickup(a1, b), move(a1, b, r1 , r2 ), move(a1, b, r 2, r3)] by means of evaluating the utility equalization condition. On the other hand, agent a2 hypothesizes operators pickup( a2, b ),move(a2, b, r1, r2 ), and move( a2 , b, r2, r3). No other interchangeable sub­ plans remain, and agent a2 hypothesizes operator move(a2, nil, r2, r1 ). As a result, the following two plans, plan( a1, 9ez )' and plan( a2, 9ex )', which are sequences of committed operators, are obtained.

With an appropriate temporal ordering (schedule) c12, these two plans form a complete collaborative plan.

5.3.3 Condition for Incomplete Collaborative plan

All the committed operators with a partial order in the collaborative award form the collaborative plan for goal g. The collaborative plan is represented in the fol­ lowing form.

If either or [x] I CMT(x])J(j=l,. ··,m) contains any hypotheses that are not supported by operators in the collaborative plan, the resulting collaborative plan is incomplete. The plan can be made complete by forming another collabora­ tive group with agents who have the skills necessary to achieve the hypotheses. This is accomplished by reapply­ ing the collaborative plan scheme, using the hypotheses as goals.

6 Concluding Remarks and Future Work

We have presented a formal model for generating col­ laborative plans from, possibley incomplete, individual plans in multiagent domains. Also, we have developed a utility-based model of rational choice with which agents can rationally decide which actions will be performed by each agent in a collaborative plan. Given a goal, a rational agent generates the best plan with respect to its utility, which is calculated by subtracting the cost of the plan from the worth of the goal for that agent. The choice of activities in collaboration is guided by two criteria; ( 1) the maximum completeness (obstacle detection and elimination), and (2) the utility equalization prin­ ciple. If the resulting collaborative plan still contains an unsupported hypothesis, the plan is incomplete. The plan can be made complete by forming another collabo­ rative group with agents who have the skills necessary to achieve the hypotheses, using the hypotheses as goals.

We are currently working on the following extensions: ( 1) Implementing the proposed scheme; (2) Theoretical analysis on computational complexity of the collabora­ tion scheme; (3) Incorporating a learning capability into agents, so that successful collaboration can be reutilized again without the overhead of organizing a group.