Achieving Mediated Agreements using Agreement Space Modeling C. Carrascosa, M. Rebollo Universidad Politécnica de Valencia Departamento de Sistemas Informáticos y Computación (DSIC) Camino de Vera s/n – 46022 Valencia – Spain {carrasco, mrebollo}@dsic.upv.es Abstract. An agreement is an arrangement between two or more enti- ties to do something. This implies a context in which terms the agreement is developed. This paper presents a model of such agreement context as an euclidean space. On the other hand, an agreement can also be seen as a Constraint Satisfaction Problem (CSP) which solution space models an agreement space. This will allow to have a mediator that could not only model the agreement as an space, but also to check the viability of the agreement as it is being built. This mediator, that could even give some counsels about the agreement terms being formulated, is called here Counselor Agent. The protocols to interact with such agent to build an agreement are also presented. 1 Introduction According to the Merrian-Webster dictionary, agreement is “an arrangement as to a course of action. Compact, treaty a: a contract duly executed and legally binding b: the language or instrument embodying such a contract”. This agree- ment, this contract, assumes or implies a context in which it is going to be carried out. So, using a classical example by Castelfranchi [3] regarding the way an speech act tries to induce different motives for goal adoption in the addressee, when a general commands to a soldier ’Fire!’, the soldier could interpret such an order in different ways according to the several meanings of such expression (he could shoot, or offer to the general some matches, or look for the firemen, or burn a fire, ...), but the most probable outcome is that he wouldn’t doubt between such options and shoot his weapon, due to the context of the situation, that is, there is an implicit agreement between general and soldier regarding orders and military concepts. This paper continues the work of [2][1] that define an agreement by means of a multi-dimensional Euclidean space approach. This modeling will allow to use geometrical properties or operations to work with such agreements, and even to model the agreement problem as a constraint-satisfaction problem (CSP) and to solve it using the Hyperpolyhedron Search Algorithm (HSA 6=) [11]. This paper focuses in the way to use this modeling as a CSP by a mediator (Counselor Agent), which could be able to on-line evaluate the feasibility of such 69 an agreement, or even give some advises as the agreement negotiation evolves. In order to do that, several agreement-related interaction protocols have been defined to be used by the participant agents to reach an agreement upon a set of agreed terms. So, one of the main differences between this approach and previous works related with agreements and agents, is the focus of the approach. In works as Contract-related agents [8], the focus is in the agent, and the way he may deal with the concept of contract. The work here presented focuses in the concept of agreement as an upper abstraction over the idea of agent, organization or other entity. Modeling the agreement in this way, is what can be really useful to a counselor mediating in such agreement. The rest of the paper is structured as follows. Context Spaces are introduced in section 2. Section 3 provides a set of general definitions needed to describe the proposed protocols and algorithms. Agreement-related interaction protocols are described in section 4 and section 5 explains how the Counselor Agents works to help participant agents to reach an agreement. A simple example is shown in section 6 and, finally, section 7 summarizes this approach and concludes. 2 Context Space This term is used in the pervasive computing field related to context-aware computing [10] [9] to define a theory that models contexts based on intuitions from state-space models. In this way, the context space of an application is determined by the types of information, deemed relevant and obtainable by the designers, that is the context attributes, and the domain of possible values in each attribute. Each one of these attributes is considered one dimension in a multidimensional Euclidean space. This multi-dimensional space defines the space in which context can be perceived. This approach also includes a context algebra to express situations in terms of Context Spaces and to reason about such situations by means of a set of operators and calculations. The operators defined are the scalar difference (it calculates the degree of similarity between two comparable context states), and the intersection (it produces a new context space containing shared regions of values of the same attributes between two comparable context spaces). By representing situations and system’s state as multi-dimensional objects, it is possible to generically describe and consequently reason about context of a system. A region of acceptable values is defined as a set which satisfies some predicate, hence, it can consist of any information (numerical or non-numerical) that best reflect the context attribute behavior (in terms of possible values) for the specific situation. 70 3 Agreements Concepts This section presents some generic concepts and definitions related to agreements needed to explain the algorithms and protocols designed for a counselor agent to guide the agreement process. A more detailed definition can be found in [2][1]. 3.1 Agreement Definitions An agreement is the definition of a working context for two or more beings or entities (agents, organizations, . . . ) so that it is obtained as the result of a negotiation process. Definition 1 (Agreement). An agreement Ag is defined as Ag = (E, Cx), where: – E = {E1 , E2 , . . . En } is a set of entities participating in Ag, so that ∀Ei , i = 1, . . . n, ∃!Oi = {oij }, j = S 1, . . . m, ontology or set of concepts known by Ei – Cx = {(cxo , cxIo )|cxo ∈ i Oi , cxIo ⊆ Do }, where Do is the domain of the ontology term cxo . Thus, this context is formed by a set of ontological terms cxo with its corresponding set of valid instances cxIo that have been agreed by E. Definition 2 (Agreement Discourse Universe). The Agreement Discourse Universe of an agreement Ag –ADU (Ag)– is the whole set of concepts known by all the entities participating in the agreement. So, if Oi is the set of all the ontologies known by the entity Ei participating in the agreement Ag (i = 1..n), then D = {o/o ∈ Oi △ Ok , ∀i 6= k/i, k = 1..n} (the symmetric difference of all the agreement participating S entities’ ontologies),1 and the ADU (Ag) is defined as ADU (Ag) = i Oi − D. The ADU (Ag) is formed by all the concepts that at least one pair of entities participating in the agreement Ag share (Figure 1). If this set is empty, entities have not anything in common and they can not reach any kind of agreement. 3.2 Agreement Process An agreement Ag has two phases: 1. Reaching an agreement (defining the agreement context Cx): It comprises the negotiation process between two or more entities (belonging to E) to reach an agreement. In fact, it is decided in two levels: (a) A decision must be taken about what are the concepts around which such agreement is going to be related, that is, Cx ⊆ ADU (Ag). 1 The symmetric difference is defined as A△B = (A∩B ′ )∪(A′ ∩B), where A′ denotes the complementary set of A 71 Fig. 1. Agreement Discourse Universe and Agreement Discourse Space with the pro- jection to a 2-dimensional Agreement Space (b) After that, the specific terms of such agreement must be fixed, that is, the values or intervals for the concepts in Cx. 2. Agreement execution: In this phase each entity must fulfill the accomplished agreement executing the needed actions or calculus according to the context defined by such agreement. This execution could not even imply any kind of additional coordination. 3.3 Agreement Space As it has been stated before, an agreement can be seen as the definition of a common context. As commented in section 2 an space metaphor such as the one used in Context Spaces can be used to express such contexts. So, an agreement space can be defined. Definition 3 (Agreement Discourse Space). The Agreement Discourse Space of an agreement Ag ADS(Ag) is defined by considering as a dimension (in an Euclidean space) each concept included in an Agreement Discourse Universe of an agreement Ag. That is, the ADS(Ag) is an n-dimensional space, where n is the cardinality of the ADU (Ag) (number of common terms). Figure 1 shows an example with 3 dimensions, where the points represent the possible combination values of such space (assuming a discrete domain for every dimension). Definition 4 (Agreement Space). According to the first phase of an agree- ment, a decision must be taken about the concepts, that is, the dimensions in which the agreement will be expressed. So, an Agreement Space is a projection of the Agreement Discourse Space onto the dimensions defining the agreement. That is, this space will be defined by the features the different entities Ei making the agreement are going to negotiate (Cx), each one of such features defining a dimension in this space (∀i : di ∈ dim(Ei , Ag)). 72 In order to be possible an agreement Ag, for all entity Ei participating in the agreement there will exist at least one other participating entity Ej so that dim(Ei , Ag) ∩ dim(Ej , Ag) 6= 0. The Agreement Space is, then, the result of eliminating the unnecessary dimensions that are not relevant for the agreement. For example, in Figure 1 the y dimension is not relevant, so the way the entities will deal with y concept is not controlled by the agreement, and the Agreement Space is reduced to the marked 2-dimensional area, that is, the projection over x and z dimensions of the defined ADS. In this way, the outcome of the first phase of the agreement will be the definition of this Agreement Space, fixing the satisfying values for each one of the different dimensions comprising this space. The second phase of the agreement will be to carry out the execution of the agreement taking into account that it has to be carried out inside the previously defined Agreement Space. Definition 5 (Local Agreement Space). The Local Agreement Space for entity Ei in the agreement Ag is defined as the projection over the dimensions of interest of entity Ei in such Agreement Space. 4 Agreement-Related Interaction Protocols WS-Agreement[6] is a standard proposed by the Global Grid Forum (GGF) that includes the definition of a simple interaction protocol to support one- to-one negotiation, with the likely aim to support different mechanisms in the future through definition of multiple interaction protocols. So, the work by [7] for what they called service agreement where one consumer of a service chooses one service provider from n available by means of the FIPA Iterated Contract Net Interaction Protocol[5]. In this proposal, a Counselor Agent (see Section 5) mediates in the agreement process in order to help the participant agents to reach an agreement related to a common vocabulary. The mediation is achieved though a set of services available to all participants that help to find a common Agreement Space, inside which agents can interact being ensured that the terms of the agreement are fulfilled. This section presents two new interaction protocols that has been defined to deal with the services offered by the Counselor Agent: ADU Definition and Agreement Counselor, that will be addressed by the ADU Interaction Protocol and the Mediated-Agreement Interaction Protocol, respectively. 4.1 ADU Interaction Protocol (ADUIP) This interaction protocol controls the service of the Counselor Agent related to the definition of the Agreement Discourse Universe of a group of entities, that is, the common vocabulary shared by such entities (see Definition 2). This protocol describes a general phase, previous to the agreement itself, that can be used in many other situations in which establish a common vocabulary is needed. Figure 2 shows this protocol, that is composed of the following steps: 73 Initiator Counsellor Participant i call for counsellor m j <= n not-understood n k <= n - j refuse l=n-j-k agree failure-no-match deadline request not-understood refuse agree call for agreement p r <= p not-understood p s <= p - r refuse t=p-r-s agree failure-proxy t t inform t Fig. 2. ADU Interaction Protocol 1. An Entity Ei sends a Call For Counselor to all entities offering the service of Counselor indicating an AgreementID. 2. If any Counselor agrees to Ei , then Ei will send a Request for Counselor to one of them, Cj , that will serve as counselor for agreement AgreementID. 3. Counselor Cj sends a Call For Agreement to all entities in the system, in- dicating an Agreement ID and a deadline to this phase of joining to the agreement. 4. Each entity Ek that wants to participate in the agreement will send to Cj an agree message with his ontology before deadline is met. 5. After deadline, Cj will calculate the ADU using the ontologies received from the entities that will participate in the agreement, communicating them if the ADU is empty that there is a failure, because there is no possibility of agreement. 74 The ADU Interaction Protocol is only focused on provide a framework to participant agents for exchanging their ontologies (or fragments of them). It does not try to solve the ontology alignment problem, which is out of the scope of this paper. 4.2 Mediated-Agreement Interaction Protocol After the existence of a common vocabulary is ensured by ADU protocol, the participant entities can negotiate the terms of any agreement. A two-phases protocol is proposed to reach an agreement among a group of entities (agents or organizations) mediated by a counselor. The final goal of this protocol is to construct the Agreement Space by means of the following steps: 1. Defining the context: It will be formed by the dimensions of the Agreement Space, that is, the concepts that will be dealt in the agreement, and that will be part of the ADU (in fact, this context will be a projection of the ADU in the dimensions of the Agreement Space). 2. Defining the agreement terms, that is the different values or intervals for the dimensions defining the context that will define the Agreement Space. This process will be done by applying one by one the constraints suggested by the participants. Moreover, it is regulated by a mediator—the Counselor—which guides the negotiation process to achieve an accord among the participants. Its main task is to check that any additional constraint is consistent with the current constraint set. That is, if they formed a convex hull. The protocol here presented is described from the Counselor point of view, and, its purpose is to help in the Agreement Space definition. This protocol (see Figure 3a) is divided into two main parts: the first one deals with the definition of the context, and the second one with the definition of the agreement terms (see Figure 3b). 1. Context Definition: An initiator requests the Counselor for an agreement. (a) An Entity Ei sends a Call For Agreement with AgreementID to the Counselor Agent that has previously calculated the ADU, indicating that he wants to begin an agreement with some or all the other entities involved in such ADU. (b) If the Counselor agrees to Ei , then he sends a Call For Context to all the entities associated to the previous ADU, indicating an Agreement ID and a deadline to this phase of joining to the agreement. (c) Each entity Ek that wants to participate in the agreement will send to the Counselor an Agree message with his agreement dimensions (that is, the concepts he is interested in negotiate for the agreement, and that are part of the previous ADU) before deadline is met. 2. Agreement Terms Definition: The former initiator is turned into another participant and the Counselor takes the initiative. 75 Initiator Counsellor Participant i (a) Counsellor Participant i (b) inform-context p call for agreement not-understood call-for-terms p p refuse inform-term agree [¬consistent] reject call for context p [redundant] r <= p not-understood reject p s <= p - r refuse [consistent] accept t=p-r-s agree call-for-terms proxied-communicative-act inform-done agreement terms failure subprotocol reply-message Fig. 3. (a) Mediated-Agreement Interaction Protocol (b) Agreement terms definition subprotocol (a) The Counselor Informs to all the entities of the dimensions of the agree- ment (from the general ADU, different concrete agreements could take place, between different or the same entities). (b) The Counselor sends a Call For Terms message to all the participating entities with the proper AgreementID to ask for agreement terms. (c) Each one of the participating entities will send an Inform message to the Counselor for each one of the negotiation terms (in the form of a constraint) that he is interested in. Such messages will be processed by the Counselor to build the AS. (d) For each Inform message, the Counselor will respond either with a Reject message, if the new term is not consistent with the agreement or is redundant, or with an Accept message if the new term is consistent. (e) The process of receiving and analyzing new agreement terms continue till there is no more terms (according to a deadline-based method). (f) The Counselor informs the participating entities either the final agree- ment terms, or that the agreement has not been possible. The final result is the definition of the Agreement Space, modeled as a hyper- polyhedron formed by all accepted constraints (agreement terms). During the execution of the agreement, all interactions have to be inside this space as the participants have agreed. 76 5 Using Agreement Spaces for Mediators It is not so strange, when trying to reach an agreement to use a mediator to, not only watch over the fulfillment of the different processes involved in reaching an agreement, but also to counsel about the final values or intervals of the agreement due to its global unbiased view of the agreement. So, this figure is also interesting when trying to automatize the agreements, that is, to carry out agreements between agents, virtual organizations or other pieces of software. Different approaches to automatic mediators can be seen in the literature such as the PERSUADER system [12] or AutoMed [4]. 5.1 Agreement Space as a CSP As it was stated before, after the Agreement Space is defined, the different enti- ties involved in the agreement must fix (possibly through a negotiation process) some concrete values or intervals for the different dimensions comprising the Agreement Space. For such negotiation, each one of these entities will have some intervals of satisfying values for the different dimensions it is interested in. These satisfying intervals may be expressed as constraints for the different dimensions that should be satisfied for the agreement. So, if this first phase of an agree- ment is seen from a mediator point-of-view, it can be seen as the solution of a Constraint-Satisfaction Problem (CSP), defined by the whole set of constraints of the different entities. Being the Agreement Space n-dimensional, each one of such constraints defines a (n − 1)-dimensional plane. As the Agreement Space is defined by the intersection of all such planes, it can be described how such space is by studying such planes. Therefore, this agreement mediator should be able to detect if an agreement is possible, checking if there exists an Agreement Space as a result of all these constraint planes intersection. The idea is to define the Agreement Space as the solution space of a CSP and to build an agreement by applying entities’ conditions as constraints in the space (applying the HSA 6= [11] algorithm to build the hyperpolyhedron modeling the CSP that will define the Agreement Space). A solution is reached if all constraints are consistent. Furthermore, if the resulting space is convex then it can be ensured that all interactions are inside the Agreement Space. As it is an agreement, an Agreement Space (AS) is defined by a set of entities and their context (E, Cx), where the context is composed by variables, their domains an all the constraints. In this way, the AS is defined by extending a common CSP definition. 5.2 Counselor Algorithm The Counselor has the responsibility of helping the participants in the agreement to find the Agreement Space, considering it as a CSP. It is an iterative process that adds new constraints one by one, guaranteeing that the new constraint is Pnconsistent with the previous ones. Constraints are inequalities of the form i=0 ai xi ≤ b, where xi are the variables of the CSP. The set of all constraints 77 defines an hyperplane and which union defines the limits for the valid values for all the variables involved in the agreement. The participants in the agreement will take values inside the resulting hyperpolyhedron. Using the mediated-agreement protocol defined in Section 4.2, the Coun- selor obtains the constraints from the participants and creates the Agreement Space using a variant of HSA 6= algorithm. This algorithm is applied inside the Agreement Terms Definition subprotocol (see Figure 3b) each time a new con- straint Ci is received from a participant (by means of an Inform message). So the Agreement Space is incrementally constructed from scratch. If Ci is inconsistent or redundant, the agent that proposed it is informed by a Reject message. The agent can redefine the constraint and submit a new one if necessary. Consistence and redundancy are checked using the HSA 6= algorithm. Ba- sically, when a new constraint Ci arrives the algorithm checks if each vertex of the current hyperpolyhedron satisfies Ci . If none vertex satisfy Ci then the constraint is inconsistent and it is rejected. That is because the space defined by the constraint does not contain any of the vertex of the hyperpolyhedron. On the other hand, if all vertex satisfy Ci then the constraint is redundant. That is because the complete hyperpolyhedron is included inside the space defined by the constraint. In any other case, the constraint is consistent and it is added to the hyperpolyhedron. When all constraints are added to the Agreement Space and it is not empty then there is an agreement among all the participants. If the Agreement Space is not empty, then it is ensured that it is convex, so any ’movement’ between two points inside this space is always inside it. Therefore, it is guaranteed that any negotiation process produced inside the agreement terms will never violate the agreement. The following section presents an example of reaching an agreement using a Counselor Agent, interacting with the above presented interaction protocols, focusing in the Agreement-terms definition subprotocol. 6 Example Let it be a set of agents interested in taking piano classes. The group is formed by one teacher and two students. They agree to negotiate over three dimensions: the number of classes (n), its duration (d) and its price (p). Initially, participants have their own preferences (modeled as constraints). – Teacher 1. at least 10 classes: n ≥ 10 2. duration between 60 and 120 min: d ≥ 60 and d ≤ 120 3. at least 20 euros/hour: p ≥ 20 – Student 1 1. no more than 20 classes: n ≤ 20 2. less than 30 euros/hour: p ≤ 30 78 – Student 2 1. minimum 15 classes: n ≥ 15 2. duration between 45 and 90 min: d ≥ 45 and d ≤ 90 Assuming that agents have some common vocabulary (checked with the ADU protocol) and they defined the above three dimensions as the agreement context, then the Counselor asks them for the terms of the agreement. There is no rule about the order in which agents propose the terms (constraints) nor the order in which they arrive to the Counselor. Depending on it, one constraint can be detected as redundant or just as a refinement of an existing one. But it does not affect to the final Agreement Space. Agent Mess Param Agent Mess Param Agent Mess Param 1 C inform n, d ,p 11 C call-for-terms 21 T inform d ≤ 120 2 C call-for-terms 12 T inform d ≥ 60 22 C accept d ≤ 120 3 T inform n ≥ 10 13 C accept d ≥ 60 23 C call-for-terms 4 C accept n ≥ 10 14 C call-for-terms 24 T inform p ≥ 20 5 C call-for-terms 15 S1 inform n ≤ 20 25 C accept p ≥ 20 6 S1 inform p ≤ 30 16 C accept n ≤ 20 26 C call-for-terms 7 C accept p ≤ 30 17 C call-for-terms 27 S2 inform d ≤ 90 8 C call-for-terms 18 S2 inform d ≥ 45 28 C accept d ≤ 90 9 S2 inform n ≥ 15 19 C reject d ≥ 45, red 29 C inform-done 10 C accept n ≥ 15 20 C call-for-terms Table 1. Example of Agreement Terms Definition This is a very simple case, in which restriction are defined over one dimension, but it is enough to follow and understand the process of construction of the Agreement Space. Let be C the counselor, T teacher, S1 student 1 and S2 student 2. An example of the process can be followed in Table 1. In the sequence of messages on this table it can be seen how the Counselor communicates to the rest of participants the context of the agreement (message 1). After that, the participants send their own constraints one by one (messages 3, 6, 9, 12, 15, 18, 21, 24 and 27) and the Counselor accepts or rejects them. For example, in message 18, S2 proposes a constraint that is redundant, since one more restrictive has been accepted in 12-13. But restrictions proposed in messages 15 and 27 have been accepted because they refine (they are more restrictive) that the ones accepted in 6-7 and 21-22 respectively. 7 Conclusions Context Spaces seem to be a valid approach to model agreements and allows to use well known techniques to solve the task of reaching an agreement and controlling its subsequent execution. The agreement is modeled as an object in the Euclidean space. The problem of defining the space associated to an agreement can be seen as a CSP, since the agreements conditions can be modeled as constraints and the 79 agreement is expressed as a set of restrictions over a set of data. The conjunction of all these restrictions will define an convex hyperpolyhedron delimiting the agreement space, that is, the space where all the computations fulfilling such agreement will be carried out, the context of such computations. Mediators can be used during the negotiation process to reach an agreement to check that any additional constraint keeps this space convex, along with con- trolling the feasibility of the agreement. For doing that, mediators can suggest more relaxed or more strict constraints in order to maintain the consistence of the space and the possibility of an agreement. This paper has presented not only the advantages of using such a Mediator or Counselor in reaching an agreement, but also the way this Counselor works and how to interact with him by means of some interaction protocols specifically designed for agreement reaching processes. As future work, the dynamic of the agreement is going to be studied, because to guarantee an agreement, besides the existence of the agreement space, the convergence of individual negotiation processes has to be guaranteed to avoid systems that oscillate without ending in a concrete agreement for some initial situations. References 1. C. Carrascosa and M. Rebollo. Modelling agreement spaces. In IBERAMIA 2008 Workshop on Agreement Technologies (WAT 2008), pages 79–88. Marc Esteve, Adriana Giret, Alberto Fernández, Vicente Julián, 2008. 2. C. Carrascosa and M. Rebollo. Agreement spaces for counselor agents (short pa- per). In Proc. of 8th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2009). Decker, Sichman, Sierra and Castelfranchi (eds.), May, 10-15, 2009, Budapest, Hungary, To appear, 2009. 3. C. Castelfranchi. Prescribed mental attitudes in goal-adoption and norm-adoption. Artificial Intelligence and Law, 7–1:37–50, 1996. 4. M. Chalamish and S. Kraus. Automed: an automated mediator for bilateral negoti- ations under time constraints. In AAMAS ’07: Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, pages 1–3, New York, NY, USA, 2007. ACM. 5. FIPA. FIPA Iterated Contract Net Interaction Protocol Specification. FIPA, 2001. 6. G. Forum. Web services agreement specification (ws-agreement). G. G. Forum, 2004. 7. F. Ishikawa, N. Yoshioka, and S. Honiden. Incorporating agreements on service options into bpel-based services. In CIMCA ’05: Proceedings of the International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce Vol-1 (CIMCA-IAWTIC’06), pages 796–803, Washington, DC, USA, 2005. IEEE Computer Society. 8. J. Knottenbelt. Contract Related Agents. PhD thesis, Department of Computing, Imperial College London, December 2006. 9. A. Padovitz, C. Bartolini, A. Zaslavsky, and S. W. Loke. Extending the context space approach to management by business objectives. In HP OpenView University 80 Association (HP-OVUA), 12th Workshop, Porto, Portugal (FEUP), 10 - 13 July 2005, 2005. 10. A. Padovitz, S. W. Loke, and A. Zaslavsky. Towards a theory of context spaces. In Workshop on Context Modeling and Reasoning (CoMoRea), in C Das and M Kumar (eds), Proceedings of the Second IEEE Annual Conference on Pervasive Computing and Communications Workshop, Orlando Florida, 14 - 17 March 2004, pages 38–42, USA, 2004. IEEE Computer Society. 11. M. A. Salido, A. Giret, and F. Barber. Constraint satisfaction by means of dynamic polyhedra. In Operational Research Proceedings 2001, pages 405–412. Springer Verlag, 2001. 12. K. P. Sycara. Resolving goal conflicts via negotiation. In Proceedings of AAAI-88, pages 245–250, 1988. 81