Towards Interaction Protocol Operations for Large Multi-agent Systems

Towards Interaction Protocol Operations for Large Multi-agent Systems Joaqu´ın Pe˜na, Rafael Corchuelo, and Jos´eLuisArjona Dpto. de Lenguajes y Sistemas Inform´aticos Avda. de la Reina Mercedes, s/n. Sevilla 41.012 (Spain) [email protected],www.lsi.us.es/˜tdg Abstract. It is widely accepted that role-based modelling is quite adequate in the context of multi-agent systems (MAS) modelling techniques. Unfortunately, very little work has been reported on how to describe the relationships between several role models. Furthermore, many authors agree on that protocols need to be encapsulated into high-level abstractions. The synthesis of role models is an operation presented in the OORAM methodology that allows us to build new role models from others in order to represent the interrelations they have. To the best of our knowledge this operation has to be performed manually at protocol level and works with protocols expressed by means of messages. In this paper, we present two algorithms to extract the protocol of a role from the protocol of a role model and vice versa that automate the synthesis or role models at the protocol level. Furthermore, in order to deal with protocol descriptions in a top down approach both operations work with protocols expressed by means of an abstraction call multi-role interaction (mRI). 1 Introduction When a large system is modelled, complexity becomes a critical factor that has to be dealt with properly. In order to tackle complexity G. Booch recommended several powerful tools such as: Decomposition, Abstraction, and Hierarchy [5]. In addition, these tools were also presented as appropriate for Agent-Oriented Software Engineering (AOSE) for complex MAS, and were adapted to this field in [18] as follows: –Decomposition: It is based on the principle divide and conquer.Itsmain advantage is that it helps to limit the designers scope to a portion of the problem. –Abstraction: It is based on defining simplified models of the system that emphasises some details and avoid others. It is interesting since it limits the designer scope of interest and the attention can be focused on the most important details. –Organisation/Hierarchy: It relies on identifying and managing the relationships between the various subsystems in the problem. It makes it possible to group together various basic components and deal with them as higher-level units of analysis, and, provides means of describing the high-level relationships between several units. Unfortunately, we think that these tools have not been carefully applied in the approaches that are appearing in this field. We have identified several problems in current methodologies that our approach tries to solve. On the one hand, there exists a huge semantic gap in MAS protocol description methodologies because most of them first identify which tasks have to be performed, and then use low level descriptions such as sequences of messages to detail them. Although these messages may represent a high level view of a protocol, which shall be refined later, the tasks that are performed are formulated as a set of messages. This representation implies that the abstraction level falls dramatically since a task requires several messages to be represented. For instance, an information request between two agents must be represented with two messages at least (one to ask, and another to reply). This introduces a semantic gap between tasks and their internal design since it is difficult to identify the tasks represented in a sequence of messages. This representation becomes an important problem regarding readability and manageability of large MAS and can be palliated using the abstraction tool presented above. On the other hand, in AOSE is widely accepted that describing the system as a set of role models that are mapped onto agents is quite adequate since it applies the decomposition tool [6,12,21,19,22,23,34]. Unfortunately, we have failed to find methodologies for MAS that use some interesting ideas about role modelling presented by Reenskaug and Andersen in the OORAM methodology [1,27]. Obviously, when we deal with a complex and large systems several role models may appear, and usually, they are interrelated. The role model synthesis operation [2], attempts to detail how role models are related, thus applying the organisation tool. This operation consists of describing new synthesised role models in terms of others. In a synthesised role model, new roles may appear and synthesised roles may also appear as aggregation of others. Unfortunately, OORAM also suffers from the first problem we have shown above since it deals with behaviour specification in terms of messages. In this paper, we provide the first step towards the solution of these problems enumerated above using the tools proposed by Booch: i) In order to apply the abstraction tool, we have defined an abstraction called multi-role interaction (mRI) which encapsulates the interaction protocol (hereafter protocol) corresponding to a task that is performed by an arbitrary number of roles. mRIs are used as first modelling class elements to represent an abstract view of the protocol of a role model which can be refined with the techniques proposed in [25]. ii) In order to apply the organisational tool, we have also defined two operations on protocols (described in terms of mRIs) to automate and ease the synthesis operation since it operates on interaction protocols of a role instead of with the whole interaction protocol of a role model: the first one, called decomposition, infers a role protocol from a role model protocol automatically; and the second one, that we called composition, infers a role model protocol from a set of role protocols automatically. This paper is organized as follows: in Section 2, we present the related work and the advantages of our approach over others; in Section 3, we present the example we use; in Section 4, we present the protocol abstraction we have defined; in Section 5, we show how to describe the protocol of a role model; in Section 6, we present the algorithms to compose and decompose protocols, and, in Section 7, we present our main conclusions. 2 Related Work In the context of distributed systems many authors have identified the need for advanced interaction models and have proposed multi-object interactions that encapsulates a piece of protocol between several objetcs [24]. Furthermore, most object-oriented analysis and design methods also recognise the need for coordinating several objects and provide designers with tools to model such multi-object collaborations. Different terms are used to refer to them: object diagrams [4], process models [7], message connections [8], data-flow diagrams [28], collaboration graphs [32], scenario diagrams [27], collaborations [13,29]. In MAS methodologies many authors have also proposed abstraction to model coordinated actions such as nested protocols [3], interactions [6] or micro-protocols [22], and so on. Unfortunately, the abstractions presented above are usually used to hide unnecessary details at some level of abstraction, reuse the protocol descriptions in new systems, and improve modularity and readability; however, most designers use message–based descriptions. We think that most AOSE approaches model protocols at low level of abstraction since they require the designer to model complex cooperations as messagebased protocols from the beginning. This issue has been identified in the GAIA Methodology [33], and also in the work of Caire et. al. [6], where the protocol description process starts with a high level view based on describing tasks as complex communication primitives (hereafter interactions). We think that the ideas presented in both papers are adequate for this kind of systems where interactions are more important than in object-oriented programming. As the methodologies GAIA and Caire’s Methodology, we also use interactions (mRIs) to deal with the first stage of protocol modelling. In the GAIA methodology, protocols are modelled using abstract textual templates. Each template represents an interaction or task to be performed between an arbitrary number of participants. In [6], Caire et al. propose a methodology in which the first protocol view is a static view of the interactions in a system. Later, the internals of these interactions are described using AUML [3]. Unfortunately, the operations we propose are difficult to be integrated with these methodologies. The reason why this happens is that we have found neither an interaction model for MAS able to describe formally a sequence protocol abstractions, nor operations on these high level protocol definitions. GAIA protocol descriptions, for example, are based on textual description thus it is difficult to reason formally on them. In Caire’s methodology, it is not shown how to sequence interactions. Although Koning et al. describe the sequence of execution of their abstraction using a logic-based formulae (CPDL), which consists of an extension of transition function of Finite State Automata (hereafter FSA), they do not define operations to operate with protocols. In our approach, we also define the sequence of mRI by means of Finite State Automaton (FSA) which has been also used by others authors at message level. We have chosen FSAs because this technique has been proved to be adequate for representing the behaviour of reactive agents [11,14,16,22]. Regarding the operations we present to the best of our knowledge the decomposition operation has not been defined before in this context. This operation can be useful for reuse, performing synthesis of role models since it operates with the protocol of a role instead of with the whole protocol and to map several protocol onto the same agent class. Unfortunately, in OORAM methodology such operation has to be applied manually to UML sequence diagrams. The inverse operation, that we call composition, has been already defined by other authors, but, to the best of our knowledge, they do not use interaction with an arbitrary number of participants as we do [9,16,30,31]. This operation can be useful for building new role models reusing already defined role protocols stored in a behaviour repository, performing tests for adaptive behaviours [16], deadlock detection or to understand easily the protocol of a new role model [25]. Unfortunately, in OORAM this operation has to be also performed manually. 3 The Example To illustrate our approach, we present an example in which a MAS delivers satellite images on a pay per use basis. We have divide the problem into two role models: one whose goal is obtaining the images (images role model)andthe other for paying them (purchase role model). This decomposition of the problem allow us to deal with both cases separately. In the Images role model the user (role Client) has to specify the images features that he or she needs (resolution, target, format, etcetera). Furthermore, we need a terrestrial centre (role Buffer) to store the images in a buffer because the throughput of a satellite (role Satellite) is higher than the average user can process and we need to analyse images features in order to determine their total price which is the goal of role Counter. In the Purchase role model we need to contact the payment system to conclude the purchase. It involves three different roles: a customer role (Customer), a customer account manager role (Customer’s Bank), and a terrestrial centre account manager role (Buffer’s Bank). When a customer acquires a set of images he uses his or her debit–card to pay them, the agent playing role Customer agrees with a Customer’s Bank agent and Buffer’s Bank agent on performing a sequence of tasks to transfer the money from the customer account to the buffer account. If the Customer’s Bank cannot afford the purchase because it has not enough money, the Customer’s Bank agent then pays on hire–purchase. 4 Our Protocol Abstraction: Multi-role Interactions The description of the protocol of a role model is made by means of mRIs. This provides an abstract view of the protocol that makes it easier to face the problem at the first stages of system modelling. Thus, we do not have to take into account all the messages that are exchanged in a role model in stages where these details have not been identified clearly. A multi-role interaction (mRI) is an abstraction that we propose to encapsulate a set of messages for an arbitrary number of roles. At conceptual level, an mRI encapsulates each task that a role model should execute to perform its goal. These tasks can be inferred in a hierarchical diagram [20] where we can identify which tasks shall execute each role model. mRIs are based on the ideas presented in two interaction models for distributedsystems[15,10].Wehavemadethatchoicebecausebothmodelshave a set of formal tools that may be used for MAS systems improving the power of our approach, this allows, to perform deadlock testing and automatic interaction refinements [25] or efficient distributed implementations [26]. The definition of an mRI is: {(G(β)}&mRI name[r1,r 2,...,r N] Where mRI name is an unified identifier of the interaction and r1,r 2,...,r N aretherolesthatexecutethemRImRI name.βis the set of beliefs of agents playing the roles implied in the mRI and G(β) is a boolean condition over β. This guard is partitioned in a set of subconditions, one for each role. G(β)holds iff the conjunction of all subconditions of each role is true. The idea behind guarded interactions has been adapted from the interaction model in which our proposal is based; furthermore, Koning et al. also adopt a similar idea. It promotes the proactivity of agents as we can see in [10,22] because agents are able to decide whether executing an mRI or not. Thus, an mRI xshall be executed if the guard of the mRI holds and all roles that participate on it are in a state where the xis one of mRIs that can be executed. Furthermore, all of them must not be executing other mRIs since the interaction execution is made atomically and each role can execute only one mRI atthesametime.Forexample,ifweconsiderFSAsinFigure3afterexecuting an mRI sequence that makes the the Satellite to be in state 1, the Buffer in state 4, the Client in state 8 and the Counter in state 11, if all the guards holds, we can execute Receive,Send or LastSat. In this case LastBuffer cannot be executed because it requires the Buffer to be in state 5. Finally, for each interaction we should describe some details that we enumerate roughly below since it is not the purpose of this paper. To describe an mRI internally, we should include the sequence of messages using AUML. Furthermore, we may use coordination or negotiation patterns from a repository if its possible (FIPA has define a repository of interaction patterns 1) and an objective 1http://www.fipa.org/specs/fipa00025/XC00025E.html Client Client Satellite Satellite Buffer Buffer Counter Counter Receive Send Last_Buffer Last_Sat Ask Fig. 1. Collaboration diagram of Images role model function that determines which of available mRIs shall be better to execute if several of them can do so at the same moment. Regarding the example, the description of one of the mRIs of the Images role model which it is used to ask for images (see Figure 3) is: {Counter.Connected(Buffer.ID())&Counter.enable()}& ask[Client,Buffer,Counter] TherestofthemRIsintheImages role model are: ask, which is used to ask for images, send, which sends an image from the Satellite to the Buffer, receive, which sends an image from Buffer to Client,LastSat, which indicates the last image for transferring from Satellite to Buffer and stores information about images in a log file, and, LastBuffer, which indicates the last image for transferring from Buffer to Client and makes the Counter to calculate the bill. The static relation between these mRIs and the roles that perform them is represented in the collaboration diagram in Figure 1. 5 Modelling the Protocol of a Role Model Once the roles and its mRIs have been identified we must describe how to sequence them. Thus, the protocol of a role model is defined as the set of sequences of mRIs execution it may performs. We can use two equivalent representations to describe the protocol of a role model (see Figure 2): –Representing the protocol of the role model as a set of FSAs, one for each role (see Figure 3). Thus, in a role model with NroleswehaveNFSAs Counter Satallite Buffer Satellite Images Role Model Images Role Model Composition/ Decomposition Client 1,3,7,10 1,4,8,11 2,5,8,11 2,5,9,12 1,3,7,10 1,4,8,11 2,5,8,11 2,5,9,122,5,9,12 1 2 1 22 Counter Client Buffer 10 11 12 10 11 1212 7 8 6 7 8 66 3 4 5 6 3 4 5 66 Role Repository Fig. 2. Composition/Decomposition of protocol for the Images role model Aiwhere each Ai=(Si,Σ i,δ i,s 0 i,F i), where Siis a set of states, Σiis a vocabulary where each symbol σ∈Σirepresents an mRI, δi:Si×Σi→Si is the transition function that represents an mRI execution, s0 i∈Siis a initial state and Fi⊆Siis the set of final states. Thus, the set of words produced by this set of FSAs is set of possible traces of execution of mRIs. AllthisFSAsexecutesitstransitionscoordinatelyasitisshowninSection4. Roughly speaking, when an mRI is executed by more than one role we must perform a transition in all of its participant roles. Each of these transitions represents the part of the mRIs that each of them performs. Whereby, to execute an mRI we must transit from one state to another in all the roles that participate in it. –Representing the protocol of the role model as a whole using a single FSA for all the roles (see Figure 4). This FSAs is of the form B=(S, Σ, δ, s0,F) where Sis a set of states that represents one state for each FSA of roles, Σ is a vocabulary where each symbol σ∈Σrepresents an mRI, δi:S×Σ→S is the transition function that represents an mRI execution, s0 i∈Siis the initial state and F⊆Sis the set of final states. Thus, the set of words produced by this FSA is set of possible traces of execution of mRIs. If we are dealing with a new role model, it may be more adequate to use a single FSA than one for each role since we see the problem in a centralised manner. The protocol for the Images role model by means of a single FSA is showninFigure4. Once the protocol of all role models in our system have been described we can synthesise those role models that are interrelated. In our example, both role models are interrelated since the images obtained in the Images role model have to be paid using the Purchase role model. In order to synthesise role models, we have to identify which roles are related and we have to merge their protocols to create the new synthesised role model. In our example, the synthesised role model Purchase-Images role model in Figure 5 is build by creating a new role where the protocol of the Customer and the Client is merged. 3 4 5 66 Ask Send Receive LastSat LastBuffer Send 7 8 66 Ask Send LastBuffer 10 11 1212 Ask Send LastBuffer 1 22 Receive LastSat Satellite Buffer Client Counter Receive* · LastSat Ask · (Send+Receive)*· · LastSat · Send* · LastBuffer Ask · Send*· · LastBuffer Ask · Send* · LastBuffer Fig. 3. FSAs of roles of Images role model 1,3,7,10 1,4,8,11 2,5,8,11 2,5,9,122,5,9,12 Ask Send Receive LastSat LastBuffer Send Fig. 4. FSA of Images role model Thus, we have to know the protocol of both the Customer and the Client in order to build the new role model. This can be done using the decomposition operation. Once we have built the protocol of the Client/Customer role, it is difficult to infer mentally which shall be the protocol of the new synthesised role model. Then, we can use the composition operation to infer it. In addition, we can perform deadlock testing in order to assure the correctness of the new protocol [25]. 6 Composition and Decomposition of Interaction Protocols These operations perform a transformation from one representation of protocol to another. As it is shown in the followings sections, these operations do not take guards into account. As we have shown above, a guard allows agents to decide if they want to execute an mRI or not. Thus, guards can make some execution traces of the protocol impossible. Unfortunately, we cannot determine this at design time. Even, if we are dealing with adaptive agents these decision can change at runtime. Thus, in both operations, we work with the set of all possible traces leaving proactivity as a runtime feature. 6.1 Composition The composition operation is an algorithm that builds a role model FSA from a set of FSA of roles obtained from a behaviour repository or from synthesis of role models. To represent the role protocol of each role in a role model we use the FSAs Ai=(Si,Σ i,δ i,s 0 i,F i)(i=1,2,...,N). Thus, the composition algorithm is defined as a new FSA of the form B=(S, Σ, δ, s0,F), where: –S=S1×...×SN, –Σ=n i=1 Σi, –δ(a, (s1,...,s n)) = (s 1,...,s  N)iff∀i∈[1..N]·(a∈ Σi∧si=s i)∨ ∨(a∈Σi∧δ(a, si)=s i), –s0=(s0 1,...,s 0 N), and –F=F1×...×FN. This algorithm builds the new FSA exploring all the feasible executions of mRIs. Their states are computed as the cartesian product of all states. Each state of this FSA is formed by a N-tuplethatstoresastateofeachrole.To execute an mRI, we have to preform it from a tuple-state where the mRI can be execute to change to a new tuple-state where the states of roles implied in the mRI shall only change. Thus, for each new tuple-state we check if an mRI may be executed (all their roles can do it from its corresponding state in the tuple-state); if so, we add it to the result. Finally, the final state of the role model FSA is formed of all possible combinations of final states of each Aiand the initial state is a tuple with the initial state of each Ai. Intuitively, it is easier to comprehend a protocol if it is described by means of a single FSA than if we use a set of them. Furthermore, we can perform deadlocktestingonittoassurethatthesynthesiswehavemadeisdeadlockfree and results in what we have thought when we synthesised them. Furthermore, this representation is easier to understand than several separated FSAs. With this operation, we can obtain automatically the FSA in Figure 4 that represents the protocol executed by the FSAs in Figure 3 of Images role model. 6.2 Decomposition To obtain the protocol of a role we must take into account the mRIs a role execute only. That is to say, we can take all the possible traces that the FSA of the role model produces and ignore the mRIs that the role does not execute. For instance, if we take the a trace (Ask, Receive, Receive, Send, LastSat, Send, LastBuffer) from the FSA of the Images role model, the trace that the role Satellite executes is (Receive, Receive, LastSat) since it participates only in mRIs Receive and