Dynamic Negotiations in Multi-Agent Systems

Abstract

Collaboration workflows for human experts involved in distributed problem solving and acting in dynamic environments require advanced self-configuration mechanisms for optimal selection of service providers. Such dynamic environments, specific for example to problems like environmental management, disaster and crisis management, and high-risk project management, are characterized by continuously changing situations, occurrence of unexpected events, as well as high variability in resources' availability. We propose a solution for selfconfiguration based on a framework for the development of flexible cooperative multi-issue one-to-many service negotiations. The framework allows two levels of dynamic configuration of negotiations. First, the negotiation protocol can by dynamically selected depending on the profiles of available service providers. Second, negotiation subject as well as the parameters of the negotiation protocol, can be dynamically set depending on the current requirements of the service requester. In this paper we illustrate the features of our framework for dynamic negotiations using an example of service contracting in the field of disaster management. We also provide initial experimental results concerning the e ect of the dynamic selection of negotiation protocol onto the quality of the negotiation outcome as well as onto the communication complexity of interactions incurred during negotiations.

Keywords

• multi-agent system
• service negotiation
• contract net

-

The increasing complexity of real-world problems demands special support for distributed collaborative problem solving. Multi-agent systems (MAS) are a special class of distributed systems that combine interaction and coordination with distribution of computation to improve performance of problem solving processes. MAS were successfully applied for solving problems that require distributed reasoning, decentralization and collaboration [ 19 ]. An example is a collaboration system for helping human experts and population to deal with disasters (see the FP7 DIADEM project1 that targets crisis management in the context of chemical incidents in industrial and urban areas).

