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 agreement, 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 =) [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 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.
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.
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].
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:
.n} (the symmetric difference of all the agreement participating entities' ontologies), 1 and the ADU (Ag) is defined as
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.
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). (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.
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 agreement, 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 E i making the agreement are going to negotiate (Cx), each one of such features defining a dimension in this space (∀i :
In order to be possible an agreement Ag, for all entity E i participating in the agreement there will exist at least one other participating entity E j so that dim(E i , Ag) ∩ dim(E j , Ag) = 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 E i in the agreement Ag is defined as the projection over the dimensions of interest of entity E i in such Agreement Space.
WS-Agreement [6] is a standard proposed by the Global Grid Forum (GGF) that includes the definition of a simple interaction protocol to support oneto-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.
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 1. An Entity E i sends a Call For Counselor to all entities offering the service of Counselor indicating an AgreementID. 2. If any Counselor agrees to E i , then E i will send a Request for Counselor to one of them, C j , that will serve as counselor for agreement AgreementID. 3. Counselor C j sends a Call For Agreement to all entities in the system, indicating an Agreement ID and a deadline to this phase of joining to the agreement. 4. Each entity E k that wants to participate in the agreement will send to C j an agree message with his ontology before deadline is met. 5. After deadline, C j 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.
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.
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). 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). (a) An Entity E i 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 E i , 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 E k 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. (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 agreement terms, or that the agreement has not been possible.
The final result is the definition of the Agreement Space, modeled as a hyperpolyhedron 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.
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].
As it was stated before, after the Agreement Space is defined, the different entities 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 agreement 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 = [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.
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 consistent with the previous ones. Constraints are inequalities of the form n i=0 a i x i ≤ b, where x i are the variables of the CSP. The set of all constraints 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 Counselor obtains the constraints from the participants and creates the Agreement Space using a variant of HSA = algorithm. This algorithm is applied inside the Agreement Terms Definition subprotocol (see Figure 3b) each time a new constraint C i is received from a participant (by means of an Inform message). So the Agreement Space is incrementally constructed from scratch.
If C i 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 = algorithm. Basically, when a new constraint C i arrives the algorithm checks if each vertex of the current hyperpolyhedron satisfies C i . If none vertex satisfy C i 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 C i 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. 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. 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.
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 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 controlling 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 using such a 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.
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).
-