Minimally intrusive negotiating agents for resource sharing

1 Introduction

Negotiation of resources is an important research area in multi-agent systems. In general, agents may negotiate to ob­ tain resources that they are missing but that are necessary to carry out their plans. In this paper, we assume that negotiation for resources takes place within the framework of [Sadri et al., 2002], where the knowledge of the agents is represented as a tuple< B, R,I, D, g >with B: beliefs about the world, the self and the other agents, as well as the negotiation poli­ cies ofthe agent; R: initially owned resources; I: intentions, i.e., the plans 1 that the agent intends to carry out, in order to achieve its goals, together with the resources required for that plan; D: store of past dialogues; and 9: agent goals.

We extend [Sadri et al., 2002] to negotiate not just re­ sources, but also time windows during which resources can be used by agents, thus allowing for sharing of (non­ consumable) resources over time, The extended framework allows solutions for a wider range of resource re-allocation problems. In the extended framework, agent intentions are

*This work is partially funded by theIST programme of the Eu­ ropean Commission under the IST-2001-32530 SOCS project.

1 It is beyond the scope of this paper to provide a general and exhaustive representation of the agent knowledge. Instead, we con­ centrate on those elements relevant to the resource sharing problem. In particular, for simplicity, we identify here intentions with plans.

Paolo Torroni

DEIS

University of Bologna V.le Risorgimento, 2 40136 Bologna, Italy ptorroni@deis.unibo.i t

sets of activities. Drawing inspiration from [EI Sakkout and Wallace, 2000], we model an activity a (a is a unique identi­ fier) as a tuple < a, Ra, Da, Tsa , T ea > denoting that are­ quires resource Ra, has duration Da, earliest start time Tsa, latest end time T ea. Note that, without loss of generality, we assume that each activity requires only one resource 2 . In the extended framework, the knowledge of agents includes a (possibly empty) concrete schedule i for activities, where if < a, t 8 , te >E i then< a, R , D, T sa, Tea >E I, such that te - ts = D, ts ~ Tsa, and te :::; T ea.

We develop negotiation protocols and policies that allow agents to exchange resources and strike deals for agreed time windows. We introduce a multi-stage process of negotiation, each characterised by a protocol and a policy. A higher stage involves more information passing between agents and more sophisticated negotiation, possibly including re-planning by the agents aimed at trying to help satisfy each other's con­ straints and requirements. The following example illustrates the sort of problems and solutions we propose in this paper. Example 1 Let x andy be two agents. x's intentions contain an activity a requiring a resource r, < a, r, 3, 1, 5 >E Ix. y's intentions contain an activity b also requiring r. x owns r from time I to 3 and from time 5 onwards, and y owns r from time 3 to 5. x needs r for three consecutive time slots between I and 5, but it currently owns r for only two time slots. Let us consider the three scenarios below.

1. < b, r, 1, 4, 10 >E Iy . The problem is solved by y agreeing to giver to x for [3, 4].
2. < b, r, 1, 3, 10 >E Iy and y has a concrete schedule Iy = < b, 3, 4 > forb to be carried out between 3 and 4. The problem is solved by y agreeing to postpone its schedule by 1 time slot and giving r to x for [3, 4].
3. < b, r, 2, 3,10 >E Iy . y cannot giver away, because otherwise b becomes unfeasible. The problem can be solved by an exchange: y agrees to give r away to x for [3, 4], in return for x giving r toy for [5, 6]. 0

2 Background and Preliminaries

In this section we review and adapt some concepts from back­ ground papers, needed in the rest of the paper.

2 Indeed, it is possible to model any activity requiring multiple resources by a number of activities, one for each resource, with the same duration and times.

Definition 1 An agent system is a finite setS, with at least two elements, where each x E Sis a ground term, represent­ ing the name of an agent. All elements of S are distinct (agent names must be uniquely identifiable). Each agent x E S is equipped at each timeT E N with a knowledge base Kx ,r' namely a tuple< Bx , Rx,Ix, Dx,n 9x,Ix,r >,as explained in the introduction.