A workflow is represented as a structured set of coordinated tasks and information exchanges defined to carry out a well-defined business process in (possibly multiple 1 DIADEM Distributed information acquisition and decision making for environmental management: http://www.ist-diadem.eu/. networked) organizations [ 18 ]. Collaborative problem solving in heterogenous, unpredictable, and dynamic environments can be achieved by providing an increased flexibility in workflow formation, that goes far beyond the classic approach of static and centralized workflow definitions. Examples based on empirical analysis of real experiences can be given in the area of organizational adaptation to disasters [ 9 ]. Such infrastructure support can be provided by service-oriented MAS, like for example the Dynamic Process Integration Framework (DPIF) [ 13 ]. In such frameworks, communication links between local processes in agents are facilitated using service discovery: whenever an agent supplying some service (we will call this agent the manager) in a workflow requires data provided by some other service (we will call this agent the contractor), a communication link must be established between them. A similar problem occurs in optimal resource allocation for workflow scheduling [ 10, 6 ], as well as in dynamic role binding in MAS organizations [ 11 ].

The self-configuration provided by service discovery and matching can be improved by enhancing it with a finer level of control based on one-to-many service negotiation ([ 5 ], [ 12 ], [ 14 ], [ 20 ]). In our work we proposed a novel negotiation model that follows the conceptual framework of one-to-many service negotiation [ 2 ]. This model allows the dynamic configuration of negotiation protocol and negotiation parameters based on the requirements of each negotiation instance. More specifically, the model provides two levels of dynamic configuration of negotiations. First, the negotiation protocol can by dynamically selected by the manager depending on the profiles of available service providers. Second, negotiation subject as well as the parameters of the negotiation protocol, can be dynamically set depending on the current requirements of the service requester. Both features are considered in this paper.

In this paper we illustrate the features of our framework for dynamic negotiations using an example of service contracting in the field of disaster management. We also provide initial experimental results concerning the e ect of the dynamic selection of negotiation protocol onto the quality of the negotiation outcome as well as onto the communication complexity of interactions incurred during negotiations.

The paper is organized as follows. We start in Section 2 by introducing the components of our framework. In Section 3 we introduce a sample example concerning a typical activity in a situation assessment problem encountered in chemical incident management. In Section 4 we provide an initial experimental analysis of the e ect of negotiation protocol selection onto the negotiation outcome as well as onto the communication complexity of negotiation interactions. In Section 5 we cover related works in the area of MAS for business process management and negotiation for service contracting and resource allocation in flexible workflows. In Section 6 we present our conclusions and point to future works. 2

Background

Negotiation is a process that describes the interaction between one or more participants that must agree on a subject by exchanging proposals about this subject [ 8 ]. Negotiation about a service that one or more participants agree to provide to other participants is called service negotiation. We have developed a conceptual framework for service negotiation that addresses protocols, subjects and decision components. Our framework supports generic one-to-many negotiations and it defines two roles: manager and contractor [ 17, 12 ]. The manager is the agent that requests a service and thus initiates the negotiation. The contractor is the agent that is able to provide the service requested by the manager. For a more complete review of the conceptual framework, please see [ 2 ]. A brief description of the design and implementation is given in [ 16 ].

Currently we have configured our framework with three negotiation protocols that we have found useful in disaster and environment management problems. These protocols are: 1. Direct Task Assignment. Using this protocol there is actually no negotiation happening between the manager and the contractors. The manager simply picks up one or more contractors and assigns them the task2. Although simple, Direct Task Assignment – DTA negotiation protocol is actually very useful to model subordination relationships, that are common for task assignments to team members that operate in a disaster environment. For example in a disaster management information system, an Incident Commander can dispatch tasks to team members operating in the area a ected by the disaster. 2. Contract Net. Proposed by [ 17 ], Contract Net – CNET3 is probably one of the most influential negotiation protocols utilized in distributed collaborative problem solving, with many extensions currently available (see for example [ 20 ]). CNET is essentially a one step protocol: the manager announces a task to the contractors in the announcement stage, each contractor proposes or refuses to submit a bid in the bidding stage, and finally the manager decides to award the task to at least one of the contractors in the awarding phase. It can be easily noticed that the DTA protocol is in fact a simplified CNET without the announcement and the bidding stages. 3. Iterated Contract Net. CNET can be extended to multiple steps thus obtaining Iterated Contract Net – ICNET4. This protocol is very useful in situations when a single step is not su cient for the manager to select a contractor for awarding the task. This may happen for example if the requirements set for the task announced by the manager are too restrictive and thus neither of the contractors is able to meet them in a satisfactory way. Another situation is when contractors are operating in a constrained environment that does not allows them to bid. For example, considering a disaster management scenario, one of the stakeholders (for example a chemical expert) might be caught in an important meeting that forbids him or her to answer to incoming phone calls. However, repeated calls, probably originating from repeated task announcements in a negotiation caused by the occurrence of a very important event, can enable him to pickup his phone and answer, i.e. to bid.

A set of generic negotiation steps are defined: (i) negotiation subject identification and negotiation announcement (initiation of negotiation), (ii) bidding, i.e. making pro2 DTA has similarities with FIPA Request interaction protocol, see http://www.fipa.org/ specs/fipa00026/, excepting that the contractor cannot refuse the task. 3 CNET is standardized by Foundation for Intelligent Physical Agents, see http://www.fipa.

org/specs/fipa00029/. 4 ICNET is standardized by Foundation for Intelligent Physical Agents, see http://www. fipa.org/specs/fipa00030/ posals and counter-proposals, (iii) deciding whether an agreement or a conflict was reached, and (iv) termination.

Negotiation subject comprises the service description and a subset of the service parameters that are important decision factors during negotiation (i.e. their current values are taken into consideration when selecting the appropriate service providers). During negotiation, these parameters are considered negotiation issues.

Negotiation issues are described by name, data type, and monotonicity. The name uniquely identifies the issue in a negotiation subject. The data type describes the type of the value that the issue is allowed to take (e.g. number, string, geographical location, date/time, etc.). The monotonicity specifies whether the manager prefers higher values to lower values of this issue: (i) INCREASING if the agent prefers high utility values of the issue and (ii) DECREASING if the agent prefers low utility values of this issue.

Service negotiations in disaster management are cooperative. Cooperativity stems from the fact that the overall goal of participants is the optimization of the response for situation assessment. Negotiations for a certain service provision are carried out only with agents that can provide the required service (i.e. that possess the domain knowledge or physical capabilities that are needed to provide the service). Provider agents will usually accept to o er their services if they are currently able to do so (i.e. if they posses all the necessary resources). During a negotiation: (i) the manager is the leading decision factor seeking to optimize the assignment of the negotiation task to the contractor(s); (ii) the contractor(s) make their best proposals for the manager, taking into account their current duties and availability, thus preserving their autonomy according to the principles of professional bureaucracy [ 1 ].

Service parameters can be classified into 4 classes: (i) DYNAMIC that specifies that the issue value is not fixed by the manager, i.e. the contractor can propose di erent values for the issue; (ii) FIXED that specifies that the issue value is fixed by the manager, i.e. if the contractor proposes a di erent value for the issue then the corresponding local utility of the issue is zero; (iii) CONDITION that specifies that the issue value is fixed by the manager, but if the contractor proposes a di erent value for the issue then the total utility of the proposal is zero; normally a contractor that cannot meet the issue value requested by the manager should decide to not bid because the utility of her bid will be zero; (iv) TRIVIAL that means that the issue is not taken into account in the computation of the bid utility, although it can be set in the request of the manager and consequently, it can be taken into account in the negotiation by the contractor and help her to make a more informed decision if and what to bid.

Negotiation participants playing either the manager or contractor roles use utility functions to quantify their preferences over proposals. In our framework the manager uses a weighted additive utility function to evaluate proposals and to select the service provider (we omit the discussion of contractor utility functions, as they are not relevant for this paper; for details on contractors’ utilities please consult reference [ 2 ]). Each negotiation issue i has a weight wi 2 [0; 1] and a partial utility function fi. Note that weights are normalized i.e. Pi wi = 1. Intuitively, for the manager the weight of an issue represents the relative importance of that issue in the set of all issues associated to a negotiation subject.

The partial utility of an issue i maps the issue domain Di to a value in the interval [0; 1], i.e. fi : Di ! [0; 1]. The function fi depends on the domain of the issue. For example, a possibility to define the partial utility function of a real valued issue with Di = [xmin; xmax] is as follows: fi(x) =

jx jxmax x j xminj

Here, x is the reference value assigned by the manager to the issue i (that represents the optimal value from the manager point of view) and jx yj is the distance between x and y (note that the distance depends on the data type of the negotiation issue). Note that a negotiation issue for which the partial utility is defined as a distance from the reference value has always a DECREASING monotonicity. Let I be the set of negotiation issues partitioned into sets I" and I# of issues with INCREASING and DECREASING monotonicity. The utility function of a proposal x = (xi)i2I is computed as follows: um(x) =

X wi fi(xi) + X wi (1

fi(xi)) i2I" i2I# 3

Sample Scenario

We illustrate our approach by using an example derived from a real world use case investigated in the FP7 DIADEM project. For the sake of clarity but without the loss of generality we assume a significantly simplified scenario that is illustrated in Figure 1 utilizing the Agent Modeling Notation – AML [ 4 ]. In a chemical incident at a refinery a chemical starts leaking and forms a toxic plume spreading over a populated area. The impact of the resulting fumes is assessed through a service composition involving collaboration of human experts. During this incident health complaints are reported. Consequently, the Incident Commander dispatches a chemical expert that holds expertise in estimating the gas concentration in the a ected area. This expert is denoted as Reference value

Weight Data type Boundary Negotiable

Location

Quality

Deadline loc 100 11:47 AM 1 2 3 REGION INTEGER TIME

n/a 100 100

FIXED DYNAMIC DYNAMIC Chemical Adviser and, among other things, she guides fire fighter Measurement Team agents which can measure gas concentrations at specific locations in order to provide feedback for a more accurate estimation of the critical area. This interaction between Chemical Adviser and Measurement Team agents involves negotiation to determine the optimal providers of appropriate measurements (for more details see [ 3 ]).

We can observe from Figure 1 that Chemical Adviser provides the service Map of High Concentration Zones and this provisioning requires the contracting of Concentration Measurement, Weather Report, as well as Information about Source services. In this scenario Chemical Adviser agent plays the negotiation role of manager looking for a provider for the service Concentration Measurement.

The optimal selection of the service provider takes into account: the location where the measurement must be performed, the quality of the measurement, and the duration for performing the measurement. Additionally we assume that the measurement quality is given as a percentage and that the maximum time frame for performing the measurement is 100 minutes. The description of the negotiation issue, together with the manager proposal are given in Table 1. Weights of negotiation issues were normalized as follows:

wLocation = 1=6; wQuality = 2=6; wDeadline = 3=6

Let us assume that there are two Measurement Team agents in the system and each of them decides to bid with an o er for providing the service Concentration Measurement. Their bids are shown in Table 2.

The utility of the bid of Measurement Team 1 is computed as follows: uLocation1 uQuality1 uDeadline1 (1

0=1) 30=100)

