Multi-Agent Organizational Structure: specification and validation

Multi-Agent Organizational Structure: specification and validation | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Multi-Agent Organizational Structure: specification and validation Issam Bouslimi This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-4197325/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract To design complex Multi-Agent Systems (MAS), the use of high-level abstraction concepts such as roles, protocols, and groups, makes the task relatively easier and closer to the reality of the system or domain that we want to simulate or create. These concepts were introduced through the multi-agent Organizational Models (OM) which can be seen at two levels: i) an abstract level which is the Organizational Structure (OS) and ii) a concrete level which is the Concrete Organization (CO) to be deployed and executed. This article is dedicated to the formal specification and validation of the identified roles in the Organizational Structure before a real deployment to generate systems with organizations exhibiting good qualities. Also, a proposal of a set of steps to automatically generate the code of the designed agent will be presented. In addition, the evaluation of some organizational aspects will be done at the abstract level makes it possible to adjust the design to remedy any failures before a real instantiation. The application domain used in this context, is a Cooperative Information Gathering System (CIGS) for travel organization. Multi-Agent Systems Organizational Model Organizational Structure Cooperative Information Gathering System Figures Figure 1 Figure 2 Figure 3 Figure 4 Figure 5 Figure 6 Figure 7 Figure 8 Figure 9 1 Introduction MAS design can be considered according to two approaches: an agent-centered approach (ACA) or an organization-centered approach (OCA) [12]. The ACA approach is essentially concerned with the definition of the internal structure of the agents in terms of mental states (Logic, Believe, Desire, Intention, Reactive …). It focuses on the micro level of the system to be modeled and does not master the interaction between the system’s components. The system behavior is supposed to emerge, and the designer has very few controls over it. The OCA, however, tries to overcome these shortcomings by two means: i) by focusing on the observable characteristics of the agents in terms of capacities instead of their internal structure; ii) by introducing organizational abstractions that make it possible to structure and regulate agent interactions for better organization of tasks, limitation of conflicts and reduction of communication cost [13]. For this purpose, concepts such as role, group, norms, laws, or interaction protocols are proposed [1]. Accordingly, the organizational approach can be viewed as a technique that governs individual behavior of agents to make them converge towards the global objectives to be achieved. Individual behaviors must comply with norms and rules fixed by the organization design [5]. Considering all these advantages, it becomes clear that following an organizational approach (instead of an agent-centered one) facilitates the design of complex, open and secured MAS [10]. In addition, all these facts explain the emergence of organizational models in MAS, among which we mention AGR [13], MOISE+[14], GAIA 2 [20] and an OM proposed in [2]. Also, a framework called MASQ was proposed to design Organization Centered Multi-Agent Systems (OCMAS) [11]. In these models, we distinguish two abstraction levels: The Organizational Structure (OS), and the Concrete Organization (CO). In this paper, we will focus on the OS: how we can design the internal behavior of the roles? Is there a way to automatically generate the code of the role class? and how we can evaluate and validate this level before moving to the instantiation? Using a Cooperative Information Gathering System (CIGS) [3] through a case study of travel organization, we will proceed as follow: i) identification of the roles involved in the system and their specification using the Object Petri Nets (OPN), ii) simulation of the internal behavior of these roles using the Renew tool. This simulation is used to check the functional criteria like liveness and termination of the process, iii) propose a set of steps to automatically generate the code of the designed role, iv) quantitative validation of organizational aspects such as flexibility, efficiency, and robustness [4, 16] using metrics that can be calculated a priori. The rest of the paper is structured in the following way. In section 2, we will present the state of the art related to the formal specifications of roles and the validation of the OS. In Section 3, we will introduce the used case study: the Cooperative Information Gathering System (CIGS). Section 4 gives an overview of the OPN and the design of identified roles using this formalism. Section 5 focuses on the simulation of these roles using the Renew tool and the validation of behavioral criteria. The steps to link the design to the implementation are proposed in Section 6. Quantitative validation of the Organizational Structure is presented in section 7. Lastly in section 8 conclusions are made. 2 Related work and positioning Between 2000 and 2010, significant attention was devoted to the organizational approach adopted for designing and developing MAS. Several Organizational Models have been proposed, and readers are referred to [27] for a detailed list. A survey of relevant works dealing with formal specification of multi-agent organizations is presented in [30]. These studies have proposed formalisms to formally specify the organizational dimension. Among these works, we mention first [16] since the evaluation criteria of the Organizational Structure proposed in this manuscript in section 6 are those presented in this work. The authors, inspired by [25, 26], propose a formalization of the OS and its properties using oriented graphs. This formalization allows for a thorough evaluation of the robustness, flexibility, and efficiency of the OS before actual deployment, and enables the selection of the configuration that best fits the scenario to be implemented. However, this formalization suffers from two shortcomings: Only the macro level of the organization is addressed. The proposed method does not refer to the internal behavior of each role. The OS is than presented as a set of roles and their mutual interactions without any formalization of the actions carried out by each role. Interactions between roles are limited to the types of relationships that exist between them: authority, coordination, or control. Consequently, during implementation, there is no mention of the objects exchanged between these roles or the protocol governing these exchanges. In [28], an OM was proposed as part of a comprehensive approach called MACODO. Organizational abstractions are formalized using the Z language. This language provides programmers with support to develop dynamic organizations that adapt to environmental changes. However, this specification is closely tied to the application domain of the MACODO approach, which is traffic monitoring. Additionally, no macro view of organizational structuring has been proposed. One additional study worth mentioning is [29] as it is closely related to our proposal of modelling multi-agent organizations with Petri Nets. The authors use PN to model a system they describe as simple. This formalization has only enabled the verification of a single criterion, which is the system is deadlock free. In addition, transition inputs consist of simple tokens, whereas in reality, the entities being manipulated are objects. Moreover, a detailed description of the internal actions of the agents has not been addressed. Although the organizational approach focuses on high-level abstract concepts without referring to implementation details, it is interesting to specify the functioning mode of roles (and consequently agents in a subsequent stage). In this study, we will demonstrate that using OPN for role specification offers the following advantages compared to other formalisms: The formal specification of the micro level of the Organizational Structure is ensured through the formalism. For each role, a detailed description of all its actions and interventions is provided. Formalizing the micro level of the Organizational Structure also dictates the mode of exchange between roles by enforcing a specific protocol. These protocols are implicitly described through the interactions of each network/role with other networks/roles. Therefore, the language provides a specification that encompasses both the micro and macro levels of the Organizational Structure. PN allow the verification of functional criteria before real system deployment. The criteria to be verified by simulation in section 5 are termination, final state accessibility, and liveness. Since OPN combine object-oriented programming concepts with PN, and since all internal role actions and interventions/interactions are modelled, an automatic transition from design to implementation is possible. Although what will be proposed in section 6 is not very comprehensive or elaborate, feasibility remains attainable. Indeed, combining a OPN editor with a set of transition rules enables the generation of the code skeleton related to the modelled role. Finally, the design of a Cooperative Information Gathering System to verify organizational criteria is presented. Although the criteria come from [4, 16], but the aim is to propose a comprehensive approach for specifying and validating the abstract level of the multi-agent organizations. 3 Overview of the Organizational Model for Cooperative Information Gathering The case study used in this work is a Cooperative Information Gathering System (CIGS). A CIGS is an organization of agents that work together to collect and share information for a common goal. These agents are programmed to collaborate and communicate with each other to efficiently gather and process data from various sources. The system starts with an initial user query, which will be decomposed into elementary tasks. These tasks will be distributed among agents, allowing for parallel processing and faster information retrieval. By working together, these agents can cover a wider range of sources and gather more comprehensive data than a single agent working alone. The CIGS was designed by following a multi-level Organizational Model. The problem treated by this system is the trip organization, where the user will introduce a list of parameters and the system will provide a result based on what is possible and user preference. For more details, we refer readers to [6, 7]. To specify and describe the functioning of the CIGS and more precisely how agents interact, we choose to model the system with an organizational perspective. Introducing organizational abstractions like roles and protocols makes it possible to structure and regulate agents’ interactions to organize their functioning, to limit conflicts and reduce communication cost [9]. Using these two abstractions, allows the design of the organization without worrying about the micro level composed of agents, but rather focusing on the macro level composed of roles and their interaction protocols. At run time, an agent is then likely to play several roles, and a role can be played by several agents. Thanks to a functional analysis, we have identified the roles which necessarily intervene in any CIGS: - The Mediator decomposes and/or reformulates the initial user query, supervises the execution of each elementary task and constructs the result. - The Coordinators are in charge of elementary tasks. They coordinate with the matchmaker to find translators able to retrieve information. After the reception of that information, they communicate it to the mediator and to other coordinators if needed. - The Matchmaker provides references towards external informational agents able to carry out elementary tasks. - The Translators (or wrappers) are external agents found by the matchmaker and in charge of retrieving information. They act as an Application Programming Interface (API) to allow the interaction between an information source and the coordinator. 4 Role representation with Object Petri Nets 4.1 Overview of Object Petri Nets Formalism In order to represent the identified roles in our CIGS, we had chosen the Object Petri Nets (OPN) formalism. This choice is motivated by the fact that OPN is a parallel systems specification language allowing us to formalize, in one hand, the concurrent activities of the roles intervening in a CIG process, and in the other hand, the roles’ actions, its interventions, the invariants, the coordination rules, its resources and the access authorizations to each resource. Object Petri Nets (OPN) [18] are a formalism coherently combining Petri Nets (PN) technology and the Object-Oriented (OO) approach. While PN are very suitable for expressing the dynamic behavior of a system, the OO approach permits the modeling and the structuring of its active (actor) and passive (information) entities. In a conventional PN, tokens are atomic, whereas in an OPN, they are presented as objects. As any PN, an OPN is made up of places, arcs, and transitions, but in an OPN, they are labeled with inscriptions referring to the handled objects. More precisely, an OPN features the following additional characteristics: - Places are typed. The type of a place is a (list of) type of an (list of) object(s). A token is a value matching the type of a place such as a (list of) constant (e.g. 2 or ‘hello’), an instance of an object class, or a reference towards such an instance. The value of a place is the set of tokens it contains. - Arcs are labeled with parameters. Each arc is labeled with a (list of) variable of the same type, as is the place that the arc is connected to. The variables on the arcs surrounding a transition serve as formal parameters of that transition and define the flow of tokens from input to output places. Arcs from places to a transition determine the possible condition of the transition: a transition may occur (or is possible) if there exists a binding of its input variables with tokens lying in its input places. Each transition is a complex structure made up of three components: a precondition, an action and emission rules. A transition may be guarded by a precondition, i.e. a side-effect free Boolean expression involving input variables. In this case, the transition is only permitted by a binding if this binding evaluates the precondition to be true. Passing a transition through depends on the precondition, on the location of tokens and on their value. Most transitions also include an action, which consists in a piece of code in which transitions’ variables may appear and object methods be invoked. This action is executed at each occurrence of the transition, and it processes the values of tokens. Finally, a transition may include a set of emission rules i.e. side-effect free Boolean expressions that determine the output arcs that are activated after the execution of the action. 4.2 Role specification with OPN We use the six following principles (explained with reference to the mediator in Fig. 2 ) to represent the behavior of a role by an OPN: - The rectangles delineate the roles with which it interacts. Only communication places appear, and which are called interface. This interface is an input place for one role and an output place for the other. - action associated with the transition represents the internal actions carried out by a role, - the interventions (I1, I2,...) which are transitions from transmitting role to a receiver role, are represented by arcs labeled by KQML performatives [19]. - a condition that holds true for each accessible marking beginning with an initial marking is known as an invariant. There exist numerous Petri Nets analysis techniques to deduce them. - the grey places are the resources, - the authorizations are represented by arcs, which connect transitions to resources. The internal behavior of the Mediator role is show in Fig. 2 . It interacts with the roles User and Coordinator. This interaction is represented by the six interface places on the top of the figure. At the left side we found the Resources used by the Mediator which are the Informational Model (IM) and the Task Model (TM). These two models belong to a whole modeling process explained with details in [7]. The QuUsMe place (for QuestionUserMediator ) represents the initial state of the mediator. It’s expressed by an Ask performative. The final state is shown by the AnMeUs place, and it expresses the reception of the final result via a tell performative. Three distinct phases, discernible within the network, comprise the Mediator's behavior: The user's query can be accepted by the Mediator, who can then reformulate it, break it down into smaller questions, and send them to the coordinators or the user. The left portion of the net is composed of transitions T1 and T2 . Following receipt of the user's question, the Mediator reformulates it (Transition T1 ) considering the user's preferences as stated in the instant message as well as the question's context. The Transition T2 is broken down by the Mediator into smaller questions that are sent to the Coordinators and maybe the user when the query has been reformulated. We utilize a dotted arc to indicate that participation in this interaction is optional. Then, the Mediator waits for the answers to these sub-questions ( AwaitingResults place). The responses to the sub-questions can be gathered by the Mediator thanks to the middle portion of the net, which is made up of transitions T3 and T4 . Upon receiving a result from a Coordinator or a user, the Mediator records it (using T3 or T4 ) in the AllTheResults place and notifies the ResultsNotification place of the existence of new results. The portion of the network on the right, consisting of transitions T5 and T6 , examines the collection of results that have been saved ( T5 ). If those results are deemed adequate, they are combined ( T6 ) to produce the result, which is then presented to the user. Should the outcomes be insufficient, the Mediator continues to wait for additional results. As soon as fresh data are received, it will begin an analysis ( T5 ) once more. It is notified of this event if one or more tokens are present in the ResultsNotification location. T1.T2.((T3|T4).T5) n .T6 is the language of the net, which provides all conceivable behaviors, where n is the total number of answers to the questions the coordinators and user submitted that the mediator received. The final state is reached by the execution of T6 transition which consumes WaitingResults token. 5 OPN simulation In addition to the formal specification of the OS roles given above, we performed a simulation to verify the behavioral aspect of the mediator role previously specified. We have chosen as a simulator the Renew tool (the Reference Net Workshop) developed at the Department of Computer Science at the University of Hamburg. Renew is freeware ( http://www.renew.de ), written in Java. It allows the graphic editing of the PN which is also used as a synoptic during the simulation. The simulation of the behavior of the Mediator role reveals two possible scenarios but which both lead to the desired end state (expressed by a token in place of the OPN of the previous section and which informs the user of the presence of a final response to his request). These scenarios, presented in Figs. 3 , correspond to the participation or not of the user when formulating the final response. The simulation allowed us to validate that the network was not blocked in both cases. It should be noted that the T5 transition has been split into two sub-transitions (T5.1 and T5.2) since the Renew tool does not allow us to express the validation conditions. To verify that all transitions can be crossed, we ran a step-by-step simulation for both scenarios. This simulation allowed us to validate the near liveliness of the network. Figure 4 shows this stepwise execution of the model relating to the second scenario (with user interaction T4). The simulation made it possible to verify the following properties: - Unfinished termination: termination is not guaranteed because we have an analysis loop of the response (((T3|T4).T5) n ) which is intentionally modeled as an iteration which allows it to take into account responses as they arrive. - The accessibility of the final state: there is an evolution of the network leading from the submission of the question (initial state) to the resolution of this question (final state). - Liveness of our network: there is for each action (transition) a configuration of the network allowing its execution. 6 Role implementation Once the termination, final state accessibility, and liveness properties have been validated through simulation, it would be interesting to proceed to the implementation stage and generate code that complies with the specification. Specifying roles using OPN allows the designer to generate the skeleton of the class related to that role. Although the process is currently manual, automation is feasible by creating an API between the E-NetObject [21] tool, which is a OPN editor, and a MAS development platform such as JADE [22], AgentBuilder [23], or MADKIT [24], enabling automatic generation of role skeletons. The API will start by parsing the XML file generated by the E-NetObject tool, which represents a snapshot of the edited net. This step will identify all designed entities such as transitions, manipulated objects, and interventions. The second step will involve applying a set of transitioning rules that will translate the identified entities in the first step into Java code of the class relevant to that role. The choice of the Java language is arbitrary since most software editors for MAS are based on this language. Each MAS development platform has a set of predefined functions for each agent, so the API must by default integrate these methods. One of these methods is the one we will call Life (the naming varies from one platform to another), which implements the agent's behavior throughout its lifecycle. The transitioning rules from an OPN to Java code can take the following form: - Each transition is a method that takes the incoming object as a parameter and produces the outgoing object as a result. - Each interaction is a message sent or received with a parameter which is the KQML performative. - Each object manipulated by the role, and which is external to the system to be implemented is a parameter of the Life method. For example, in our CIG context, external objects are resources and the initial request formulated by the user. - The Life method will implement the networking language, which is in our case: T1.T2.((T3|T4).T5) n .T6 as described in section 3. This method takes as parameters all external objects to the system. In our case, these objects are the Info Model, the task Model (as Ontology type in our case), and the user's initial question (String type). By applying these transition rules, the skeleton of the resulting Java class is shown in the following Fig. 5 . 7 Quantitative assessment of the Organizational Structure The two organizational levels of the OM need to be accompanied with tools and metrics, to make the evaluation process possible, before a real deployment of the multi-agent system. In this section, we will focus on the quantitative evaluation of the first organization level which is the Organizational Structure. We refer readers to [8] for qualitative evaluation of the communication in the concrete organizational level. 7.1 Evaluation criteria The criteria used to evaluate the performance of the OS are inspired from [4, 16]. The authors applied quantitative concepts from graph theory in order to assess the structure used to implement the MAS. We will briefly introduce these criteria but for a complete explanation we refer readers to [4, 16, 9]. The organizational properties which are evaluated are: - Robustness: how the OS is stable in an unpredictable environment - Flexibility: the capability of an organization to adapt to changing circumstances - Efficiency: how to achieve the global goal of the system with the minimum of resources. To evaluate these properties, the authors introduced three equations to measure specific graph-theoretical aspects of organizational structures which are: - Connectedness: expresses how strongly the roles are linked with one another - Economy: how we can keep a system connected with the minimum of links - Univocity: expresses the absence of redundant links within the same role Each one of these structural aspects is calculated within one of these three structural dimensions which described the nature of links between each role: - Authority dimension: it implies that a role can delegate a task to another role. - Coordination dimension: which represent the knowledge exchange between roles. - Control dimension: the fact that a role must monitor the activities of another role. The organizational properties, which are robustness, flexibility, and efficiency, are measured from graphs representative of the different roles and the different types of links that exist between them. The authors provided a vector of values which represent the optimal results that we can obtain for each one of these properties. During the two next sections, we will present the role graphs from where we will make the calculations, and we will compare our results with these optimal vectors of values. 7.2 Role graphs In this section, we will introduce the representative graphs of the different roles of the Organizational Structure according to the three structural dimensions of control, authority, and coordination. Since the CIGS was conceived to resolve the problem of travel organization, the OS was strictly dependent on the problem resolving process. As shown in Fig. 6 , the problem is decomposed into four elementary tasks which are the visits, the accommodation, the transport, and the weather report. The organization of accommodations is extremely related to the transport as they should have the same arrival and departure dates. Each elementary task will search information from a different Information Sources. As a result, the OS includes the following roles: - A Mediator, overseeing the CIG process, - As many Coordinators as there are basic tasks in the trip organization problem. In our case there are four: visits, the accommodation, the transport and the weather report. These coordinators will be titled, in the role graph, respectively, Coordinator 1, Coordinator 2, Coordinator 3 and Coordinator 4. - Since a Matchmaker can be specialized in more than one field, we supposed that we will have three. Therefore, we have three Matchmakers respectively rated Matchmaker1, Matchmaker 2 and Matchmaker 3. - As many Translators as there are elementary tasks. In our case, we chose to associate a translator with each coordinator. We will then have four translators labeled respectively Translator 1, Translator 2, Translator 3 and Translator 4. To facilitate the reading of the representative diagram of the different types of links between the roles identified in our OS, we have chosen to present a graph for each structural dimension (control, authority, and coordination) already introduced in section 5.1: The "control" dimension (see Fig. 7 ): the mediator has a control link over all the coordinators allowing him to assess the provided results. The “authority” dimension (cf. Figure 8 ): The Mediator has both a link of authority and control with the coordinator roles, which allows it to both delegate the sub-objectives to them and assess the returned results. In turn, the Coordinators have a link of authority on the one hand over the Matchmakers by requiring them to provide the addresses of information sources likely to contain the desired result, and on the other hand over the Translators by ordering them to query and return partial results from these sources. The "coordination" dimension (see Fig. 9 ): The Coordinator can interact with another Coordinator in the case of solving interrelated problems which are expressed through a coordination link. Message feedback as responses to requests between the different roles is presented by a coordination link. Finally, the Translators publish their skills to the Matchmakers, which also translate into a coordination link. 7.3 Results and interpretations The results obtained from the application of the equations provided in [4, 16] as well as the maximum values which optimize the three structural properties are given by the following tables: Table 1 Robustness STRUCTURAL PROPERTY OPTIMAL VALUES OBTAINED VALUES Economy coordination 0 0,94 Univocity authority 0 0,91 Connectivity coordination 1 1 Table 2 Flexibility STRUCTURAL PROPERTY OPTIMAL VALUES OBTAINED VALUES Economy coordination 0 0,94 Connectivity authority 0 1 Connectivity coordination 1 1 Table 3 Efficiency STRUCTURAL PROPERTY OPTIMAL VALUES OBTAINED VALUES Economy coordination 1 0,94 Economy control 1 1 Economy authority 1 1 From these results, and by comparing them with the vector of values that optimize the three organizational properties, we can draw the following conclusions: - The organization is not strong. In fact, two out of three values are far from the optimal values, which are Economy-coordination and Univocity-authority. Let us recall in this context that robustness induces the system's ability to resist in the face of unpredictable events such as the failure of an agent, playing a given role, to provide a certain service. However, and as we have defined the current OS, very little redundancy is present, so there is no alternative for delegation in the case of failure. During execution, a Coordinator may judge that the result returned by a Translator is irrelevant and consider the recruitment of another Translator: which is not considered in our modeling. The lack of robustness is also due to the specialization of our agents which are therefore not interchangeable. In this context, and to fix this weakness, we must integrate the possibility of an auto-adaptation of agent goals in case of unpredictable events as described in [17]. - The organization is not very flexible because we have a very centralized, very economical organization and therefore with very little redundancy in terms of coordination. The values of the Economy-Coordination and Connectivity-Authority dimensions are far from the optimal values. In our case, and to restrict the information exchange between agents, and to reduce the cost of communication, the recruitment of agents is centralized at the level of the Mediator and Coordinators who exercise authority over the rest of the agents. In short, flexibility has been sacrificed for the benefit of the economy in terms of interactions. A solution to the lack of flexibility in the MAS organization acting in uncertain environments is proposed in [15]. This can be the subject of future works. - The organization is very efficient. Indeed, the three values of this criterion are almost optimal. This is explained by the fact that we have optimal modeling at the level of each dimension, so a minimum structure to coordinate, control and direct. Only the mediator and the coordinators have authority over the other agents, and the coordination and control links are reduced to the essential. The effectiveness of the organization as defined in [3] is on its optimal value as the goals are well accomplished by the agents. 8 Conclusion and future work In this paper we have proposed a formal specification of the identified roles in the abstract level of the Organizational Model (the Organizational Structure) of a Multi-Agent System. The chosen formalism was the Object Petri Nets. This formalism enabled us to formally present the internal actions, interventions, and the rules of sequence of the various roles. This representation formalism also has the advantage of being simulated in order to validate the properties of the model. We were then able to validate the behavioral aspects of the roles via a simulation with the Renew simulator. Properties such as non-blocking and liveliness of the model have been verified. We also proposed a way to automatically generate the code of each role based on its OPN specification. We are conscient that the automatic transitioning from the design to the implementation require more technical studies, but we are convinced that is feasible. In addition, we made a quantitative evaluation of our OS based on graph-theoretical measures. This evaluation concern organizational properties such as flexibility, robustness and efficiency and was carried through a Cooperative Information Gathering System. The objective was to provide a comprehensive approach for defining and verifying the abstract level of the multi-agent organizations, even though the evaluation criteria originate from [4, 16]. Declarations Author Contribution Only I.B. wrote the whole article References A. Artikis and J. Pitt, 2001, A Formal Model of Open Agent Societies. In: 5 th International Conference on Autonomous Agents (AA’01) , Montreal-Canada, pp. 192-193. Afsaneh Fatemi, Kamran Zamanifar, and Naser Nematbakhsh, 2001. Adaptive Team-Based Multi-Agent Organizational Model: A Case in Rescue Systems. International Journal of Computer Science and Information Technology 3.2, pp. 165–175. Daniel D. Corkill, Edmund H. Durfee, Victor R. Lesser, Huzaifa Zafar, and Chongjie Zhang,2011. Organizationally Adept Agents. In Working Notes of the AAMAS-11 Workshop on Coordination, Organizations, Institutions, and Norms in Multiagent Systems (COIN). Grossi, D., Dignum, F., Dignum, V., Dastani, M., Royakkers, L., 2006. Structural evaluation of agent organizations. 5th International Joint Conference on Autonomous agents and Multiagent systems , pp. 1110-1112. Hosny Ahmed Abbas, Samir Ibrahim Shaheen, Mohammed Hussein Amin, 2015. Organization of Multi-Agent Systems: An Overview. Journal of Intelligent Information Systems , Vol. 4, No. 3, pp. 46-57. I. Bouslimi, Khaled Ghédira and Chihab Hanachi, 2006. An Agent-based Organizational Model for Cooperative Information Gathering, In: Proceeding of the second International Conference on Signal-Image Technology and Internet-based Systems, SITIS , Hammamet, Tunisia, pp. 414-425. I. Bouslimi, Chihab Hanachi, Hassan Tout and Khaled Ghédira, 2008. Coordination framework for Cooperative Information Gathering. In: International Journal of Advanced Intelligence Paradigms, Inderscience Publishers , Vol. 1, No. 1, pp. 60-79. I. Bouslimi, C. Hanachi and K. Ghédira, 2014. An Experimental Evaluation of Communication in an Organization-Based Multi-agent System. IEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (IAT) , pp. 72-78. Ines Thabet, Issam Bouslimi, Chihab Hanachi and Khaled Ghedira, 2011. A Multi-agent Organizational Model for Grid Scheduling. In : KES International Conference (KES-AMSTA 2011 ),Manchester, UK, Vol. 6682, pp. 148-158. Jensen, Andreas & Villadsen, Jørgen, 2013. A comparison of organization-centered and agent-centered multi-agent systems. Artificial Intelligence Research. 2. 10.5430/air.v2n3p5 9. J. Ferber, T. Stratulat, J. Tranier,2009. Towards an integral approach of organizations in multi-agent systems: the MASQ approach. Chapter book of Multi-agent Systems: Semantics and Dynamics of Organizational Models in Virginia Dignum (Ed), IGI. J. Ferber and O. Gutknecht, 1998, A Meta-Model for the Analysis and Design of Organizations in Multi-Agent Systems. In: 3 rd International Conference on Multi-Agents Systems, (ICMAS’98), IEEE Computer Society . Paris, France. Jacques Ferber, Olivier Gutknecht, and Fabien Michel, 2004. From Agents to Organizations: an Organizational View of Multi-Agent Systems. In: Agent-Oriented Software Engineering (AOSE) IV , P. Giorgini, Jörg Müller, James Odell, eds, Melbourne, (2003), LNCS 2935, pp. 214-230. J.F. Hübner, J. S. Sichman, O. Boissier, 2002. MOISE+: towards a structural, functional, and deontic model for MAS organization. In: the First International Joint Conference on Autonomous Agents & Multi-Agent Systems, (AAMAS’02) , Bologna-Italy pp. 501-502. Keogh, Kathleen, and Liz Sonenberg. 2020. Designing Multi-Agent System Organizations for Flexible Runtime Behavior. Applied Sciences 10, no. 15: 5335. https://doi.org/10.3390/app10155335 Loris Penserini, David Grossi, Frank Dignum, Virginia Dignum, Huib Aldewereld. 2009. Evaluating Organizational Configurations. In Proceedings of The 2009 IEEE/WIC/ACM International Conferences on Intelligent Agent Technology (IAT-09), IEEE CS Press , Milano, Italy. Matteo Baldoni, Cristina Baroglio, Roberto Micalizio, Stefano Tedeschi, 2023. Accountability in multi-agent organizations: from conceptual design to agent programming. In Autonomous Agents and Multi-Agent Systems 37. https://doi.org/10.1007/s10458-022-09590-6 Sibertin-Blanc, 1985. High-level Petri nets with Data structure. 6th European workshop on Petri nets and applications , Espoo (Finland). Tim Finin, Richard Fritzson, Don McKay, and Robin McEntire, 1994. KQML as an agent communication language. In Proceedings of the third international conference on Information and knowledge management (CIKM '94) . New York, NY, USA, pp. 456–463. Zambonelli, N. R. Jennings and M. Wooldrige, 2003. Developing Multi-Agent Systems: The Gaia Methodology. In ACM Transactions on Software Engineering Methodology . pp. 317-370. Frédéric Raclot, David Andreu, Thérèse Libourel Rouge, Robin Passama. E-NetObject: Un Editeur de Réseaux de Petri à Objets. 02180, 2002, pp.40. fflirmm-00269413f https://jade.tilab.com/, 10/10/2023. https://www.agentbuilder.com, 12/01/2024. https://www.madkit.net/madkit/index.php, 01/10/2023. D. Grossi, F. Dignum, M. Dastani, and L. Royakkers. Foundations of organizational structures in multiagent systems. In AAMAS ’05: Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, pages 690–697, New York, NY, USA, 2005. ACM. D. Grossi, F. Dignum, V. Dignum, M. Dastani, and L. Royakkers. Structural aspects of the evaluation of agent organizations. In COIN@ECAI 2006, 2006. Dignum, V. (Ed.), 2009. Handbook of Research on Multi-Agent Systems: Semantics and Dynamics of Organizational Models: Semantics and Dynamics of Organizational Models. IGI Global. Weyns, D., Haesevoets, R., & Helleboogh, A, 2010. The MACODO organization model for context-driven dynamic agent organizations. ACM Transactions on Autonomous and Adaptive Systems (TAAS), 5(4), 16. Celaya, Jose & Desrochers, Alan & Graves, Robert. (2007). Modeling and Analysis of Multi-agent Systems using Petri Nets. Journal of Computers - JCP. 4. 1439 - 1444. 10.1109/ICSMC.2007.4413960. S. Sabeg, T. M. Maarouk and M. El Habib Souidi, "Formal Specification and Verification for Organization-based systems : A Survey," 2022 4th International Conference on Pattern Analysis and Intelligent Systems (PAIS) , Oum El Bouaghi, Algeria, 2022, pp. 1-6, doi: 10.1109/PAIS56586.2022.9946660. Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-4197325","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":286689954,"identity":"c2165fdc-70c8-4dee-94f2-75ef3187f2d6","order_by":0,"name":"Issam Bouslimi","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA7UlEQVRIiWNgGAWjYBACNgh1AIiZGw4wGNgAGYyNB4jUwgjSkgZlEAYQLUDiMJyLE/DxH3/46QbDHTmD8wcbD90oOG+3tv0w0JYam2icDpPIMZbOYXhmbHAjseFwjsHt5G1nEoFajqXlNuDUwsMA1HI4ccMNRogWswNALUA2bi38xx//Bms5fxCk5Vyy2fmHBLQwJJhBbDkAdtgBO7MbhGyRyDGzzjF4ZiwJ8UtygtkNoC0JePwi33/88e2cijtyfOcPH/6c88fO3ux8+sMHH2pscGqBAAMEMxGsMgGvcjRgT4riUTAKRsEoGBkAAOYraLdYnpjZAAAAAElFTkSuQmCC","orcid":"","institution":"University of Jendouba","correspondingAuthor":true,"prefix":"","firstName":"Issam","middleName":"","lastName":"Bouslimi","suffix":""}],"badges":[],"createdAt":"2024-04-01 00:14:21","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-4197325/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-4197325/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":54181751,"identity":"1eebbf8d-adbd-4c9f-93db-043874647f04","added_by":"auto","created_at":"2024-04-05 16:37:26","extension":"png","order_by":1,"title":"Figure 1","display":"","copyAsset":false,"role":"figure","size":31153,"visible":true,"origin":"","legend":"\u003cp\u003eFormal specification of the Mediator Role with OPN\u003c/p\u003e","description":"","filename":"1.png","url":"https://assets-eu.researchsquare.com/files/rs-4197325/v1/daa4394f6447b2c9a65f95db.png"},{"id":54181750,"identity":"a03788a4-2c19-4416-9812-d0b3efb55a35","added_by":"auto","created_at":"2024-04-05 16:37:26","extension":"png","order_by":2,"title":"Figure 2","display":"","copyAsset":false,"role":"figure","size":125176,"visible":true,"origin":"","legend":"\u003cp\u003eScenario with user interaction vs Scenario without user interaction\u003c/p\u003e","description":"","filename":"2.png","url":"https://assets-eu.researchsquare.com/files/rs-4197325/v1/a324d8fcec6c46c5f7495cde.png"},{"id":54181752,"identity":"918f3ba3-90bf-4439-b1fe-ae5b9295e1af","added_by":"auto","created_at":"2024-04-05 16:37:26","extension":"png","order_by":3,"title":"Figure 3","display":"","copyAsset":false,"role":"figure","size":291752,"visible":true,"origin":"","legend":"\u003cp\u003eStep-by-step simulation for scenario 1\u003c/p\u003e","description":"","filename":"3.png","url":"https://assets-eu.researchsquare.com/files/rs-4197325/v1/2c3246d4a869d149f2309300.png"},{"id":54181754,"identity":"4dc403b7-5aaa-413f-be5f-e9dbfade05cc","added_by":"auto","created_at":"2024-04-05 16:37:26","extension":"png","order_by":4,"title":"Figure 4","display":"","copyAsset":false,"role":"figure","size":5713,"visible":true,"origin":"","legend":"\u003cp\u003eThis image is not available with this version.\u003c/p\u003e","description":"","filename":"4.png","url":"https://assets-eu.researchsquare.com/files/rs-4197325/v1/6ad57da56a609466793ea2a1.png"},{"id":54181753,"identity":"a6ffc345-8e90-4199-a677-ac09b0a59f66","added_by":"auto","created_at":"2024-04-05 16:37:26","extension":"png","order_by":5,"title":"Figure 5","display":"","copyAsset":false,"role":"figure","size":355997,"visible":true,"origin":"","legend":"\u003cp\u003eMediator java class code\u003c/p\u003e","description":"","filename":"5.png","url":"https://assets-eu.researchsquare.com/files/rs-4197325/v1/c66772b65a7cf644cc1f035b.png"},{"id":54181756,"identity":"c08764fe-d6d8-42a4-8c01-4ff4a1f20f8a","added_by":"auto","created_at":"2024-04-05 16:37:26","extension":"png","order_by":6,"title":"Figure 6","display":"","copyAsset":false,"role":"figure","size":93295,"visible":true,"origin":"","legend":"\u003cp\u003eTrip organization elementary tasks\u003c/p\u003e","description":"","filename":"6.png","url":"https://assets-eu.researchsquare.com/files/rs-4197325/v1/4c1b47172edf77c997a3fa98.png"},{"id":54181755,"identity":"1caa15b8-39fb-47de-b3b4-485c6208bd18","added_by":"auto","created_at":"2024-04-05 16:37:26","extension":"png","order_by":7,"title":"Figure 7","display":"","copyAsset":false,"role":"figure","size":46807,"visible":true,"origin":"","legend":"\u003cp\u003eControl links of the Organizational Structure\u003c/p\u003e","description":"","filename":"7.png","url":"https://assets-eu.researchsquare.com/files/rs-4197325/v1/da94e04bf14babab65211f49.png"},{"id":54181758,"identity":"0c3ae767-000e-4c5b-aa63-2402f3441ff6","added_by":"auto","created_at":"2024-04-05 16:37:26","extension":"png","order_by":8,"title":"Figure 8","display":"","copyAsset":false,"role":"figure","size":109238,"visible":true,"origin":"","legend":"\u003cp\u003eAuthority links of the Organizational Structure\u003c/p\u003e","description":"","filename":"8.png","url":"https://assets-eu.researchsquare.com/files/rs-4197325/v1/186e1c88c22bf22a6e0fea98.png"},{"id":54181757,"identity":"ca93030c-42be-48cd-a01a-175eb10a48dd","added_by":"auto","created_at":"2024-04-05 16:37:26","extension":"png","order_by":9,"title":"Figure 9","display":"","copyAsset":false,"role":"figure","size":128885,"visible":true,"origin":"","legend":"\u003cp\u003eCoordination links of the Organizational Structure\u003c/p\u003e","description":"","filename":"9.png","url":"https://assets-eu.researchsquare.com/files/rs-4197325/v1/4aff52f30caff8f33373a52b.png"},{"id":57573858,"identity":"c90904ad-aab9-4672-acb3-ebced68240cc","added_by":"auto","created_at":"2024-06-02 16:53:34","extension":"pdf","order_by":0,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":1554241,"visible":true,"origin":"","legend":"","description":"","filename":"manuscript.pdf","url":"https://assets-eu.researchsquare.com/files/rs-4197325/v1/94a271b7-80c0-486a-9fc2-67a09df2e56c.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Multi-Agent Organizational Structure: specification and validation","fulltext":[{"header":"1 Introduction","content":"\u003cp\u003eMAS design can be considered according to two approaches: an agent-centered approach (ACA) or an organization-centered approach (OCA) [12]. The ACA approach is essentially concerned with the definition of the internal structure of the agents in terms of mental states (Logic, Believe, Desire, Intention, Reactive \u0026hellip;). It focuses on the micro level of the system to be modeled and does not master the interaction between the system\u0026rsquo;s components. The system behavior is supposed to emerge, and the designer has very few controls over it. The OCA, however, tries to overcome these shortcomings by two means: i) by focusing on the observable characteristics of the agents in terms of capacities instead of their internal structure; ii) by introducing organizational abstractions that make it possible to structure and regulate agent interactions for better organization of tasks, limitation of conflicts and reduction of communication cost [13]. For this purpose, concepts such as role, group, norms, laws, or interaction protocols are proposed [1]. Accordingly, the organizational approach can be viewed as a technique that governs individual behavior of agents to make them converge towards the global objectives to be achieved. Individual behaviors must comply with norms and rules fixed by the organization design [5].\u003c/p\u003e \u003cp\u003eConsidering all these advantages, it becomes clear that following an organizational approach (instead of an agent-centered one) facilitates the design of complex, open and secured MAS [10]. In addition, all these facts explain the emergence of organizational models in MAS, among which we mention AGR [13], MOISE+[14], GAIA\u003csup\u003e2\u003c/sup\u003e[20] and an OM proposed in [2]. Also, a framework called MASQ was proposed to design Organization Centered Multi-Agent Systems (OCMAS) [11]. In these models, we distinguish two abstraction levels: The Organizational Structure (OS), and the Concrete Organization (CO).\u003c/p\u003e \u003cp\u003eIn this paper, we will focus on the OS: how we can design the internal behavior of the roles? Is there a way to automatically generate the code of the role class? and how we can evaluate and validate this level before moving to the instantiation?\u003c/p\u003e \u003cp\u003eUsing a Cooperative Information Gathering System (CIGS) [3] through a case study of travel organization, we will proceed as follow: i) identification of the roles involved in the system and their specification using the Object Petri Nets (OPN), ii) simulation of the internal behavior of these roles using the Renew tool. This simulation is used to check the functional criteria like liveness and termination of the process, iii) propose a set of steps to automatically generate the code of the designed role, iv) quantitative validation of organizational aspects such as flexibility, efficiency, and robustness [4, 16] using metrics that can be calculated a priori.\u003c/p\u003e \u003cp\u003eThe rest of the paper is structured in the following way. In section 2, we will present the state of the art related to the formal specifications of roles and the validation of the OS. In Section 3, we will introduce the used case study: the Cooperative Information Gathering System (CIGS). Section 4 gives an overview of the OPN and the design of identified roles using this formalism. Section 5 focuses on the simulation of these roles using the Renew tool and the validation of behavioral criteria. The steps to link the design to the implementation are proposed in Section 6. Quantitative validation of the Organizational Structure is presented in section 7. Lastly in section 8 conclusions are made.\u003c/p\u003e"},{"header":"2 Related work and positioning","content":"\u003cp\u003eBetween 2000 and 2010, significant attention was devoted to the organizational approach adopted for designing and developing MAS. Several Organizational Models have been proposed, and readers are referred to [27] for a detailed list. A survey of relevant works dealing with formal specification of multi-agent organizations is presented in [30].\u003c/p\u003e\n\u003cp\u003eThese studies have proposed formalisms to formally specify the organizational dimension. Among these works, we mention first [16] since the evaluation criteria of the Organizational Structure proposed in this manuscript in section 6 are those presented in this work. The authors, inspired by [25, 26], propose a formalization of the OS and its properties using oriented graphs. This formalization allows for a thorough evaluation of the robustness, flexibility, and efficiency of the OS before actual deployment, and enables the selection of the configuration that best fits the scenario to be implemented. However, this formalization suffers from two shortcomings:\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003eOnly the macro level of the organization is addressed. The proposed method does not refer to the internal behavior of each role. The OS is than presented as a set of roles and their mutual interactions without any formalization of the actions carried out by each role.\u003c/li\u003e\n \u003cli\u003eInteractions between roles are limited to the types of relationships that exist between them: authority, coordination, or control. Consequently, during implementation, there is no mention of the objects exchanged between these roles or the protocol governing these exchanges.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eIn [28], an OM was proposed as part of a comprehensive approach called MACODO. Organizational abstractions are formalized using the Z language. This language provides programmers with support to develop dynamic organizations that adapt to environmental changes. However, this specification is closely tied to the application domain of the MACODO approach, which is traffic monitoring. Additionally, no macro view of organizational structuring has been proposed.\u003c/p\u003e\n\u003cp\u003eOne additional study worth mentioning is [29] as it is closely related to our proposal of modelling multi-agent organizations with Petri Nets. The authors use PN to model a system they describe as simple. This formalization has only enabled the verification of a single criterion, which is the system is deadlock free. In addition, transition inputs consist of simple tokens, whereas in reality, the entities being manipulated are objects. Moreover, a detailed description of the internal actions of the agents has not been addressed. Although the organizational approach focuses on high-level abstract concepts without referring to implementation details, it is interesting to specify the functioning mode of roles (and consequently agents in a subsequent stage).\u003c/p\u003e\n\u003cp\u003eIn this study, we will demonstrate that using OPN for role specification offers the following advantages compared to other formalisms:\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003eThe formal specification of the micro level of the Organizational Structure is ensured through the formalism. For each role, a detailed description of all its actions and interventions is provided.\u003c/li\u003e\n \u003cli\u003eFormalizing the micro level of the Organizational Structure also dictates the mode of exchange between roles by enforcing a specific protocol. These protocols are implicitly described through the interactions of each network/role with other networks/roles. Therefore, the language provides a specification that encompasses both the micro and macro levels of the Organizational Structure.\u003c/li\u003e\n \u003cli\u003ePN allow the verification of functional criteria before real system deployment. The criteria to be verified by simulation in section 5 are termination, final state accessibility, and liveness.\u003c/li\u003e\n \u003cli\u003eSince OPN combine object-oriented programming concepts with PN, and since all internal role actions and interventions/interactions are modelled, an automatic transition from design to implementation is possible. Although what will be proposed in section 6 is not very comprehensive or elaborate, feasibility remains attainable. Indeed, combining a OPN editor with a set of transition rules enables the generation of the code skeleton related to the modelled role.\u003c/li\u003e\n \u003cli\u003eFinally, the design of a Cooperative Information Gathering System to verify organizational criteria is presented. Although the criteria come from [4, 16], but the aim is to propose a comprehensive approach for specifying and validating the abstract level of the multi-agent organizations.\u003c/li\u003e\n\u003c/ul\u003e"},{"header":"3 Overview of the Organizational Model for Cooperative Information Gathering","content":"\u003cp\u003eThe case study used in this work is a Cooperative Information Gathering System (CIGS). A CIGS is an organization of agents that work together to collect and share information for a common goal. These agents are programmed to collaborate and communicate with each other to efficiently gather and process data from various sources. The system starts with an initial user query, which will be decomposed into elementary tasks. These tasks will be distributed among agents, allowing for parallel processing and faster information retrieval. By working together, these agents can cover a wider range of sources and gather more comprehensive data than a single agent working alone.\u003c/p\u003e\n\u003cp\u003eThe CIGS was designed by following a multi-level Organizational Model. The problem treated by this system is the trip organization, where the user will introduce a list of parameters and the system will provide a result based on what is possible and user preference. For more details, we refer readers to [6, 7].\u003c/p\u003e\n\u003cp\u003eTo specify and describe the functioning of the CIGS and more precisely how agents interact, we choose to model the system with an organizational perspective. Introducing organizational abstractions like roles and protocols makes it possible to structure and regulate agents\u0026rsquo; interactions to organize their functioning, to limit conflicts and reduce communication cost [9]. Using these two abstractions, allows the design of the organization without worrying about the micro level composed of agents, but rather focusing on the macro level composed of roles and their interaction protocols. At run time, an agent is then likely to play several roles, and a role can be played by several agents.\u003c/p\u003e\n\u003cp\u003eThanks to a functional analysis, we have identified the roles which necessarily intervene in any CIGS:\u003c/p\u003e\n\u003cp\u003e- The Mediator decomposes and/or reformulates the initial user query, supervises the execution of each elementary task and constructs the result.\u003c/p\u003e\n\u003cp\u003e- The Coordinators are in charge of elementary tasks. They coordinate with the matchmaker to find translators able to retrieve information. After the reception of that information, they communicate it to the mediator and to other coordinators if needed.\u003c/p\u003e\n\u003cp\u003e- The Matchmaker provides references towards external informational agents able to carry out elementary tasks.\u003c/p\u003e\n\u003cp\u003e- The Translators (or wrappers) are external agents found by the matchmaker and in charge of retrieving information. They act as an Application Programming Interface (API) to allow the interaction between an information source and the coordinator.\u003c/p\u003e"},{"header":"4 Role representation with Object Petri Nets","content":"\u003cdiv id=\"Sec5\" class=\"Section2\"\u003e\n \u003ch2\u003e4.1 Overview of Object Petri Nets Formalism\u003c/h2\u003e\n \u003cp\u003eIn order to represent the identified roles in our CIGS, we had chosen the Object Petri Nets (OPN) formalism. This choice is motivated by the fact that OPN is a parallel systems specification language allowing us to formalize, in one hand, the concurrent activities of the roles intervening in a CIG process, and in the other hand, the roles\u0026rsquo; actions, its interventions, the invariants, the coordination rules, its resources and the access authorizations to each resource.\u003c/p\u003e\n \u003cp\u003eObject Petri Nets (OPN) [18] are a formalism coherently combining Petri Nets (PN) technology and the Object-Oriented (OO) approach. While PN are very suitable for expressing the dynamic behavior of a system, the OO approach permits the modeling and the structuring of its active (actor) and passive (information) entities. In a conventional PN, tokens are atomic, whereas in an OPN, they are presented as objects. As any PN, an OPN is made up of places, arcs, and transitions, but in an OPN, they are labeled with inscriptions referring to the handled objects. More precisely, an OPN features the following additional characteristics:\u003c/p\u003e\n \u003cp\u003e- Places are typed. The type of a place is a (list of) type of an (list of) object(s). A token is a value matching the type of a place such as a (list of) constant (e.g. 2 or \u0026lsquo;hello\u0026rsquo;), an instance of an object class, or a reference towards such an instance. The value of a place is the set of tokens it contains.\u003c/p\u003e\n \u003cp\u003e- Arcs are labeled with parameters. Each arc is labeled with a (list of) variable of the same type, as is the place that the arc is connected to. The variables on the arcs surrounding a transition serve as formal parameters of that transition and define the flow of tokens from input to output places. Arcs from places to a transition determine the possible condition of the transition: a transition may occur (or is possible) if there exists a binding of its input variables with tokens lying in its input places.\u003c/p\u003e\n \u003cp\u003eEach transition is a complex structure made up of three components: a precondition, an action and emission rules. A transition may be guarded by a precondition, i.e. a side-effect free Boolean expression involving input variables. In this case, the transition is only permitted by a binding if this binding evaluates the precondition to be true. Passing a transition through depends on the precondition, on the location of tokens and on their value. Most transitions also include an action, which consists in a piece of code in which transitions\u0026rsquo; variables may appear and object methods be invoked. This action is executed at each occurrence of the transition, and it processes the values of tokens. Finally, a transition may include a set of emission rules i.e. side-effect free Boolean expressions that determine the output arcs that are activated after the execution of the action.\u003c/p\u003e\n\u003c/div\u003e\n\u003cdiv id=\"Sec6\" class=\"Section2\"\u003e\n \u003ch2\u003e4.2 Role specification with OPN\u003c/h2\u003e\n \u003cp\u003eWe use the six following principles (explained with reference to the mediator in Fig. \u003cspan class=\"InternalRef\"\u003e2\u003c/span\u003e) to represent the behavior of a role by an OPN:\u003c/p\u003e\n \u003cp\u003e- The rectangles delineate the roles with which it interacts. Only communication places appear, and which are called interface. This interface is an input place for one role and an output place for the other.\u003c/p\u003e\n \u003cp\u003e- action associated with the transition represents the internal actions carried out by a role,\u003c/p\u003e\n \u003cp\u003e- the interventions (I1, I2,...) which are transitions from transmitting role to a receiver role, are represented by arcs labeled by KQML performatives [19].\u003c/p\u003e\n \u003cp\u003e- a condition that holds true for each accessible marking beginning with an initial marking is known as an invariant. There exist numerous Petri Nets analysis techniques to deduce them.\u003c/p\u003e\n \u003cp\u003e- the grey places are the resources,\u003c/p\u003e\n \u003cp\u003e- the authorizations are represented by arcs, which connect transitions to resources.\u003c/p\u003e\n \u003cp\u003eThe internal behavior of the Mediator role is show in Fig. \u003cspan class=\"InternalRef\"\u003e2\u003c/span\u003e. It interacts with the roles User and Coordinator. This interaction is represented by the six interface places on the top of the figure.\u003c/p\u003e\n \u003cp\u003eAt the left side we found the Resources used by the Mediator which are the Informational Model (IM) and the Task Model (TM). These two models belong to a whole modeling process explained with details in [7]. The \u003cem\u003eQuUsMe\u003c/em\u003e place (for \u003cem\u003eQuestionUserMediator\u003c/em\u003e) represents the initial state of the mediator. It\u0026rsquo;s expressed by an \u003cem\u003eAsk\u003c/em\u003e performative. The final state is shown by the \u003cem\u003eAnMeUs\u003c/em\u003e place, and it expresses the reception of the final result via a \u003cem\u003etell\u003c/em\u003e performative.\u003c/p\u003e\n \u003cp\u003eThree distinct phases, discernible within the network, comprise the Mediator\u0026apos;s behavior:\u003c/p\u003e\n \u003cp\u003eThe user\u0026apos;s query can be accepted by the Mediator, who can then reformulate it, break it down into smaller questions, and send them to the coordinators or the user. The left portion of the net is composed of transitions \u003cem\u003eT1\u003c/em\u003e and \u003cem\u003eT2\u003c/em\u003e. Following receipt of the user\u0026apos;s question, the Mediator reformulates it (Transition \u003cem\u003eT1\u003c/em\u003e) considering the user\u0026apos;s preferences as stated in the instant message as well as the question\u0026apos;s context. The Transition \u003cem\u003eT2\u003c/em\u003e is broken down by the Mediator into smaller questions that are sent to the Coordinators and maybe the user when the query has been reformulated. We utilize a dotted arc to indicate that participation in this interaction is optional. Then, the Mediator waits for the answers to these sub-questions (\u003cem\u003eAwaitingResults\u003c/em\u003e place).\u003c/p\u003e\n \u003cp\u003eThe responses to the sub-questions can be gathered by the Mediator thanks to the middle portion of the net, which is made up of transitions \u003cem\u003eT3\u003c/em\u003e and \u003cem\u003eT4\u003c/em\u003e. Upon receiving a result from a Coordinator or a user, the Mediator records it (using \u003cem\u003eT3\u003c/em\u003e or \u003cem\u003eT4\u003c/em\u003e) in the \u003cem\u003eAllTheResults\u003c/em\u003e place and notifies the \u003cem\u003eResultsNotification\u003c/em\u003e place of the existence of new results.\u003c/p\u003e\n \u003cp\u003eThe portion of the network on the right, consisting of transitions \u003cem\u003eT5\u003c/em\u003e and \u003cem\u003eT6\u003c/em\u003e, examines the collection of results that have been saved (\u003cem\u003eT5\u003c/em\u003e). If those results are deemed adequate, they are combined (\u003cem\u003eT6\u003c/em\u003e) to produce the result, which is then presented to the user. Should the outcomes be insufficient, the Mediator continues to wait for additional results. As soon as fresh data are received, it will begin an analysis (\u003cem\u003eT5\u003c/em\u003e) once more. It is notified of this event if one or more tokens are present in the \u003cem\u003eResultsNotification\u003c/em\u003e location.\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eT1.T2.((T3|T4).T5)\u003c/em\u003e \u003csup\u003en\u003c/sup\u003e \u003cem\u003e.T6\u003c/em\u003e is the language of the net, which provides all conceivable behaviors, where n is the total number of answers to the questions the coordinators and user submitted that the mediator received. The final state is reached by the execution of \u003cem\u003eT6\u003c/em\u003e transition which consumes \u003cem\u003eWaitingResults\u003c/em\u003e token.\u003c/p\u003e\n\u003c/div\u003e"},{"header":"5 OPN simulation","content":"\u003cp\u003eIn addition to the formal specification of the OS roles given above, we performed a simulation to verify the behavioral aspect of the mediator role previously specified. We have chosen as a simulator the Renew tool (the Reference Net Workshop) developed at the Department of Computer Science at the University of Hamburg. Renew is freeware (\u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttp://www.renew.de\u003c/span\u003e\u003c/span\u003e), written in Java. It allows the graphic editing of the PN which is also used as a synoptic during the simulation.\u003c/p\u003e\n\u003cp\u003eThe simulation of the behavior of the Mediator role reveals two possible scenarios but which both lead to the desired end state (expressed by a token in place of the OPN of the previous section and which informs the user of the presence of a final response to his request). These scenarios, presented in Figs. \u003cspan class=\"InternalRef\"\u003e3\u003c/span\u003e, correspond to the participation or not of the user when formulating the final response. The simulation allowed us to validate that the network was not blocked in both cases. It should be noted that the T5 transition has been split into two sub-transitions (T5.1 and T5.2) since the Renew tool does not allow us to express the validation conditions.\u003c/p\u003e\n\u003cp\u003eTo verify that all transitions can be crossed, we ran a step-by-step simulation for both scenarios. This simulation allowed us to validate the near liveliness of the network. Figure\u0026nbsp;4 shows this stepwise execution of the model relating to the second scenario (with user interaction T4).\u003c/p\u003e\n\u003cp\u003eThe simulation made it possible to verify the following properties:\u003c/p\u003e\n\u003cp\u003e- Unfinished termination: termination is not guaranteed because we have an analysis loop of the response (((T3|T4).T5)\u003csup\u003en\u003c/sup\u003e) which is intentionally modeled as an iteration which allows it to take into account responses as they arrive.\u003c/p\u003e\n\u003cp\u003e- The accessibility of the final state: there is an evolution of the network leading from the submission of the question (initial state) to the resolution of this question (final state).\u003c/p\u003e\n\u003cp\u003e- Liveness of our network: there is for each action (transition) a configuration of the network allowing its execution.\u003c/p\u003e"},{"header":"6 Role implementation","content":"\u003cp\u003eOnce the termination, final state accessibility, and liveness properties have been validated through simulation, it would be interesting to proceed to the implementation stage and generate code that complies with the specification.\u003c/p\u003e\n\u003cp\u003eSpecifying roles using OPN allows the designer to generate the skeleton of the class related to that role. Although the process is currently manual, automation is feasible by creating an API between the E-NetObject [21] tool, which is a OPN editor, and a MAS development platform such as JADE [22], AgentBuilder [23], or MADKIT [24], enabling automatic generation of role skeletons. The API will start by parsing the XML file generated by the E-NetObject tool, which represents a snapshot of the edited net. This step will identify all designed entities such as transitions, manipulated objects, and interventions. The second step will involve applying a set of transitioning rules that will translate the identified entities in the first step into Java code of the class relevant to that role.\u003c/p\u003e\n\u003cp\u003eThe choice of the Java language is arbitrary since most software editors for MAS are based on this language. Each MAS development platform has a set of predefined functions for each agent, so the API must by default integrate these methods. One of these methods is the one we will call Life (the naming varies from one platform to another), which implements the agent\u0026apos;s behavior throughout its lifecycle.\u003c/p\u003e\n\u003cp\u003eThe transitioning rules from an OPN to Java code can take the following form:\u003c/p\u003e\n\u003cp\u003e- Each transition is a method that takes the incoming object as a parameter and produces the outgoing object as a result.\u003c/p\u003e\n\u003cp\u003e- Each interaction is a message sent or received with a parameter which is the KQML performative.\u003c/p\u003e\n\u003cp\u003e- Each object manipulated by the role, and which is external to the system to be implemented is a parameter of the Life method. For example, in our CIG context, external objects are resources and the initial request formulated by the user.\u003c/p\u003e\n\u003cp\u003e- The Life method will implement the networking language, which is in our case: \u003cem\u003eT1.T2.((T3|T4).T5)\u003c/em\u003e \u003csup\u003en\u003c/sup\u003e \u003cem\u003e.T6\u003c/em\u003e as described in section 3. This method takes as parameters all external objects to the system. In our case, these objects are the Info Model, the task Model (as Ontology type in our case), and the user\u0026apos;s initial question (String type).\u003c/p\u003e\n\u003cp\u003eBy applying these transition rules, the skeleton of the resulting Java class is shown in the following Fig. \u003cspan class=\"InternalRef\"\u003e5\u003c/span\u003e.\u003c/p\u003e"},{"header":"7 Quantitative assessment of the Organizational Structure","content":"\u003cp\u003eThe two organizational levels of the OM need to be accompanied with tools and metrics, to make the evaluation process possible, before a real deployment of the multi-agent system. In this section, we will focus on the quantitative evaluation of the first organization level which is the Organizational Structure. We refer readers to [8] for qualitative evaluation of the communication in the concrete organizational level.\u003c/p\u003e\n\u003cdiv id=\"Sec10\" class=\"Section2\"\u003e\n \u003ch2\u003e7.1 Evaluation criteria\u003c/h2\u003e\n \u003cp\u003eThe criteria used to evaluate the performance of the OS are inspired from [4, 16]. The authors applied quantitative concepts from graph theory in order to assess the structure used to implement the MAS. We will briefly introduce these criteria but for a complete explanation we refer readers to [4, 16, 9].\u003c/p\u003e\n \u003cp\u003eThe organizational properties which are evaluated are:\u003c/p\u003e\n \u003cp\u003e- Robustness: how the OS is stable in an unpredictable environment\u003c/p\u003e\n \u003cp\u003e- Flexibility: the capability of an organization to adapt to changing circumstances\u003c/p\u003e\n \u003cp\u003e- Efficiency: how to achieve the global goal of the system with the minimum of resources.\u003c/p\u003e\n \u003cp\u003eTo evaluate these properties, the authors introduced three equations to measure specific graph-theoretical aspects of organizational structures which are:\u003c/p\u003e\n \u003cp\u003e- Connectedness: expresses how strongly the roles are linked with one another\u003c/p\u003e\n \u003cp\u003e- Economy: how we can keep a system connected with the minimum of links\u003c/p\u003e\n \u003cp\u003e- Univocity: expresses the absence of redundant links within the same role\u003c/p\u003e\n \u003cp\u003eEach one of these structural aspects is calculated within one of these three structural dimensions which described the nature of links between each role:\u003c/p\u003e\n \u003cp\u003e- Authority dimension: it implies that a role can delegate a task to another role.\u003c/p\u003e\n \u003cp\u003e- Coordination dimension: which represent the knowledge exchange between roles.\u003c/p\u003e\n \u003cp\u003e- Control dimension: the fact that a role must monitor the activities of another role.\u003c/p\u003e\n \u003cp\u003eThe organizational properties, which are robustness, flexibility, and efficiency, are measured from graphs representative of the different roles and the different types of links that exist between them. The authors provided a vector of values which represent the optimal results that we can obtain for each one of these properties. During the two next sections, we will present the role graphs from where we will make the calculations, and we will compare our results with these optimal vectors of values.\u003c/p\u003e\n\u003c/div\u003e\n\u003cdiv id=\"Sec11\" class=\"Section2\"\u003e\n \u003ch2\u003e7.2 Role graphs\u003c/h2\u003e\n \u003cp\u003eIn this section, we will introduce the representative graphs of the different roles of the Organizational Structure according to the three structural dimensions of control, authority, and coordination. Since the CIGS was conceived to resolve the problem of travel organization, the OS was strictly dependent on the problem resolving process. As shown in Fig. \u003cspan class=\"InternalRef\"\u003e6\u003c/span\u003e, the problem is decomposed into four elementary tasks which are the visits, the accommodation, the transport, and the weather report. The organization of accommodations is extremely related to the transport as they should have the same arrival and departure dates. Each elementary task will search information from a different Information Sources. As a result, the OS includes the following roles:\u003c/p\u003e\n \u003cp\u003e- A Mediator, overseeing the CIG process,\u003c/p\u003e\n \u003cp\u003e- As many Coordinators as there are basic tasks in the trip organization problem. In our case there are four: visits, the accommodation, the transport and the weather report. These coordinators will be titled, in the role graph, respectively, Coordinator 1, Coordinator 2, Coordinator 3 and Coordinator 4.\u003c/p\u003e\n \u003cp\u003e- Since a Matchmaker can be specialized in more than one field, we supposed that we will have three. Therefore, we have three Matchmakers respectively rated Matchmaker1, Matchmaker 2 and Matchmaker 3.\u003c/p\u003e\n \u003cp\u003e- As many Translators as there are elementary tasks. In our case, we chose to associate a translator with each coordinator. We will then have four translators labeled respectively Translator 1, Translator 2, Translator 3 and Translator 4.\u003c/p\u003e\n \u003cp\u003eTo facilitate the reading of the representative diagram of the different types of links between the roles identified in our OS, we have chosen to present a graph for each structural dimension (control, authority, and coordination) already introduced in section 5.1:\u003c/p\u003e\n \u003cp\u003eThe \u0026quot;control\u0026quot; dimension (see Fig. \u003cspan class=\"InternalRef\"\u003e7\u003c/span\u003e): the mediator has a control link over all the coordinators allowing him to assess the provided results.\u003c/p\u003e\n \u003cp\u003eThe \u0026ldquo;authority\u0026rdquo; dimension (cf. Figure \u003cspan class=\"InternalRef\"\u003e8\u003c/span\u003e): The Mediator has both a link of authority and control with the coordinator roles, which allows it to both delegate the sub-objectives to them and assess the returned results. In turn, the Coordinators have a link of authority on the one hand over the Matchmakers by requiring them to provide the addresses of information sources likely to contain the desired result, and on the other hand over the Translators by ordering them to query and return partial results from these sources.\u003c/p\u003e\n \u003cp\u003eThe \u0026quot;coordination\u0026quot; dimension (see Fig. \u003cspan class=\"InternalRef\"\u003e9\u003c/span\u003e): The Coordinator can interact with another Coordinator in the case of solving interrelated problems which are expressed through a coordination link. Message feedback as responses to requests between the different roles is presented by a coordination link. Finally, the Translators publish their skills to the Matchmakers, which also translate into a coordination link.\u003c/p\u003e\n\u003c/div\u003e\n\u003cdiv id=\"Sec12\" class=\"Section2\"\u003e\n \u003ch2\u003e7.3 Results and interpretations\u003c/h2\u003e\n \u003cp\u003eThe results obtained from the application of the equations provided in [4, 16] as well as the maximum values which optimize the three structural properties are given by the following tables:\u0026nbsp;\u003c/p\u003e\n \u003ctable id=\"Tab1\" border=\"1\"\u003e\n \u003ccaption language=\"En\"\u003e\n \u003cdiv class=\"CaptionNumber\"\u003eTable 1\u003c/div\u003e\n \u003cdiv class=\"CaptionContent\"\u003e\n \u003cp\u003eRobustness\u003c/p\u003e\n \u003c/div\u003e\n \u003c/caption\u003e\n \u003cthead\u003e\n \u003ctr\u003e\n \u003cth align=\"left\"\u003e\n \u003cp\u003eSTRUCTURAL PROPERTY\u003c/p\u003e\n \u003c/th\u003e\n \u003cth align=\"left\"\u003e\n \u003cp\u003eOPTIMAL VALUES\u003c/p\u003e\n \u003c/th\u003e\n \u003cth align=\"left\"\u003e\n \u003cp\u003eOBTAINED VALUES\u003c/p\u003e\n \u003c/th\u003e\n \u003c/tr\u003e\n \u003c/thead\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd align=\"left\"\u003e\n \u003cp\u003eEconomy\u003csub\u003ecoordination\u003c/sub\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd align=\"char\"\u003e\n \u003cp\u003e0\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd align=\"char\"\u003e\n \u003cp\u003e0,94\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align=\"left\"\u003e\n \u003cp\u003eUnivocity\u003csub\u003eauthority\u003c/sub\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd align=\"char\"\u003e\n \u003cp\u003e0\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd align=\"char\"\u003e\n \u003cp\u003e0,91\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align=\"left\"\u003e\n \u003cp\u003eConnectivity\u003csub\u003ecoordination\u003c/sub\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd align=\"char\"\u003e\n \u003cp\u003e1\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd align=\"char\"\u003e\n \u003cp\u003e1\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\n \u003cdiv class=\"gridtable\"\u003e\u0026nbsp;\u003ctable id=\"Tab2\" border=\"1\"\u003e\n \u003ccaption language=\"En\"\u003e\n \u003cdiv class=\"CaptionNumber\"\u003eTable 2\u003c/div\u003e\n \u003cdiv class=\"CaptionContent\"\u003e\n \u003cp\u003eFlexibility\u003c/p\u003e\n \u003c/div\u003e\n \u003c/caption\u003e\n \u003cthead\u003e\n \u003ctr\u003e\n \u003cth align=\"left\"\u003e\n \u003cp\u003eSTRUCTURAL PROPERTY\u003c/p\u003e\n \u003c/th\u003e\n \u003cth align=\"left\"\u003e\n \u003cp\u003eOPTIMAL VALUES\u003c/p\u003e\n \u003c/th\u003e\n \u003cth align=\"left\"\u003e\n \u003cp\u003eOBTAINED VALUES\u003c/p\u003e\n \u003c/th\u003e\n \u003c/tr\u003e\n \u003c/thead\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd align=\"left\"\u003e\n \u003cp\u003eEconomy\u003csub\u003ecoordination\u003c/sub\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd align=\"char\"\u003e\n \u003cp\u003e0\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd align=\"char\"\u003e\n \u003cp\u003e0,94\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align=\"left\"\u003e\n \u003cp\u003eConnectivity\u003csub\u003eauthority\u003c/sub\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd align=\"char\"\u003e\n \u003cp\u003e0\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd align=\"char\"\u003e\n \u003cp\u003e1\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align=\"left\"\u003e\n \u003cp\u003eConnectivity\u003csub\u003ecoordination\u003c/sub\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd align=\"char\"\u003e\n \u003cp\u003e1\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd align=\"char\"\u003e\n \u003cp\u003e1\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\n \u003c/div\u003e\n \u003cdiv class=\"gridtable\"\u003e\u0026nbsp;\u003ctable id=\"Tab3\" border=\"1\"\u003e\n \u003ccaption language=\"En\"\u003e\n \u003cdiv class=\"CaptionNumber\"\u003eTable 3\u003c/div\u003e\n \u003cdiv class=\"CaptionContent\"\u003e\n \u003cp\u003eEfficiency\u003c/p\u003e\n \u003c/div\u003e\n \u003c/caption\u003e\n \u003cthead\u003e\n \u003ctr\u003e\n \u003cth align=\"left\"\u003e\n \u003cp\u003eSTRUCTURAL PROPERTY\u003c/p\u003e\n \u003c/th\u003e\n \u003cth align=\"left\"\u003e\n \u003cp\u003eOPTIMAL VALUES\u003c/p\u003e\n \u003c/th\u003e\n \u003cth align=\"left\"\u003e\n \u003cp\u003eOBTAINED VALUES\u003c/p\u003e\n \u003c/th\u003e\n \u003c/tr\u003e\n \u003c/thead\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd align=\"left\"\u003e\n \u003cp\u003eEconomy\u003csub\u003ecoordination\u003c/sub\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd align=\"char\"\u003e\n \u003cp\u003e1\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd align=\"char\"\u003e\n \u003cp\u003e0,94\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align=\"left\"\u003e\n \u003cp\u003eEconomy\u003csub\u003econtrol\u003c/sub\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd align=\"char\"\u003e\n \u003cp\u003e1\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd align=\"char\"\u003e\n \u003cp\u003e1\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align=\"left\"\u003e\n \u003cp\u003eEconomy\u003csub\u003eauthority\u003c/sub\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd align=\"char\"\u003e\n \u003cp\u003e1\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd align=\"char\"\u003e\n \u003cp\u003e1\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\n \u003c/div\u003e\n \u003cp\u003e\u003cbr\u003e\u003c/p\u003e\n \u003cp\u003eFrom these results, and by comparing them with the vector of values that optimize the three organizational properties, we can draw the following conclusions:\u003c/p\u003e\n \u003cp\u003e- The organization is not strong. In fact, two out of three values are far from the optimal values, which are Economy-coordination and Univocity-authority. Let us recall in this context that robustness induces the system\u0026apos;s ability to resist in the face of unpredictable events such as the failure of an agent, playing a given role, to provide a certain service. However, and as we have defined the current OS, very little redundancy is present, so there is no alternative for delegation in the case of failure. During execution, a Coordinator may judge that the result returned by a Translator is irrelevant and consider the recruitment of another Translator: which is not considered in our modeling. The lack of robustness is also due to the specialization of our agents which are therefore not interchangeable. In this context, and to fix this weakness, we must integrate the possibility of an auto-adaptation of agent goals in case of unpredictable events as described in [17].\u003c/p\u003e\n \u003cp\u003e- The organization is not very flexible because we have a very centralized, very economical organization and therefore with very little redundancy in terms of coordination. The values of the Economy-Coordination and Connectivity-Authority dimensions are far from the optimal values. In our case, and to restrict the information exchange between agents, and to reduce the cost of communication, the recruitment of agents is centralized at the level of the Mediator and Coordinators who exercise authority over the rest of the agents. In short, flexibility has been sacrificed for the benefit of the economy in terms of interactions. A solution to the lack of flexibility in the MAS organization acting in uncertain environments is proposed in [15]. This can be the subject of future works.\u003c/p\u003e\n \u003cp\u003e- The organization is very efficient. Indeed, the three values of this criterion are almost optimal. This is explained by the fact that we have optimal modeling at the level of each dimension, so a minimum structure to coordinate, control and direct. Only the mediator and the coordinators have authority over the other agents, and the coordination and control links are reduced to the essential. The effectiveness of the organization as defined in [3] is on its optimal value as the goals are well accomplished by the agents.\u003c/p\u003e\n\u003c/div\u003e"},{"header":"8 Conclusion and future work","content":"\u003cp\u003eIn this paper we have proposed a formal specification of the identified roles in the abstract level of the Organizational Model (the Organizational Structure) of a Multi-Agent System. The chosen formalism was the Object Petri Nets. This formalism enabled us to formally present the internal actions, interventions, and the rules of sequence of the various roles. This representation formalism also has the advantage of being simulated in order to validate the properties of the model. We were then able to validate the behavioral aspects of the roles via a simulation with the Renew simulator. Properties such as non-blocking and liveliness of the model have been verified. We also proposed a way to automatically generate the code of each role based on its OPN specification. We are conscient that the automatic transitioning from the design to the implementation require more technical studies, but we are convinced that is feasible. In addition, we made a quantitative evaluation of our OS based on graph-theoretical measures. This evaluation concern organizational properties such as flexibility, robustness and efficiency and was carried through a Cooperative Information Gathering System. The objective was to provide a comprehensive approach for defining and verifying the abstract level of the multi-agent organizations, even though the evaluation criteria originate from [4, 16].\u003c/p\u003e"},{"header":"Declarations","content":"\u003ch2\u003eAuthor Contribution\u003c/h2\u003e\u003cp\u003eOnly I.B. wrote the whole article\u003c/p\u003e"},{"header":"References","content":"\u003col\u003e\n\u003cli\u003eA. Artikis and J. Pitt, 2001, A Formal Model of Open Agent Societies. \u003cem\u003eIn: 5\u003csup\u003eth \u003c/sup\u003eInternational Conference on Autonomous Agents (AA\u0026rsquo;01)\u003c/em\u003e, Montreal-Canada, pp. 192-193.\u003c/li\u003e\n\u003cli\u003eAfsaneh Fatemi, Kamran Zamanifar, and Naser Nematbakhsh, 2001. Adaptive Team-Based Multi-Agent Organizational Model: A Case in Rescue Systems. \u003cem\u003eInternational Journal of Computer Science and Information Technology\u003c/em\u003e 3.2, pp. 165\u0026ndash;175.\u003c/li\u003e\n\u003cli\u003eDaniel D. Corkill, Edmund H. Durfee, Victor R. Lesser, Huzaifa Zafar, and Chongjie Zhang,2011. Organizationally Adept Agents. In \u003cem\u003eWorking Notes of the AAMAS-11 Workshop on Coordination, Organizations, Institutions, and Norms in Multiagent Systems\u003c/em\u003e (COIN).\u003c/li\u003e\n\u003cli\u003eGrossi, D., Dignum, F., Dignum, V., Dastani, M., Royakkers, L., 2006. Structural evaluation of agent organizations. \u003cem\u003e5th International Joint Conference on Autonomous agents and Multiagent systems\u003c/em\u003e, pp. 1110-1112.\u003c/li\u003e\n\u003cli\u003eHosny Ahmed Abbas, Samir Ibrahim Shaheen, Mohammed Hussein Amin, 2015. Organization of Multi-Agent Systems: An Overview. \u003cem\u003eJournal of Intelligent Information Systems\u003c/em\u003e, Vol. 4, No. 3, pp. 46-57.\u003c/li\u003e\n\u003cli\u003eI. Bouslimi, Khaled Gh\u0026eacute;dira and Chihab Hanachi, 2006. An Agent-based Organizational Model for Cooperative Information Gathering, \u003cem\u003eIn: Proceeding of the second International Conference on Signal-Image Technology and Internet-based Systems, SITIS\u003c/em\u003e, Hammamet, Tunisia, pp. 414-425.\u003c/li\u003e\n\u003cli\u003eI. Bouslimi, Chihab Hanachi, Hassan Tout and Khaled Gh\u0026eacute;dira, 2008. Coordination framework for Cooperative Information Gathering. \u003cem\u003eIn: International Journal of Advanced Intelligence Paradigms, Inderscience Publishers\u003c/em\u003e, Vol. 1, No. 1, pp. 60-79.\u003c/li\u003e\n\u003cli\u003eI. Bouslimi, C. Hanachi and K. Gh\u0026eacute;dira, 2014. An Experimental Evaluation of Communication in an Organization-Based Multi-agent System. \u003cem\u003eIEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (IAT)\u003c/em\u003e, pp. 72-78.\u003c/li\u003e\n\u003cli\u003eInes Thabet, Issam Bouslimi, Chihab Hanachi and Khaled Ghedira, 2011. A Multi-agent Organizational Model for Grid Scheduling. \u003cem\u003eIn\u003c/em\u003e\u003cem\u003e:\u003c/em\u003e\u003cem\u003e \u003c/em\u003e\u003cem\u003eKES International Conference (KES-AMSTA 2011\u003c/em\u003e),Manchester, UK, Vol. 6682, pp. 148-158. \u003c/li\u003e\n\u003cli\u003eJensen, Andreas \u0026amp; Villadsen, J\u0026oslash;rgen, 2013. A comparison of organization-centered and agent-centered multi-agent systems. \u003cem\u003eArtificial Intelligence Research. 2. 10.5430/air.v2n3p5\u003c/em\u003e9.\u003c/li\u003e\n\u003cli\u003eJ. Ferber, T. Stratulat, J. Tranier,2009. Towards an integral approach of organizations in multi-agent systems: the MASQ approach. Chapter book of Multi-agent Systems: Semantics and Dynamics of Organizational Models in Virginia Dignum (Ed), IGI.\u003c/li\u003e\n\u003cli\u003eJ. Ferber and O. Gutknecht, 1998, A Meta-Model for the Analysis and Design of Organizations in Multi-Agent Systems. \u003cem\u003eIn: 3\u003csup\u003erd\u003c/sup\u003e International Conference on Multi-Agents Systems, (ICMAS\u0026rsquo;98), IEEE Computer Society\u003c/em\u003e. Paris, France. \u003c/li\u003e\n\u003cli\u003eJacques Ferber, Olivier Gutknecht, and Fabien Michel, 2004. From Agents to Organizations: an Organizational View of Multi-Agent Systems. \u003cem\u003eIn: Agent-Oriented Software Engineering (AOSE) IV\u003c/em\u003e, P. Giorgini, J\u0026ouml;rg M\u0026uuml;ller, James Odell, eds, Melbourne, (2003), LNCS 2935, pp. 214-230. \u003c/li\u003e\n\u003cli\u003eJ.F. H\u0026uuml;bner, J. S. Sichman, O. Boissier, 2002. MOISE+: towards a structural, functional, and deontic model for MAS organization. \u003cem\u003eIn: the First International Joint Conference on Autonomous Agents \u0026amp; Multi-Agent Systems, (AAMAS\u0026rsquo;02)\u003c/em\u003e, Bologna-Italy pp. 501-502.\u003c/li\u003e\n\u003cli\u003eKeogh, Kathleen, and Liz Sonenberg. 2020. Designing Multi-Agent System Organizations for Flexible Runtime Behavior. \u003cem\u003eApplied Sciences\u003c/em\u003e 10, no. 15: 5335. https://doi.org/10.3390/app10155335\u003c/li\u003e\n\u003cli\u003eLoris Penserini, David Grossi, Frank Dignum, Virginia Dignum, Huib Aldewereld. 2009. Evaluating Organizational Configurations. \u003cem\u003eIn \u003c/em\u003e\u003cem\u003eProceedings\u003c/em\u003e\u003cem\u003e of The 2009 IEEE/WIC/ACM International Conferences on Intelligent Agent Technology (IAT-09), IEEE CS Press\u003c/em\u003e, Milano, Italy.\u003c/li\u003e\n\u003cli\u003eMatteo Baldoni, Cristina Baroglio, Roberto Micalizio, Stefano Tedeschi, 2023. Accountability in multi-agent organizations: from conceptual design to agent programming. In Autonomous Agents and Multi-Agent Systems 37. https://doi.org/10.1007/s10458-022-09590-6\u003c/li\u003e\n\u003cli\u003eSibertin-Blanc, 1985. High-level Petri nets with Data structure. \u003cem\u003e6th European workshop on Petri nets and applications\u003c/em\u003e, Espoo (Finland).\u003c/li\u003e\n\u003cli\u003eTim Finin, Richard Fritzson, Don McKay, and Robin McEntire, 1994. KQML as an agent communication language. \u003cem\u003eIn Proceedings of the third international conference on Information and knowledge management (CIKM \u0026apos;94)\u003c/em\u003e. New York, NY, USA, pp. 456\u0026ndash;463.\u003c/li\u003e\n\u003cli\u003eZambonelli, N. R. Jennings and M. Wooldrige, 2003. Developing Multi-Agent Systems: The Gaia Methodology. \u003cem\u003eIn ACM Transactions on Software Engineering Methodology\u003c/em\u003e. pp. 317-370.\u003c/li\u003e\n\u003cli\u003eFr\u0026eacute;d\u0026eacute;ric Raclot, David Andreu, Th\u0026eacute;r\u0026egrave;se Libourel Rouge, Robin Passama. E-NetObject: Un Editeur de R\u0026eacute;seaux de Petri \u0026agrave; Objets. 02180, 2002, pp.40. fflirmm-00269413f\u003c/li\u003e\n\u003cli\u003ehttps://jade.tilab.com/, 10/10/2023.\u003c/li\u003e\n\u003cli\u003ehttps://www.agentbuilder.com, 12/01/2024.\u003c/li\u003e\n\u003cli\u003ehttps://www.madkit.net/madkit/index.php, 01/10/2023.\u003c/li\u003e\n\u003cli\u003eD. Grossi, F. Dignum, M. Dastani, and L. Royakkers. Foundations of organizational structures in multiagent systems. In AAMAS \u0026rsquo;05: Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, pages 690\u0026ndash;697, New York, NY, USA, 2005. ACM.\u003c/li\u003e\n\u003cli\u003eD. Grossi, F. Dignum, V. Dignum, M. Dastani, and L. Royakkers. Structural aspects of the evaluation of agent organizations. In COIN@ECAI 2006, 2006.\u003c/li\u003e\n\u003cli\u003eDignum, V. (Ed.), 2009. Handbook of Research on Multi-Agent Systems: Semantics and Dynamics of Organizational Models: Semantics and Dynamics of Organizational Models. IGI Global.\u003c/li\u003e\n\u003cli\u003eWeyns, D., Haesevoets, R., \u0026amp; Helleboogh, A, 2010. The MACODO organization model for context-driven dynamic agent organizations. ACM Transactions on Autonomous and Adaptive Systems (TAAS), 5(4), 16.\u003c/li\u003e\n\u003cli\u003eCelaya, Jose \u0026amp; Desrochers, Alan \u0026amp; Graves, Robert. (2007). Modeling and Analysis of Multi-agent Systems using Petri Nets. Journal of Computers - JCP. 4. 1439 - 1444. 10.1109/ICSMC.2007.4413960.\u003c/li\u003e\n\u003cli\u003eS. Sabeg, T. M. Maarouk and M. El Habib Souidi, \u0026quot;Formal Specification and Verification for Organization-based systems : A Survey,\u0026quot; \u003cem\u003e2022 4th International Conference on Pattern Analysis and Intelligent Systems (PAIS)\u003c/em\u003e, Oum El Bouaghi, Algeria, 2022, pp. 1-6, doi: 10.1109/PAIS56586.2022.9946660.\u003c/li\u003e\n\u003c/ol\u003e"}],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":true,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":false,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":false,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Multi-Agent Systems, Organizational Model, Organizational Structure, Cooperative Information Gathering System","lastPublishedDoi":"10.21203/rs.3.rs-4197325/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-4197325/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eTo design complex Multi-Agent Systems (MAS), the use of high-level abstraction concepts such as roles, protocols, and groups, makes the task relatively easier and closer to the reality of the system or domain that we want to simulate or create. These concepts were introduced through the multi-agent Organizational Models (OM) which can be seen at two levels: i) an abstract level which is the Organizational Structure (OS) and ii) a concrete level which is the Concrete Organization (CO) to be deployed and executed. This article is dedicated to the formal specification and validation of the identified roles in the Organizational Structure before a real deployment to generate systems with organizations exhibiting good qualities. Also, a proposal of a set of steps to automatically generate the code of the designed agent will be presented. In addition, the evaluation of some organizational aspects will be done at the abstract level makes it possible to adjust the design to remedy any failures before a real instantiation. The application domain used in this context, is a Cooperative Information Gathering System (CIGS) for travel organization.\u003c/p\u003e","manuscriptTitle":"Multi-Agent Organizational Structure: specification and validation","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-04-05 16:37:21","doi":"10.21203/rs.3.rs-4197325/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"d751ba81-78ed-4c82-a1e6-4b42fda5d776","owner":[],"postedDate":"April 5th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2024-06-02T16:53:18+00:00","versionOfRecord":[],"versionCreatedAt":"2024-04-05 16:37:21","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-4197325","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-4197325","identity":"rs-4197325","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}