Note that, in this paper, we assume that the only parts of the knowledge base of an agent that change over time are the dialogue store, which grows in time, and the concrete sched­ ule. We will also assume that, in Ix, all activities that require the same resource have disjoint time windows. In the sequel, when clear from the context, we will sometimes refer to the knowledge base of an agent x simply as Kx or K.

Definition 2 Let S be an agent system. Let Res be a set of resources. 3 Let Res x N x N ----+ S be the resource allocation in the system at time T (this can be determined, for example, from n and D of all agents at time T). The allocation of resources is defined for time periods [T8 , TeJ, Ts ~ 0, Te :::; T max, where T max is the maximum schedul­ ing time, defined as follows:

The negotiation process we will define modifies the re­ source distribution in the agent system through time. The Temporal Resource Reallocation Problem (T-RRP) is the problem of answering to the following question: Does there exist a time T during the negotiation process when the re­ source distribution is such that each agent has the resources it requires for time periods that would allow it to perform the ac­ tivities in its intention, within their specified time windows?

The purpose of this work is to show how it is possible to find a solution to the T-RRP (when one exists) by using agents that negotiate by means of dialogues. We will assume that all agents in a system share the same communication language, in terms of syntax, semantics, ontology, and pragmatics. We refer to [Sadri et al., 2002] for a formal definition of a lan­ guage for negotiation. In brief, a language defines the set of allowed dialogue moves. Each dialogue move is coded into a tell predicate, which has 5 arguments: sender, receiver, con­ tent, dialogue identifier, and time of the move. We will use the communication language .C1-TW, defined below:

Definition 3 .C1-TW = {

tell(X, Y, Content, D, T) I Content E

• { (1) request(give(R, (Ts, Te)))
• accept(request(give(R, (Ts, Te))))
• refuse(request(give(R, (Ts, Te))))
• promise(R, (Ts, Te), (Ts', Te'))
• change(promise(R, (Ts, Te), (Ts', Te')))
• accept(promise(R, (Ts, Te), (Ts', Te'))) } } where Ts, Teare positive integers between 0 and Tmax, for all dialogue moves, Ts < Te, and for (4)-(6), Ts' < Te'.

The first three moves are of intuitive meaning. (4) is used by X to propose a deal (promise): X will give R to Y for the interval [Ts', Te'] if Y will giveR to X for the interval [Ts, Te]. (5) is used to refuse a proposed deal and ask for a new one (there is no refuse_promise move which only termi­ nates a protocol), (6) is used to accept a deal.

3 Without Joss of generality, we assume that all resources in the system are non-consumable (for resource reallocation, consumable resources differ from non-consumable ones in that the former can be allocated only for maximal intervals (0, T max ], and not for any sub-intervals, where T m ax is given below in the definition).

Given a language for negotiation .C, we define the set of final moves :F(.C). In particular, :F(.C1-rw) is the subset of .C1-rw that contains all the moves whose content is (2), (3) or (6).

Dialogues can be generated by means of policies, held by the knowledge base of the agents.

Definition 4 Policies are expressed as dialogue constraints of the form Pi 1\ C => Pi+ 1, where Pi and Pi+ 1 are moves. The conditions C are to be evaluated in the knowledge base of the agent or in extensions to it. The intended use of these policies is that if the agent receives a move Pi, and the conditions C are satisfied in its knowledge base, the agent generates Pi+l· An operational model for policies is defined in [Sadri et al., 2002].

Definition 5 Given an agent system S equipped with a lan­ guage for negotiation .C and two agents X and Y in S equipped with policy Pol, a dialogue induced by Pol be­ tween X and Y is a set of ground dialogue moves in .C, {po,p1,p2, . . . }, such that, for a given set of time lapses 0 :::; To < T1 < T2 < ... :

1. Vi ~ 0, Pi is uttered at time Ti;
2. Vi ~ 0, if Pi is uttered by agent X (viz. Y), then Pi+l (if any) is uttered by agent Y (viz. X);
3. V i > 0, Pi can be uttered by agent U E {X, Y} only if there exists a (grounded) dialogue constraint in Pol, Pi-11\ C =>Pi s.t. Ku,r;_, 1\Pi-1 f- C;
4. there is an identifier D such that, V i ~ 0, the dialogue identifier of Pi is D;
5. 'VT, Ti-l < T < Ti, Vi > 0 s.t. Pi and Pi-1 belong to the dialogue, there exist no moves at T with either X or Y being either the receiver or the utterer.

A dialogue {Po, p1, ... Pm}, m ~ 0, is terminated if Pm is a ground final move, namely Pm is a ground instance of a move in :F(.C). We say that such a terminated dialogue starts at time To and ends at time T m.

Note that this definition prevents agents from being in­ volved in more than one dialogue at a time (e.g., dialogues cannot be nested).

An important property of policies used to induce dialogues as in Definition 5 is conformance to protocols, known to all agents involved in the dialogue. A dialogue protocol can be defined as a set of states, representing the current state of dia­ logue, a set of allowed dialogue moves, and a set of transition rules that, given a state and a move, produce a state. A pro­ tocol is therefore defined as a finite state machine, consisting of states and arcs, which has among its states an initial state So, two final states, SF-s (successful termination) and SF-u (unsuccessful termination), and possibly a number of inter­ mediate states Si. The arcs can be viewed as allowed transi­ tions mapping one state to another given a label. These labels correspond to the content of moves. An example of protocol is in Fig. 1. When we show the protocols, we use some ab­ breviations, such as for instance:

request for request(give(R, (Ts, Te))), refuseJeq for refuse(request(give(R, (Ts, Te)))).

In order to define the concept of conformance, we define dialogues in relation with protocols.

Definition 6 Given an agent system S equipped with a lan­ guage for negotiation £, and a protocol P, a dialogue con­ forming toP, between two agents X andY inS, is a set of ground dialogue moves in£, {po,PI.P2, .. . }, such that, for a given set of time lapses 0 ~ To < T1 < T2 < ... :

1. 2. 4. 5. as for Definition 5;
2. the content of Po must label an arc from So. Vi, if the content of Pi is the label of an arc into a final state, then there is no Pi+1 in the dialogue. V i, the contents of Pi and Pi+l, if they both exist, must be labels, respectively, of an arc going into a state, and an arc coming out of the same state.

A dialogue {Po, P1, ... Pm}, m 2: 0, is terminated if Pm is the label of an arc into a final state.

We are now ready to define the concept of conformance of policies to protocols.

Definition 7 Given a policy Pol and a protocol P, Pol con­ forms to P if every dialogue induced by Pol is a dialogue conforming to P.

We define sequences of dialogues for a resource R and an activity A, between two agents X andY.

Definition 8 Given an agent system S, a sequence of dia­ logues a between two agents X and Y in S for a resource R and an activity A is a set of terminated dialogues between X andY, a= {do, d1, d2, .. . }, where dj = {Pjo,Pj1, ... , Pjn} for all j, such that, for a given set of time lapses 0 ~ To < T1 < T2 < ... :

1. Vi 2: 0, di is initiated by X at time Ti, and it is termi­ nated at a time Tf < Ti+ 1 ;
2. ~i, j, i =I= j such that Pio = Pjo;
3. Vi, if di and di+1 are in a, then di = {piO, ... ,Pin} and Pin = tell(Y, X, refuse( request( give(R, (Ts, Te) ))), di , T) for some Ts , Te, T;
4. 3 < A, R, D, TS, TE >E Ix such that Vi Pio = tell(X, Y, request( give(R, (Ts, Te) )), di, Ti)) for some Ts, Te such that Ts 2: TS and Te ~ TE;
5. If a is finite, i.e. a = do, . .. , d f for some f 2: 0, then d1 = {PJo, ... ,PJn}. the last dialogue in these­ quence, is such that for some T, T8 , Te, T~ , T~, P!n = tell(Y,X, accept( request( give(R, (Ts, Te) ))), df, T) or P!n = tell(Y,X,accept( promise(R, (Ts,Te), (Ts', Te') )), df, T) .