uMT1 = uLocation1 + uQuality1 + uDeadline1 = 0:844 The utility of the bid of Measurement Team 2 is computed as follows: uLocation2 uQuality2 uDeadline2

(1 0=1) 0=100) 25=100)

Chemical Adviser agent uses these equations to compute the utilities of each bid received from Measurement Team agents. Then Chemical Adviser applies a strategy that allows it to either immediately select the winning bid or to decide if to continue the negotiation using a new iteration. Let us assume that Chemical Adviser applies a strategy that considers acceptable only those bids that pass a given threshold. If none is above the threshold then Chemical Adviser can perform a second iteration either by relaxing the conditions of the call for proposals (for example by decreasing the required quality of the measurements or by extending the deadline for performing the measurements) or by decrementing the threshold, thus giving a chance to the Measurement Team agents to update their bids. If at least one bid is considered acceptable then Chemical Adviser can decide to accept one or more Measurement Team agents to contract the Concentration Measurement service. Assuming a threshold of 0:85, according to this algorithm Chemical Adviser will select Measurement Team 2 after the first iteration. 4

Experimental Results

In this section we discuss the results of our initial experiments with service negotiations utilizing the di erent negotiation protocols currently supported by our framework: DTA, CNET, and ICNET. We first propose a model for the experimental analysis of oneto-many negotiations and then we provide experimental results that cover negotiation outcome and communication complexity of negotiation interactions. 4.1

Modeling Assumptions

When faced with a service negotiation problem, an agent playing the manager role will have to decide what negotiation protocol to use. In our case, the manager may decide to use one of the DTA, CNET or ICNET negotiation protocols that were discussed in Section 2. This choice will a ect important factors like quality of the negotiation outcome as well as communication complexity incurred during the negotiation interaction [ 15 ] that overall impact the e cacy of the collaboration process for resolving the incident.

In what follows we propose a simple experimental setting aimed at analyzing the impact of the strategy employed by the manager agent to choose a service negotiation protocol on the quality of the negotiation outcome as well as on the communication complexity of negotiation interactions. The experiment is focused on evaluating a single negotiation rather than a complex collaboration workflow comprising more negotiations (we are aware of this limitation and we plan to address it in the near future).

Let us assume that a manager agent M is negotiating for contracting a service from a contractor agent that is member of a set of n contractors C1; : : : ; Cn. Simplifying things we assume that each contractor Ci can o er a utility value ui to the manager such that ui 2 [uimin; uimax] [0; 1]. The interval [uimin; uimax] is part of the profile of the contractor. For example, if the utility intervals of contractors Ci and C j have an empty intersection and uimin < u mjin it means that C j will always appear as more profitable than Ci for the manager. However, if the intersection of the intervals is nonempty it means that sometimes Ci can also be more profitable than C j for the manager.

Moreover, each negotiation will always involve requirements that are set by the manager and must be met by the contractor in order to be allowed to bid for a contract. These requirements depend on the negotiation issues and on the constraints on the negotiation issues that are set by the manager in the request for service. For example, considering the Concentration Measurement service, Chemical Adviser may require Measurement Team agents to bid if and only if they are equipped with certain specialized measurement devices like for example drager tubes5. We assume that for each contractor Ci there is a probability of ci 2 [0; 1] that she will be able to satisfy the requirements set by the manager’s request. The probability pi is also part of contractor’s Ci profile.

Contractors are usually critical resources that do not always have the possibility to bid for a service contract. Let us take for example the Chemical Adviser that can be caught in an important meeting while health complaints start being reported. In such a situation the Incident Commander must assign the task Map of Critical Zones to an expert in the chemistry of gases, i.e. the Chemical Adviser. Then the Incident Commander must adopt an iterative negotiation protocol to allow the Chemical Adviser to bid. Let us assume that in our experimental setting each contractor Ci is busy with a probability bi 2 [0:1]. Nevertheless, we assume that even when she is busy, if Ci is able to meet the requirements set by the manager then she will find time to bid in the second iteration.

Let us also assume that the manager M will choose to utilize one of the DT A, CNET or ICNET (two iterations version) negotiation protocols with the probabilities p; q; r 2 [0; 1] such that p + q + r = 1. The triple (p; q; r) is part of the manager’s profile. Depending on the utilized protocol the negotiation will incur a certain communication cost estimated as the number of messages exchanged between the manager and the contractor during the negotiation. Moreover the quality of the negotiation outcome will be estimated as the utility perceived by the manager for the contracted service.

If the manager is utilizing the DT A negotiation protocol then she will randomly assign the task to one of the contractors. However, a contractor that does not meet the requirements will not be able to provide the service, so she will have to report failure. In this case the manager will randomly select another contractor and so on, until a suitable contractor is found (we assume this is always the case). Note however that this trialand-error process performed by the manager a ects the outcome of the negotiation by decrementing her perceived utility. More precisely, if the successful contractor Ci that could perform the task was selected in the k-th trial then the utility perceived by the 5 They are tubes that contain chemicals that react to a specific compound to form a stain or color when passed through the gas. manager will be ui (1 (k 1)=n) rather than ui. Moreover, the communication cost associated to this negotiation interaction consists of 2 k message exchanges.