We assume the atomicity of sequences of dialogues: agents will not react to any incoming request about a resource r if they are participating in an ongoing sequence of dialogues regarding r, and moreover they themselves will not make a request for r with respect to another activity while they are participating in an ongoing sequence of dialogues which they initiated (an agent cycle very similar to the one in [Sadri et al., 2002] will achieve this atomicity).

3 Negotiation Stages

We define two different stages of negotiation, each character­ ized by the degree of flexibility of the agents and the amount of information disclosed and used by them:

Stage 1: Request/flexible schedule

Stage 2: Blind deal

In this section, for each stage we define the protocol, the policies adopted by the agents, and the properties of the stage. The properties that we study are ( i) conformance of the policy to the protocol, ( ii) properties of single dialogues (termina­ tion and characterization of the class of problems that can be solved), (iii) properties of sequences of dialogues happening at that stage, and ( iv) subsumption of earlier stages (in terms of solvable problems). In particular, for each stage we give an example of a problem that can be solved within it, and an example of a problem that cannot.

In defining the policies and in stating the results, we rely upon some predicates, whose formal definition is given in ap­ pendix. We use the notation Kx ,T f- p to indicate that at time T the knowledge of X entails a certain predicate p. The proofs of the results are omitted for lack of space.

3.1 Stage 1 - request/flexible schedule