If the manager is utilizing the CN ET negotiation protocol then she will select the contractor Ci that provides her the highest utility ui from those contractors that met the requirements of the call for proposals and were not busy (i.e. they were able to bid). The communication cost consumed for a busy contractor consists of 2 message exchanges, while for a not busy contractor (it doesn’t matter if she could met or not the requirements, according to the CN ET negotiation protocol [ 17 ] she either proposed or refused to bid) the communication cost consists of 3 message exchanges.

If the manager is utilizing the ICN ET protocol we assume that she will always perform two negotiation iterations. We simply the negotiation by assuming that contractors do not change their between iterations. This assumption is not as restrictive as it might look, because some contractors are busy and can bid only in the second iteration. Moreover, we also assume that a busy contractor that meets the requirements of the call for proposals will always find time to bid during the second negotiation iteration. The manager decides the contractor to whom to award the task after the second iteration. The communication cost for a busy contractor consists in 4 message exchanges, while for a non-busy contractor it consists of 5 message exchanges. 4.2

Experimental Results and Discussions

We created a simulation experiment assuming the model introduced in Section 4.1. In the simulation we considered one manager and n contractors. During a simulation, the given manager and contractors’ profiles are set and a large number of negotiation instances are run. The manager is characterized by her profile (p; q; r) that defines her strategy for dynamic selection of the negotiation protocol for each negotiation instance. Each contractor Ci is characterized by her profile defined as a triple ([uimin; uimax]; ci; bi). The contractors’ profiles are given as input to the simulation algorithm. The values of the utilities ui are randomly selected for each negotiation instance assuming uniform distributions. Moreover, the probabilities ci and bi are utilized to determine the status of a contractor (as satisfying or not satisfying the requirements of the manager proposal and busy or not busy) for each negotiation instance.

The goal of the simulation was to observe and analyze the quality of the negotiation outcome as well as the incurred communication cost for di erent profiles of the manager agent. Therefore we ran the simulation for various manager profiles by sampling the probability space (p; q; r) accordingly. Assuming a sampling rate of 1=m (where m is a given natural number) we developed a simulation program that evaluates the average utility perceived by the manager, as well as the average communication cost incurred during negotiations for the following large set of manager profiles f(i=m; j=m; 1 (i + j)=m)j0 i; j m; 0 i + j mg.

In our initial experiment we considered a simple negotiation case with 1 manager and 3 contractors. We ran 2000 negotiations and we recorded the negotiation outcome as well as the number of exchanged messages. We took m = 20 in the sampling rate of the probabilities that define the manager profile. The contractor profiles were set as follows: C1 = ([0:2; 0:3]; 0:8; 0:2), C2 = ([0:5; 0:6]; 0:5; 0:5), and C3 = ([0:8; 0:9]; 0:2; 0:8). These values show that the manager will always prefer C2 and C3 to C1. Note that failed negotiations (i.e. negotiations that failed to allocate a contractor for providing the service) are possible given this set of contractor profiles, and consequently they were filtered out during our experiments. Note however that their number was very small (approximately 1% from the total number of negotiations), so it was considered not relevant for the results of the experiment.

If the manager is using the DT A protocol then C1 will perform the task whenever she is able to meet the manager’s requirements and (i) she is either selected the first or (ii) she is selected after C2 and C3 but both C2 and C3 could not meet the manager’s requirements and reported failure (note that as C1 meets the requirements requested by the manager with a higher probability than C2 and C3, she will perform quite often the task according to the DT A protocol). The conditions for C2 or C3 to perform the task are analogous with the conditions for C1. Note that the status of being “busy” is not taken into account by the manager when she is playing the DT A negotiation protocol, i.e. if she selects a certain contractor then the task will be assigned to her in any case. Nevertheless, if the assigned contractor cannot finalize the task successfully then she will report failure and consequently the manager will retry the operation of service contracting by assigning the task to another contractor.

If the manager is using the CNET protocol the contractors that are set to “busy” are not taken into account by the manager, as they cannot bid. although they receive the call for proposals from the manager. For example, even if C3 can o er a high utility to the manager, she has a high probability of being busy, so she will not be able to bid in many CNET negotiations. So in this case C2 can C1 can win the negotiation more often. Moreover, C2 is also busy quite often, giving a chance to award the task to C1.

Finally, when the manager is using the ICNET protocol, even if a contractor is “busy” and cannot bid in the first negotiation iteration she will still be able to bid in the second iteration. This interaction pattern allows for example to contractor C3 to bid and consequently to increase the utility perceived by the manager.

The experimental results are shown graphically in Figures 2 and 3. These figures present the plots of the average utility perceived by the manager as well as of the average number of exchanged messages per negotiation as functions of the probabilities p and q (shown as P DTA and P CNET on the figures) of the manager to choose between the DT A and CNET negotiation protocols. Note that the dependencies on the probability r for choosing the ICNET protocol trivially follow as p + q + r = 1.

The first observation is that the highest utility (slightly above 0:5) is perceived by the manager when she always uses ICNET negotiation protocol. However, this strategy also brings her the highest overhead in terms of communication complexity, i.e. slightly above 14 messages on average per negotiation. This clearly shows the tradeo that exists between the optimality of the solution and the communication complexity that occurs in negotiation interactions when the negotiation protocol can be dynamically selected by the initiator of the negotiation.

Secondly, we can observe that the di erence in terms of manager’s perceived utility between the DT A and CNET protocols is small (at least in this experiment). For example, if ICNET is not utilized, i.e. r = 0 or equivalently p + q = 1, we can easily observe that the average utility perceived by the manager is slightly variable around 0:4. This can be explained by the fact that what is gained by the bidding stage that is present in CNET (and absent in DT A) is actually lost by the fact that a “busy” contractor cannot bid, while DT A can use him or her for awarding the task. In such a situation the optimal strategy of the manager will depend on his knowledge of the probabilities of availability to bid of the contractors. i.e. the less are they busy the higher will be the manager’s perceived utility. Note however that communication complexity is clearly higher for CNET (about 10 messages per negotiation if p = 0 and q = 1) than for DT A (about 4 messages per negotiation if p = 1 and q = 0).

Finally, note that the manager utility um for a manager profile (p; q; r) can be decomposed as “expected utility” based on the utilities that would have been obtained if the manager had been used either DT A, CNET or ICNET protocols only, i.e. um(p:q:r) = p umDT A + q uCmNET + r umICNET = p um(1; 0; 0) + q um(0; 1; 0) + r um(0; 0; 1). This decomposition of um explains the planar shape of the surface representing function um in Figure 2. This observation extends also to the planar shape of the surface representing Mes function in Figure 3. 5

Related Works

ADEPT – Advanced Decision Environment for Process Tasks is probably one of the first business process management systems that proposed the utilization of intelligent software agents to cope with inter-organizational collaborative aspects of business processes including: multiple and geographically dispersed organizations, autonomous management of resources, highly dynamic and unpredictable nature of business processes, decentralized control, mixtures of human activities and automated tasks [ 7 ]. ADEPT introduced many concepts that we found useful including loosely coupling of agent tasks and services by means of service matchmaking and negotiation and usage of the notion of agency (with peer-to-peer and hierarchical relationships in organizations) that we found similar with our communities. However ADEPT was an early work and could not benefit on the recent developments including principled approaches of agent-oriented methodologies and technological advancements in software agent platforms. Additionally we did not find in ADEPT the concept of ad-hoc community that we introduced to model teams of agents that act together towards resolving a given incident.

Recently, a service negotiation framework has been proposed in paper [ 12 ]. That framework was applied to Web service negotiations between insurance companies and car repair companies. The negotiation is implemented as an interaction between Web services and the participants’ preferences are represented using an ontology. The framework utilizes ICNET protocol for negotiation, with the message exchanges implemented as Web service method invocations. In this approach, the negotiation protocol(s) used are fixed, unlike in our approach where we do not constrain them to fixed interaction protocols. Rather, we define a set of generic negotiation steps that are likely to be followed by many negotiation protocols. Our framework is generic in the sense that it allows creation and integration of di erent negotiation protocols. The approach of combining generic negotiation with components for representation of negotiation participants’ deal space, utilities, and resources allows us to design and evaluate di erent negotiation protocols useful for service negotiation in disaster management. Also, unlike [ 12 ] where the authors utilize a fixed set of subject issues specially tailored for their scenario, we give the possibility to define new subject issues with their properties that best suit the application in hand. Additionally, contractor utilities have a di erent semantics inspired by task allocation problems ([ 14 ]) that is more appropriate for the collaborative rather than competitive context for which our system is designed. However, similarly to [ 12 ], we use additive weighted utility functions for managers that take into account partial utility functions defined for each negotiation issue.