Protocol. The protocol is given in Figure 1.

Policy. The policy is shown in Figure 2: an agent will accept a request for R if it can find a concrete schedule of its own activities that does not make use of R during the requested interval. It will refuse it otherwise, leading to an unsuccessful final state. Note that it is up to the requesting agent to find good heuristics to formulate a request or a series of requests which can be accepted.

Example 2 Let us consider the following example:

There is no solution if y sticks to Iy: but if y was happy with a different schedule, e.g. i~ = { < a, 15,20 >},then x and y could both do their activities by sharing resource r. Thus, this example can be solved by the following negotiation dialogue d(1) occurring at Stage 1 (i.e., induced by the policy ofFig. 2):

Properties. Stage 1 is computationally demanding for the agent who is replying to a request. The problems that can be solved at this stage are all those that can be solved by means of a (possibly empty) modification in the agents' current concrete schedule.

( i): protocol conformance. It is possible to prove that the policy of Stage 1 is conforming to the protocol in Fig. 1.

( ii): properties of single dialogues. A request/flexible sched­ ule interaction enjoys the property of termination. In fact, di­ alogues following this protocol have a fixed number of steps. Theorem 1 Let us consider a system composed of two agents, x andy. Then, for all system resources r, all activities

(IC.1) tell( X, y , request(give(R, (Ts, T e))), D, T) 1\ have(R, (Ts, Te), T) 1\--, need(R, (Ts, Te), T) =? 3 T' I tell(y, X, accept(request(give(R, (Ts, Te)))), D, T') 1\ T < T' (IC.2) tell( X, y , request(give(R, (Ts, T e))), D , T) 1\ have(R, (Ts, Te), T) 1\ need(R, (Ts , Te), T) =? 3 T' I tell(y, X, refuse(request(give(R, (Ts, Te)))), D, T') 1\ T < T' (IC.3) tell(X, y, request(give(R, (Ts , T e))), D , T) 1\ --, have(R, (Ts, Te), T) =? 3 T' I tell(y, X, refuse(request(give(R, (Ts, Te)))), D, T') 1\ T < T'

a assigned to x, all times T, and all intervals [Ts, Te] s.t.

Kx,r f- miss(r, (Ts, T e), a) 1\

Ky ,r f- avail(r, (Ts, Te)),

there exists a dialogue d induced by the policy of Stage 1, starting at time T, and ending at time T 1 , such that

Ky,r' f- indiff(r, (Ts , T e)) . Intuitively this theorem states that if there exists a time window tw such that an agent x needs r in it and another agent has r available in tw, then there also exists a dialogue induced by the policy of Stage l which solves x's reallocation problem about r. This intu­ itive understanding of the theorem is the result of the formal predicate definitions given in appendix.

(iii): properties of sequences. It is up to the agent who is missing a resource to find good heuristics to formulate the requests, which can lead to a successful dialogue sequence (provided it is possible to find a solution at this stage). Given an agent x, a resource r, and an activity a, one possibility could be a cycle starting at a time T where x successively asks for intervals [Ts , Te] such that Kx ,r f- miss(r, (Ts, Te), a), until all such intervals are exhausted, or the request for one of the intervals is accepted. We call this Strategy I .

Theorem 2 Let us consider a system composed of two agents, x andy, negotiating at Stage 1. Then, for all resources r in the system, and all activities a assigned to x that require r, if x follows Strategy! in its attempt to acquire r from y, starting at T with a request for r for an interval [Ts, Te] such that Kx,r f- miss(r, (Ts, Te ), a), then either the resulting se­ quence of dialogues will be finite and will terminate at a time T 1 , andKx,r' f- feas(a,(Ts*,Te*)),forsomeTs* ,Te*,or ~ Ts', Te' such that

(iv): subsumption of earlier stages. Stage 1 subsumes our previous work done in [Sadri et al., 2002], in the sense that the resource reallocation problems it solves include those solved by [Sadri et al., 2002].

We now give a counterexample for Stage 1.

Example 3 Let us consider the following modification of Example 2, where there is a different initial resource assign­ ment, and different time windows for the activity b (b must be completed by 15):

We do not give any concrete schedules for the agents' activi­ ties since they play no role here. There is no solution to this problem that can be fopnd at Stage 1. In fact, if y gives away r, it will not be possible for it to carry out a any more. 0

3.2 Stage 2 - blind deal

Protocol. The protocol is shown in Fig. 3. After the initial move by y, request(give(R, (Ts, Te))), which makes the di­ alogue reach state 8 1 , the other agent x can either accept or refuse, as in Stage 1, or can propose a deal (promise) . Af­ ter a promise, the agent y who made the request can either accept the deal, causing a successful termination, or refuse it (change.prom), which brings back to 81.

Policy. The policy is shown in Fig. 4. 4 An agent will accept a request about a resource R for the period [Ts, Te] if it would do it at Stage 1, but it will refuse it only if it does not have any deal to propose (promise). In particular, an agent x will pro­ pose a deal, in reply to a request made by an agent y, if there exists an interval [Ts', Te'], disjoint from [Ts, Te], which has the following property: Once y obtains R for [Ts', Te'], it will not need it anymore for [Ts , Te]. In that case, if y ac­ cepts to give R away for the interval [T s', Te'], the negotia­ tion process reaches a successful final state, otherwise x may continue proposing different deals (if they exist), until y ac­ cepts one (successful termination), or there exist no new ones to propose, in which case x will refuse the initial request, thus leading to an unsuccessful final state.

Since there might be several alternative proposals for a deal at a given time, but we want the agent's policies to be deter­ ministic, we use in the definition of the policies of an agent x at Stage 2 a predicate pick((Ts, Te), T), that at any given time T uniquely determines a time period, having made ref­ erence possibly to 'Dx,T and R x·

Example 3 can be solved by the following negotiation dialogue d(2) occurring at Stage 2:

tell(x, y, request(give(r, (10, 15))), d(2) , 1)

tell(y, x,promise(r, (15, 20), (10, 15)), d(2), 2)

tell(x, y , accept(promise(r, (15, 20), (10, 15)) ), d(2), 3)

Properties. At Stage 2 agents are more cooperative than at Stage 1. This is achieved by both agents - and in particu-

4 We use the notation K:x,'T U b. 1- p, where b. is a set of atoms, to mean that K:x,'T, enlarged with b., entails p.