In paper [ 5 ], the authors introduced a new multi-issue negotiation model such that the negotiation subject is characterized by interdependencies between the issues. Similarly to our negotiation framework, this model is applied to cooperative negotiation in crisis management. The paper discusses in some detail a scenario involving the activity of an emergency call center for victims dispatching taking into account appropriate spaces in the hospitals as well as transport constraints and availabilities. However, there are notable di erences between this approach and our approach. The model proposed in [ 5 ] is using a mediator with the role of a centralized authority (for example a physician or a higher level authority) that makes proposals to participant agents, and receives their responses that either accept or reject the proposals. Rejections are accompanied by recommendations made to the mediator that enable him to adjust his proposal in the next negotiation step. Participant agents decide to accept or reject the mediator proposals using multi-criteria decision analysis tools. In our approach the problem is di erent – to determine one or more optimal service providers according to a set of service parameters that are dynamically determined depending on the current conditions in a situation assessment problem.

In paper [ 10 ], the authors proposed a new method for generic workflow scheduling that is able to support both human and non-human (i.e. machines, tools, or computers) resource allocation taking into account quantitative measures of the competence and preference of resources for workflow operations. In paper [ 6 ] the authors proposed a new method for optimal allocation of resources in complex manufacturing workflows using CNET negotiation. Resource agents are allowed to bid for resource allocation and deallocation for each workflow operation. Resources can dynamically change by updating their characteristics like workload and processing time. A certain cost function is defined for each workflow operation. The authors propose a sound bid evaluation function that allows to find an optimal allocation of resources to minimize the cost of workflow execution. Note however that di erently from our work, both papers [ 10 ] and [ 6 ] assume a static workflow definition, while this assumption cannot be applied for our type of problems where the workflow is dynamically formed during the distributed problem solving process, possibly spanning multiple organizations [ 3 ].

In paper [ 11 ], the authors consider the problem of dynamic role assignment in agent organizations where agents can dynamically join and/or leave an organization. They propose a new version of CNET called agent centric contract net protocol that takes into account agent reputation for reliable agent discovery and dynamic role binding. Although the problem of dynamic role binding is more complex than service contracting that we considered in our approach, agent characteristics like reputation, as well as competence or preference can be also easily incorporated into our model by considering them as negotiation issues that convey a certain utility for the manager agent that is requesting the service. 6

Conclusions

In this paper we presented a framework that allows definition of one-to-many service negotiation protocols in agent-based collaborative processes. This framework supports flexible configuration of multi-issue negotiation subjects, properties of negotiation issues, and utility functions of participant agents. An example describing a sample negotiation scenario was discussed in detail, emphasizing how service negotiation can improve the selection of optimal service providers. We also presented a simple experimental setting and initial experimental results aimed at analyzing the impact of the strategy employed by the manager agent for selecting a service negotiation protocol on the quality of the negotiation outcome as well as on the communication complexity of negotiation interactions.

As future work we plan to expand the experiments in at least two directions: (i) to analyze the impact of the negotiation protocol on the quality of the negotiation outcome as well as on the communication complexity of negotiation interactions depending on several profiles of contractor agents; the results can help the manager to tune his strategy for better selection of the negotiation protocol; (ii) to consider more complex negotiation instances that take into account more negotiation iterations, as well as that contractors might change their bids and managers can change their strategy for accepting contractors’ bids during each iteration; (iii) to consider more complex workflows involving at least two interdependent negotiations such that the contracted service might also involve contracting of other required services.

Acknowledgement

The work reported in this paper was carried out as part of the Diadem project: http:// www.ist-diadem.eu. The Diadem project is funded by the E.U. under the Information and Communication Technologies (ICT) theme of the 7th Framework Programme for R&D, ref. no: 224318.

References

1. Argente , E. , Julian , V. , and Botti , V.: Multi-Agent System Development Based on Organizations. Electronic Notes in Theoretical Computer Science 150 , 55 -71 Elsevier ( 2006 )

2. Ba˘dica˘, C. , Scafes ¸ , M. : Conceptual Framework for Design of Service Negotiation in Disaster Management Applications . In: Bai, Q. , Fukuta , N. (eds.), Advances in Practical Multi-Agent Systems, Studies in Computational Intelligence 325 , 359 -375 Springer Verlag ( 2010 )