(IC.1) & (JC.3) from Stage 1 (IC.4) tell(X, y, request(give(R, Ts, Te)), D, T) 1\ have(R, (Ts, Te), T) 1\ need(R, (Ts, Te), A, T) 1\ ~ Ts', Te' I · have(R, (Ts', Te')) 1\ tell(y, X,promise(R, (Ts', Te'), (Ts , Te)), D , _) rt. Vy ,T 1\ Ky ,T U {obtain(R,(Ts',Te')),give...away(R,(Ts,Te) )} f- feas(A , (Ts',Te')) :::;. 3 T' I tell(y, X, refuse(request(give(R, Ts, Te))), D, T') 1\ T < T' (IC.5) tell( X, y, request(give(R, Ts, Te)), D , T) 1\ have(R, (Ts, Te), T) 1\ need(R, (Ts, T e), A, T) 1\pick((Ts', Te'), T)l\ · have(R, (Ts', Te'), T) 1\ tell(y, X,promise(R, (Ts', Te'), (Ts, Te)), D, _) rt. Vy ,T 1\Ky,T U {obtain(R,(Ts',Te')),give...away(R,(Ts,Te))} f- feas(A,(Ts',Te')) :::;. 3 T' I tell(y, X , promise(R, (Ts', Te'), (Ts, Te)), D , T') 1\ T < T' (IC.6) tell(X, y, change(promise((-, -), (Ts , Te))), D , T) 1\ have(R, (Ts, Te), T) 1\ need(R, (Ts , Te), A, T) 1\ pick((Ts', Te'), T) l\ · have(R, (Ts', Te'), T) 1\ tell(y, X ,promise(R, (Ts', T e'), (Ts, Te)), D , _) rt. V y,T 1\ Ky ,T U {obtain(R,(Ts',Te')),give...away(R,(Ts,Te) )} f- feas(A,(Ts',Te')) :::;. 3 T' I tell(y, X , promise(R, (Ts', Te'), (Ts, Te)) , D , T') 1\ T < T' (IC.7) tell( X , y, change(promise(R, (Ts', Te'), (Ts, Te))), D , T) 1\ have(R, (Ts , Te), T) 1\ need(R, (Ts, Te), A, T 1\ ~ Ts', Te' I· have(R, (Ts', Te'), T) 1\ tell(y, X,promise(R, (Ts', Te'), (Ts, Te)), D, _) rt. Vy ,T 1\Ky,T U {obtain(R,(Ts',Te')),give...away(R,(Ts, Te) )} f- feas(A , (Ts',Te')) :::;. 3 T' I tell(y, X, refuse(request(give(R, (Ts, Te)))), D, T') 1\ T < T' (IC.8) tell( X, y, promise(R, (Ts', Te'), (Ts , Te)), D, T) 1\ miss(R, (Ts, Te), A) 1\ Ky ,T U {obtain(R,(Ts ,Te)),give...away(R,(Ts',Te'))} f- feas(A,(_, _)) :::;. 3 T' I tell(y, X, accept(promise(R, (Ts', Te'), (Ts, Te)), D , T')) 1\ T < T' (IC.9) tell(X, y, promise(R, (Ts', Te'), (Ts, Te)), D , T) 1\ miss(R, (Ts, Te), A) 1\ Ky,T U {obtain(R,(Ts,Te)) ,give...away(R,(Ts',Te'))} J.L feas(A,(_,_)) :::;. 3 T' I tell(y, X , change(promise(R, (Ts', Te'), (Ts , Te)), D , T')) 1\ T < T'

lartheagenttowhomtherequestisaddressed-todomore Kx,T' reasoning in order to be helpful in response to requests.

• (i): protocol conformance. It is possible to prove that the policy of Stage 2 is conforming to the protocol in Fig. 3.

(ii): properties of single dialogues. Stage 2 does not enjoy the fixed dialogue length property of Stage 1, but it termi(iv): subsumption of earlier stages. More problems can be nates if we have a finite scheduling horizon T max and we do solved by Stage 2 than by Stage 1, namely: not allow the same move twice at different times, in the same Theorem 5 Let us consider a system composed of two dialogue (which is a reasonable requirement). Stage 2 is comagents, x and y. For all resources r in the system, all acputationally more demanding than Stage 1 for both agents. tivities a assigned to x , all times T and intervals [Ts, Te] s. t.

Theorem 3 Let us consider a system composed of two agents, x andy, each having an initial resource assignment. Then, for all resources r in the system, all activities a and b, all times 7 and all intervals [Ts, Te], such that

Kx,T f- miss(r, (Ts, Te), a) 1\ Ky,T f- need(r, (Ts, Te), b) 1\ 3[Ts',Te']suchthatKy,T u{give...away(r, (Ts,Te)), obtain(r,(Ts',Te'))} f- feas(b ,(Ts" ,Te"))

policy of Stage 2, starting at time 7 , and ending at a time 7 1 , such that

ffeas(a,(Ts*,Te*)) for some Ts* ,Te*, or ~ Ts, Te, Ts', Te' such that Kx,T f- miss(r, (Ts , T e), a) 1\ Ky ,T U {give...away(r, (Ts, Te)), obtain(r, (Ts', Te'))} f- indiff(r, (Ts , Te)).

there exists a dialogue d induced by the policy of Stage 2, starting at timeT, and ending at timer', such that

Although this enlarges the set of problems that can be solved, it does not solve, for instance, the problems where for some [Ts", Te"], there exists a dialogued induced by the more than one exchange is needed. We now give the following counterexample for Stage 2.

Kx,T' f- need(r, (Ts, Te), a) 1\ Ky ,T' f- indiff(r, (Ts , Te)).

(iii): properties of sequences.

Theorem 4 Let us consider a system composed of two agents, x andy, negotiating at Stage 2. Then, for all re- Ry = {have(r,(13,17))} which require r, if starting at time T x follows Strategy] to request r from y, either the sequence of dialogues will

Example 4 Let us consider the following modification of Example 2, where there is a different resource and activity assignment:

sources r in the system, and all activities a assigned to x There is no solution to this problem that can be found at Stage 2. In fact, the (minimal) requests that x will make to obtain r for 5 consecutive time periods are: [13, 15] and [15, 17] . y terminate at r' after a finite number of dialogues, and may reply to the first one with a deal to obtain r for [10, 12]

or for [11, 13], neither of which makes x's activity b feasible. The same will happen for the second request, which results in an unsuccessful sequence of negotiation dialogues for a problem that has a solution. D

4 Discussion

This work benefits from a logic-based high level approach that facilitates specification and proof of formal properties and which has an operational model, that forms a bridge be­ tween the system description and implementation. This fea­ ture is difficult to find in most related work: as the negotiation process becomes more elaborated, it gets harder to find and prove formal properties as those identified here. In the follow­ ing, we briefly survey similar approaches to agent negotiation or proposed solutions to the same problem.

Our modelling of constraints draws inspiration from work on constraint satisfaction for a monolithic system [El Sakkout and Wallace, 2000]. But our work differs from it both in context and approach. Our aim is to provide protocols and policies for a multi-stage process of negotiation in a collab­ orative multi-agent context, whereas their aim is the solution of T-RRP problems viewed as constraint satisfaction prob­ lems, while minimising changes to concrete schedules. [Har­ rison, 2000] extends such work to multi-agent systems, but the focus there is again that of minimising changes to exist­ ing schedules, and not on negotiation.

[Conry et al., 1992] proposes an approach to negotiation based on multiple stages, focusing on coordination degrees. Progressive stages require that agents solve problems in a more coordinated way. In the first stage, the agents try to solve problems independently of other agents' constraints, while in the last one it is possible, e.g., to discover that the overall problem is over-constrained and thus a certain goal is unfeasible.

There are many issues regarding negotiation that our pa­ per does not address. For example, we do not deal with the efficiency and timeliness of negotiation. These issues are ad­ dressed in [Kraus et al., 1995] using utility functions.

We are currently working on extending our negotiation process to a number of further stages, whereby the agents dis­ close to each other more information about their constraints in order to be able to propose more informed deals for ex­ changes of resources. We would like to stress that we ap­ proach a resource sharing problem from a multi-agent per­ spective: Existing scheduling techniques are likely to outper­ form compared to the negotiation processes outlined in this work, but they do not generally allow for agent autonomy. In the final stage of such an approach, where all the constraints are known, the problem becomes one of distributed constraint satisfaction. [Yokoo and Hirayama, 2000] reviews a number of algorithms for such an application.