3. Ba˘dica˘, C. , Ilie , S. , Kamermans , M. , Pavlin , G. , and Scafes¸, M. : Using Negotiation for Dynamic Composition of Services in Multi-Organizational Environmental Management . International Symposium on Environmental Software Systems ISESS' 2011 ( 2011 ) (submitted)

4. Cervenka , R. , Trencansky , I.: The Agent Modeling Language - AML , Whitestein Series in Software Agent Technologies and Autonomic Computing ( 2007 )

5. Hemaissia-Jeannin , M. , El Fallah Seghrouchni , A. , Labreuche , C. : A New Multilateral Multiissue Negotiation Protocol and its Application to a Crisis Management Problem . Multiagent and Grid Systems 4 ( 1 ), 103 - 123 IOS Press ( 2008 )

6. Hsieh , F.-S.: Analysis of contract net in multi-agent systems . Automatica 42 ( 5 ), 733 -740 Elsevier ( 2006 )

7. Jennings , N. R. , Norman , T. J. , Faratin , P. , O'Brien , P. , and Odgers , B. : Autonomous Agents For Business Process Management. Applied Artificial Intelligence 14 ( 2 ), 145 - 189 Taylor & Francis ( 2000 )

8. Jennings , N.R. , Faratin , P. , Lomuscio , A.R. , Parsons , S. , Sierra , C. , and Wooldridge , M. : Automated Negotiation: Prospects, Methods and Challenges. Group Decision and Negotiation 10 ( 2 ), 199 -215 Springer ( 2001 )

9. Kreps G.A. , Bosworth , S.L. : Organizational Adaptation to Disaster . In: Rodriguez, H. , Quarantelli , E.L. , and Dynes , R.R . (eds.), Handbook of Disaster Research , 297 -315 Springer ( 2007 )

10. Lee , K.M. : Adaptive Resource Scheduling for Workflows Considering Competence and Preference . In: Negoita, M.Gh. , Howlett , R.J. , and Jain , L.C. (eds.) Knowledge-Based Intelligent Information and Engineering Systems. Lecture Notes in Computer Science 3214 , 723 -730 Springer ( 2004 )

11. Lee , J. , Lee , S.-J., and Chen , H.-M.: Dynamic role binding with Agent-centric Contract Net Protocol in agent organizations . IEEE International Conference on Systems, Man and Cybernetics , SMC 2008 , 536 - 643 ( 2008 )

12. Paurobally , S. , Tamma , V. , and Wooldridge , M.: A Framework for Web service negotiation . ACM Transactions on Autonomous and Adaptive Systems 2 ( 4 ), ACM Press ( 2007 )

13. Pavlin , G. , Kamermans , M. , and Scafes¸, M. : Dynamic Process Integration Framework: Toward E cient Information Processing in Complex Distributed Systems . Informatica 34 , 477 - 490 ( 2010 )

14. Sandholm , T. : An implementation of the contract net protocol based on marginal cost calculations . Proceedings of the 12th International Workshop on Distributed Artificial Intelligence , 295 - 308 ( 1993 )

15. Scafes ¸ M., and Ba˘dica˘, C. : Framework for Performance Evaluation of Service Negotiations in Agent Systems . Proc. of the 8th Int.Workshop on Modelling, Simulation, Verification and Validation of Enterprise Information Systems MSVVEIS 2010 , 19 - 29 , INSTICC Press ( 2010 )

16. Scafes¸, M. , Ba˘dica˘, C. , Pavlin , G. , and Kamermans , M. : Design and Implementation of a Service Negotiation Framework for Collaborative Disaster Management Applications . Proceedings of the 2nd International Conference on Intelligent Networking and Collaborative Systems INCOS' 2010 , 519 - 524 ( 2010 )

17. Smith , R.G. : The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver . IEEE Transactions on Computers 29 ( 12 ), 1104 - 1113 IEEE Computer Society ( 1980 )

18. van der Aalst , W., van Hee, K. : Workflow Management: Models, Methods, and Systems . MIT Press ( 2002 )

19. Wooldridge , M.: An Introduction to MultiAgent Systems ( 2nd ed.), John Wiley & Sons ( 2009 )

20. Yang , J. , Li , W.-L. , and Hong , C.-Y.: An Improvement to CNCP in Large-Scale Muti-Agent System . Proccedings of the 3rd International Conference on Innovative Computing Information and Control ICICIC'08 , 147 ( 2008 )