3.1.1 Openness management

The existing approaches in this context were dedicated to dealing with addition, removal and evolution of agents in MAS. We mention mainly: the centralized, the distributed and the hybrid model.

1. (i) The Centralized Model (Decker et al., Reference Decker, Sycara and Williamson1997): it is based in a specific agent called broker. When an agent is integrated in the system, it must provide its characteristics to the broker, which updates itself according to the capabilities and requirements of the new agent. Any agent leaving the system has only to signal his removal to the broker.

2. (ii) The Distributed Model (Sehaba, Reference Sehaba2002): in this model, agents communicate by broadcasting messages. The addition of a new agent requires to warn all the existing agents of his presence and to ask for their knowledge. When modifying an agent, this latter must send a message to all the agents in the system and they will update their representations. In a similar way, the removal of an agent requires him to signal his departure to all the elements.

3. (iii) The Hybrid Model (Sehaba, Reference Sehaba2002): the MAS is decomposed into groups of connections. In order to integrate the system, an agent must send its characteristics to the broker which assigns it to the appropriate group. Consequently, the agent will present itself to the elements of the group in question and receives their representations. As for the removal of an agent, this latter has just to report his departure to its acquaintances. Similarly, an agent having evolved must signal the disappearance of some of its characteristics and have to introduce its new functionalities to its acquaintances.

3.1.2 Openness design

Openness here is seen as an engineering challenge. The design of open MAS was considered as a topic of a major concern and researchers had started to propose architectural models and suitable infrastructures and mechanisms to support MAS structural openness. We mention as example here the Peer-to-Peer model which is the basis of some software frameworks mainly Jade as well as some reorganizational models.

1. (i) Peer to Peer Model: this model is suitable for designing open MAS thanks to its ability to scale up to thousands or even millions of nodes. The addition or the removal of an agent from MAS, whose conception is based on such model, causes a change to the whole system’s structure. The use of this trend implies handling some openness aspects such as intrusion and exception detection, workflow management and security issues (Aldeeb et al., Reference Aldeeb, Crockett and Stanatan2008; Platon et al., Reference Platon, Sabouret and Honiden2008; Bijani, Reference Bijani2012).

2. (ii) Reorganizational Model: they are based on what is called OCMAS (Organization-Centered MAS), Massonet et al. (Reference Massonet, Deville and Nve2002). This approach gives a big attention to the MAS structure. It defines the logical relationship between agents and their organizations regardless of the agents behaviour and activities. We mention as example the AGR model (Agent/Group/Role), also called AALAADIN, and the AGRE model. We also mention GoOrg model (Amaral & Hübner Reference Amaral and Hübner2019). It is a structural model defined in order to generate an automated design of the open MAS. It uses as input a goals tree, the necessary skills to achieve the goal and the predicted workload and throughput. It generates as output an organizational chart.

3.1.3 Openness simulation

Some models are proposed in the literature in order to represent and simulate structural openness in MAS. We mention, in this context, the algebraic models and more particularly Hendrick’s work (Hendrickx & Martin Reference Hendrickx and Martin2016). In this work, integers are used to label the agents: the set of agents present in the system at time t is denoted by N(t) and its cardinality is denoted by n(t). Each agent i holds a value $x_i(t)\in IR$. At each time t, one of the following three events may occur causing a change in the MAS structure:

1. (i) Departure of an agent: it is mathematically expressed as follows: one uniformly randomly selected agent $i\in {N(t)}$ leaves the system so that $N(t+1)=N(t)/i$ and $n(t+1)= n(t)-1$. This event may only occur when $n(t)>0$;

2. (ii) Arrival of an agent: one new agent $i \in N(s)$ $\forall$ $s<t$, joins the system so that $N(t+1)= N(t)\cup i$ and $n(t+1)=n(t)+1$. The initial value $x_i(t+1)\in IR $ of the arriving agent is drawn independently from a constant distribution D with mean 0 and variance $\sigma^{2}$;

3. (iii) Gossip between two agents: two agents $i,j \in N(t)$ are uniformly randomly and independently selected among the n(t) agents and they update their values $x_i$ and $x_j$ by performing a pairwise average: $x_i(t+1)= x_j(t+1)=(x_i(t)+x_j(t))/2$.

3.1.4 Openness evaluation

Recently, the topic of performance evaluation in MAS has interested some researchers. In particular, structural openness (Hattab et al., Reference Hattab, Ben Hmida and Lejouad Chaari2017) and structural controllability (Liu et al., Reference Liu, Lin and Chen2013; Guan et al., Reference Guan, Ji and Zhang2017; Zegzhda et al., Reference Zegzhda, Stephanora and Suprun2017) were assessed using graph theory.

1. (i) Evaluation of structural openness: in Hattab et al. (Reference Hattab, Ben Hmida and Lejouad Chaari2017), evolving graphs were selected for assessing structural openness in MAS thanks to their ability to authorize any combination of addition and removal of entities. By applying a number of graph theory properties, some measures were defined in order to evaluate the structural changes at the level of MAS topology. We mention as example: alpha index, degree of structural extensibility, structural impact, transitivity, etc.

   Actually, the work described above has a specific goal: the evaluation of structural openness in a generic way. The proposed approach was validated on a multi-agent road traffic application and could be applied on other domains since its generic nature. The difference between that work and the present one is that the first is generic only in the context of structural openness. However, the second aims to define a model which is generic in the sense that it could take in consideration any type of openness and any application domain.

2. (ii) Evaluation of structural controllability: to decide if an MAS is structurally controllable or not, dynamic graphs were used. For example, in Angluin et al. (Reference Angluin, Aspnes, Fischer and Jiang2008), it was shown that an MAS is structurally controllable if and only if the union graph is connected. In Zegzhda et al. (Reference Zegzhda, Stephanora and Suprun2017), the goal was to compute controllability boundaries. For this purpose, a regular graph in the form of tree with virtual nodes was proposed and some methods of calculating the number of vertices were applied. Similarly, in Guan et al. (Reference Guan, Ji and Zhang2017), the controllability of MAS was quantitatively studied. The latter work supposed that the interconnection between agents is directed, and it employed the notions of distance partition and almost equitable partition for the calculation;

3.2.1 The design of open MAS

The design of open MAS has been primarily seen as a major preoccupation since the AOSE methodology works (Massonet et al., Reference Massonet, Deville and Nve2002). The latter were proposed in order to describe an MAS by covering functional and non-functional goal analysis. We mention as example here AgentUML, Gaia and MAS-CommonKads. Actually, these modelling languages are based on four main concepts: Organization, Role, Goal and Task. The drawback of such methodologies is their static and deterministic nature which contradicts with openness notion. Indeed, modifications at the level of the previously mentioned concepts were not taken into account. Moreover, the uncertainty in the deployment context, tasks and requirements was not considered. That’s why, looking for new methods to design open MAS was in urgent need. We mention as example: the role-based model, the service-oriented approach, the logic-based model and the normative models.

1. (i) The Role-Based Model (Xu et al., Reference Xu, Zhang and Patel2007): it consists in a three-layer model namely, agent society, role space and role organization. In this model, openness appears at three levels and it is defined in this work as the dynamic additions and removals of agent roles during runtime;

2. (ii) The Service-Oriented Model: such model was used to deploy large-scale open MAS like THOMAS (Carrascosa et al., Reference Carrascosa, Giret, Julian, Rebollo, Argente and Botti2009; Argente et al., Reference Argente, Botti, Carrascosa, Giret, Julian and Rebollo2011). It was specifically addressed for the design of open organizations and was proposed in order to allow agents to handle the problem of discovery and composition in dynamic and changing open environments. It includes two categories of services: openness management services and structural services. Another work was recently done in this context. It consists in proposing an open based-services architecture in order to engineer Vehicle-to-Grid (V2G) and Grid-to-Vehicle (G2V) energy transfer problem. To this end, some novel design patterns were defined to be used with statecharts in many real world situations (Spanoudakis et al., Reference Spanoudakis, Akasiadis, Kechagias and Chalkiadakis2019).

3. (iii) The Logic-Based Model (Artikis et al., Reference Artikis, Sergot, Pitt, Busquets and Riverat2016): this work takes in consideration the unpredictability of open environment in MAS. It supposes that the behaviour of an agent in such systems cannot be predictable or controllable. In fact, an agent may disobey to the MAS specification in order to realize its individual goal, or it can fail to conform to the MAS specification because of reasons beyond its control. That’s why, architectures with fixed specifications are seen as not suitable for the design of open MAS. As a solution, a logic-based model was proposed. The latter is characterized by its ability to modify, at runtime, the fixed specifications at design time. It consists of a well-defined procedures for a modification of the rules of the game, as well as decision making over and enactment of proposed modifications.

4. (iv) Normative Models and Electronic Institutions: the changing nature of open MAS, as well as the strong collaboration and coordination in such systems, requires an appropriate architecture not only to deal with additions, removal and evolution of agents but also to enhance performance and facilitate interactions between them. In recent years, normative modelling appears as an important method to attain these goals. Norms, which are considered as a set of defined conventions to articulate or to restrain interactions (Viana et al., Reference Viana, Caetano, Cunha, Alencar and Lucena2018) or as rules and standards commonly understood by a group of agents in order to produce a desired behaviour (Mahmoud et al., Reference Mahmoud, Ahmad, Mohd Yusoff and Mustapha2014), are nowadays a powerful formalism in designing open MAS. The importance of such model is highlighted in Luck et al. (Reference Luck, McBurney and Preist2003) by declaring: ‘Human societies have successfully coped with similar issues by creating institutions that establish norms for group dynamics in open systems. The next challenge for agent-based computing is to develop appropriate representations of analogous computational concepts to the norms, legislation, authorities, enforcement, etc., that can underpin the development and deployment of dynamic electronic institutions’. In Derakhshan et al. (Reference Derakhshan, Bench-Capon and McBurney2013), norms are considered as a practical method for the dynamic assignment of rights, responsibilities and sanctions to agents in open MAS. In this work, an architecture using the normative method was implemented. The latter facilitates the management of agents as follows:

   • When an agent enters or exit the system, a new role will be assigned to the agent and as a consequence dynamic assignments of rights and responsibilities will occur.

   • Dynamic assignment of rights and responsibilities may take place when an action or/and when an important time is reached.

   Besides, normative solutions were used in Mahmoud et al. (Reference Mahmoud, Ahmad, Mohd Yusoff and Mustapha2014) in order to propose frameworks and architectures for designing open MAS. We mention mainly: BOID Normative Architecture (Belief, Obligation, Intention and Desire), Programming BOID-Plan Agent, BIO Normative Architecture, Normative KGP Agents and OP-RND Normative Framework.

   Added to that, the issue of synthesising normative systems has been recently studied in Huang et al. (Reference Huang, Ruan, Chen and Su2016) and after that a framework was designed and produced for this purpose in Morales et al. (Reference Morales, Wooldridge, Rodríguez-Aguilar and Lopez-Sanchez2017). The latter carries out an evolutionary game theoretic process which allows to the agents to adopt the norms that are fittest to coordinate them.

   In the same context and as a consequence to the use of normative models in designing open MAS, electronic institutions have been appeared as an important software element in engineering open environments and regulating agents behaviour. They are defined in Jonge et al. (Reference Jonge, Rodriguez-Aguilar and Gui2014) as components providing the rules of the game in agent societies by fixing what agents are permitted and forbidden to do and under what circumstances. The latter work surveys existing infrastructures to engineer open environments using electronic institutions such as EIDE and AMELI. In de Brito et al., (2019), an architecture of an institutional platform was proposed, such platform was conceived in order to achieve the normative regulation of the system. In a similar way, an institutional model for representing open MAS was proposed in Fornaro et al. (Reference Fornara, Vigano, Verdicchio and Colombetti2008).

3.2.2 Analysis of open MAS internal properties

Some researchers’ efforts were dedicated to analyzing internal properties of open MAS. Actually, interests have been essentially focused on measuring the stability of open MAS functioning. Thus, controllability was studied and assessed from a functional point of view, and graph theory was used as a tool for achieving such purpose. We mention Rahmani’s work (Rahamani et al., 2009) in which graph theory was used to study the agreement problem of MAS. MAS controllability was also investigated based on path and cycle graphs in Liu and Ji (Reference Liu and Ji2018). For the same purpose, many research works were proposed such as Tian et al. (Reference Tian, Guan and Wang2018) and Lu et al. (Reference Lu, Zhang and Wang2018). We mention also the work of Robin Milner that highlights the importance of modelling agents networks in order to understand and optimize their behaviour. It proposes a unified structural theory based on bigraphs to represent MAS (Milner Reference Milner2009). Besides, since Hendler’s works Hendler (Reference Hendler2001) and (Reference Hendler2007), the concept of semantic web has aroused the curiosity of the multiagent community and we are today face a new vision for a new generation of autonomous systems on web called Hypermedia MAS (Ciortea et al., Reference Ciortea, Mayer, Gandon, Boissier, Ricci and Zimmermann2019). In this context, a huge number of models was proposed in the literature in order to analyze and interpret agents’ behaviour. For example, knowledge graphs were used to this end. They are defined in Chen and Chen (Reference Chen and Chen2019) as a set of structural data which are interconnected to describe objective things such as concepts, entities and attributes. The latter work enumerates a set of hypemedia MAS where agents exploit knowledge graph to extract useful information. For example, it is used in Intelligent Search Systems to analyze the needs of users and to provide the answers that best meet them. Such graph is also used by agents in Question and Answer Systems in order to retrieve correct answers to the raised questions by users. Finally, in recommendation systems, agents behaviour is modelled as a knowledge graph. The latter was useful to analyze the potential needs of users and to suggest, as a consequence, a relevant and personalized content to them. We mention, also, Ontologies-Based Models which have been recently used in a huge number of research works in the multiagent field. We cite as example Ma et al. (Reference Ma, Schultz, Christensen, Vrbak, Demazeau and Jrgensen2019), Pico-Valencia et al. (Reference Pico-Valencia, Holgado-Terriza and Senso2019) and Guo et al. (Reference Guo, Liu, Xu and Xie2019).

3.2.3 Decision making

Decision making in the context of open MAS is seen as the ability of the composing agents to predict if other agents left the system or new agents are now present. This is indeed in order to decide on possibly choosing a different line of action. To this end, Markov Decision Process was used as a tool to represent open agent systems. In this context, we mention the Interactive Partially Observable Markov Decision Process (I-POMDP). The latter focuses on studying the impact of agents leaving and reentering in a wildfire scenario by providing a set of equations to predict agent openness, that is to estimate when a neighbouring agent leaves or reenters the system (Chandrasekaran et al., Reference Chandrasekaran, Eck, Doshi and Soh2016).

3.2.4 Anomalies detection

As openness becomes an important concern, open MAS are becoming more vulnerable to intrusions, misuses and attacks. Hence, the detection of such threats seems to be necessary. For such purpose, modelling technique was used in some works. For example, some anomalies detection methods were mentioned in Bijani’s review (Bijani Reference Bijani2012). For example, two attack modelling approaches in open MAS were introduced namely: coordination graph and statistical techniques. Coordination graphs, in which nodes are states and arcs represent attacks, allow detecting maximal malicious group of attackers. As for statistical techniques, they help detecting some intrusions at the level of functionalities like probing attacks, ontology attacks and denial of services attacks in open MAS. In the same context, a graph-based approach has been introduced in Kanfert et al. (Reference Kanfert, Scharf and Edenhofer2014). It is proposed in order to detect suspicious behaviour in open MAS at runtime. Such formalism helped applying some metrics such as prestige, actor centrality, reputation Buckets.

3.2.5 Stability verification

With the development and deployment of open MAS in diverse applications, a growing need has emerged to verify and validate agents behaviour. In fact, such task allows estimating not only the stability of the system but also the communicative behaviour correctness. Based on a literature overview, we mention the following existing models:

1. (i) Finite State Automata: in multi-agent self-stabilizing systems, where interacting agents can undergo temporary or permanent failures representing, respectively, the replacement or the departure of an agent, varying compositions were modelled as a graph of finite state machines also called communication graph (Angluin et al., Reference Angluin, Aspnes, Fischer and Jiang2008). Such automata show how agents change dynamically their internal states while interacting. Their objective is to help in designing algorithms that eventually stabilize on the desired answer if the system compositions stop changing, that is, once the system has become closed.

2. (ii) Markov Chain Model: in order to get information about the level of stability in evolving MAS, a Markov Chain Model was used in De Wilde and Briscoe (Reference De Wilde and Briscoe2011). The latter provides a better understanding and quantification of MAS stability. It represents an attempt to control such systems.

3. (iii) Formal methods: we mention here kouvaro’s work (Kouvaros et al., Reference Kouvaros, Lomuscio, Pirovano and Punchihewa2019). The latter defined a semantics for open MAS and their corresponding verification problem which are called the open model checking problem. In this context, two classes of systems that admit verification procedures were defined and they aimed to assess specifications on MAS scenarios.

3.3.1 Trust and reputation modelling

Because of the decentralization and the high distribution of open MAS, agents may be said to be unreliable and self-interested (Hyunh et al., Reference Hyunh, Jennings and Shadbolt2006). Hence, they need mechanisms to control their interactions and to choose partners to cooperate with. At this level, trust and reputation mechanisms have arisen as key elements are not only facilitating the interactions among agents but also in the design of MAS. They are defined as expectation of competence and willingness to perform a given task in order to estimate the trustworthiness of each agents partner and to decide whether the partner is sufficiently reliable to interact with. We provide below an overview on trust and reputation models that currently exist in the literature. Indeed, has enumerated and classified an amount of trust and reputation models as follows:

1. (i) The Centralized Trust and Reputation Models: this family of models works very well in centralized environments. It is suitable for representing systems putting together two types of agents: users and sellers. It aimed to calculate the reputation value for each agent. We mention mainly the online reputation models that are appropriate for designing e-commerce sites such as eBay, Amazon and OnSale. The main examples in this context are Sopras and Histos model, Carter and al model as well as Dirichlet reputaion systems.

2. (ii) The Agent-Oriented Trust and Reputation Models: this family of trust and reputation models is suitable for peer-to-peer systems. It considers reputation or trust as subjective or cognitive properties. We can mention mainly Abdul-Rahman and Hailes model (Abdul-Rahman & Hailes Reference Abdul-Rahman and Hailes2000) and AFRAS (Carbo et al., Reference Carbo, Molina and Davila2003). The first aims to qualify the relationship between any two agents in terms of trustworthiness. To do so, for each agent, a discrete set of four elements is assigned: Very Trustworthy, Trustworthy, Very Untrustworthy, Untrustworthy. Then, for every instance of the previous set, the number of the corresponding past experiences is kept and the maximum of the tuple values is taken into consideration to decide how much an agent is trustworthy for its partner. The second one is based on a fuzzy set to represent reputation values, and it uses a weighted aggregation in order to update an old one. Castelfranchi & Falcone model (Castelfranchi & Falcone Reference Castelfranchi and Falcone1998) is based on the beliefs of an agent i in the ability and performances of an agent j and its dependency on it to obtain a goal g. This notion was refined in ForTrust model (Herzig et al., Reference Herzig, Lorini, Hubner, Ben-Naim, Castelfranchi, Demelombe, Longin and Vercouter2008) which differentiates between occurrent and dispositional trust. The first refers to the trust on other agents to act here and now, and the second denotes the disposition of the trustee to perform an action in order to achieve a goal. Both of them are represented and defined using predicates. Esfiandiari et al., model (Esfandiari et al., Reference Esfiandiari and Chandresekharan2001) aims to evaluate trust in different ways: observation-based-evaluation using bayesian networks and interaction-based-evaluation using protocols to ask agents about some information. To deal with the received witness information, a trust net is built as a directed graph with interval-labelled edges. We mention also the cognitive models having an ontological dimension such as ReGret (Sabater & Sierra Reference Sabater and Sierra2001) and FIRE (Hyunh et al., Reference Hyunh, Jennings and Shadbolt2006). They compute as well as trust value and reliability measure using direct experiences, witness information and social structures. Some other agent-oriented models are proposed in order to represent online market places and to provide reputation information to the buyers mainly Padovan et al. model (Padovan et al., Reference Padovan, Sackmann, Eymann and Pippow2002) and Regan and Cohen model (Regan & Cohen Reference Regan and Cohen2005). We also mention Repage (Sabater-Mir et al., Reference Sabater-Mir, Paolucci and Conte2006) which is a cognitive model based on a tuple of predicates expressing whether a given target agent is good or bad with respect to a certain context. BDI+Repage model (Pinyol & Sabater-Mir Reference Pinyol and Sabater-Mir2013) integrates Repage model with a multi-valued BDI architecture providing a logic-based framework. It is defined as a multi-context system where each context is seen as a logic and a set of formulas written in that logic.

3.3.2 Agent compliance and conformance verification

In open MAS where entities interact in an unpredictable way, we cannot assume that agents will always act so as to conform with conversations policies and to comply to interaction protocols. Thus, conformance and compliance verification seems to be important, and many research works have studied this topic. For example, Baldoni et al. (Reference Baldoni, Baroglio, Martelli and Patti2006) verify the conformance of an agent’s conversation policy to a public conversation protocol, which is based on the theory of formal languages. The conformance test was done using a special finite state automaton. In the same context, a tool which is able to observe and check for agent compliance to interactions protocols was defined in Alberti et al. (Reference Alberti, Gavanelli, Lamma, Chesani, Mello and Torroni2006). The verified protocols are written in a logic-based formalism called Social Integrity Constraints (ICs), and it can be used to provide semantics to communicative actions and protocols in terms of expectations about agents’ behaviour.

In De Pinninck et al. (Reference De Pinninck, Sierra and Schorlemmer2010), graph theory was used in order to represent the normative behaviour of agents in open MAS. The latter work proposes to model the system as a network where agents interact under defined rules and using a set of enforcement techniques. Such techniques are meant for scenarios in which the agents do not know in advance which agent to interact with. They permit verifying that the agent code will fulfill all the systems norms. The verification, in this work, happens at two levels:

• At the level of agents: by verifying the partner agent’s abidance to the normative behaviour.

• At the level of interactions: by verifying the truthfulness and validity of a sent message.

Added to that, runtime norm verification has shown its significance. As mentioned in Alechina et al. (Reference Alechina, Dastani and Logan2018), it deals with techniques that allow checking whether an execution of the system satisfies or violates a given correctness property. Such verification is based on different formalisms: extended regular expressions, trace matches by the AspectJ team and we cite here the work of Ancona et al. (Reference Ancona, Ferrando and Mascardi2017), query-oriented languages like PQL and rule-based approaches.

We mention, also, the work concerning enforcing equilibria in MAS (Perelli Reference Perelli2019). In fact, the equilibrium issue is implicitly related to MAS openness and its verification seems to be important in such systems. It refers to checking whether the Nash equilibria are compatible with a temporal specification that is desired from the designers perspective. In the latter work, verification techniques including model checking are used to this end.

Using the same model, strategic abilities in MAS with private data sharing (Belardinelli, F., Boureanu, I., et al., Reference Belardinelli, Boureanu, Dima and Malvone2019) and those under imperfect information (Belardinelli, F., Lumuscio, A., et al., Reference Belardinelli, Lomuscio and Malvone2019) were verified. We propose to call the models exhibited above AIPs models with reference to the Agent Interaction Protocols.

3.3.3 Knowledge exchange representation

In MAS, the communication between agents is ensured through exchanging messages. Such exchange needs mutual understanding of the message meaning. Agent communication language (ACL) is used to this end. It is considered as the de facto standard of ACL’s implementation in MAS. During the last decades and due to the Internet spread, semantic web technologies were exploited in order to facilitate the data exchange. Gan et al., (2018) propose a combination of the existing FIPA-ACL with Semantic Web (SW). This approach is proposed to enhance the communication between agents and to ensure semantic interoperability. In Jirkovsky and Kadera (Reference Jirkovsky and Kadera2019), a solution for facilitating data exchange between agents is proposed. It is based on the modelling of system interfaces and messages instead of data model.

4.2.1 The first layer: a structural evolving graph

Our evolving graph consists of a set of vertices V representing the agents of the system and a set of arcs E symbolizing the interactions relating the agents over time. Indeed, an interaction may be unidirectional or bidirectional. That is to say, it involves two types of agents: a requester agent, which asks for the interaction, and receiver agents, those undergoing the interaction. Thus, it seems judicious to make the generic graph directed. Besides, we propose to label each component of the graph as follows:

1. (i) Each node v of the evolving graph symbolizes a corresponding agent ai of the system. Actually, each agent is characterized by an identifier id that distinguishes it from the other agents. Added to that, in an open MAS, an agent can appear and disappear a number of times, which make the system structurally open as previously defined. Thus, we propose to assign for each vertex v of the underlying graph, the set of the structural properties of the corresponding agent ai. We represent such set by:

   (1) \begin{equation} S_{v}= < id, A_{v}, R_{v}, P_{v} > \end{equation}
   where

   • id is the identifier of the corresponding agent ai.

   • $A_{v}$ is the number of appearances (additions) of the agent ai in the system.

   • $R_{v}$ is the number of disappearances (removals) of the agent ai from the system.

   • $P_{v}$ is the presence vector of the node v. Such vector consists in keeping a historical record of the agent structural evolution in time. It is defined in Pigné (Reference Pigné2009) as follows:

     Let Gi = $(V_i, E_i)$ be the subgraph of the underlying graph G = (V, E) at the date $t_i$. A vertex v is said present at time $t_i$ if $v \in V_{i}$.

     Thus, the presence vector of a vertex v of the underlying graph G is a vector of integers such that:

     (2) \begin{equation} \left\{ \begin{array}{l@{\quad}l} Pv(v,Gi)= 1 & {\rm if}\, v \in Vi \\[5pt] 0 & {\rm otherwise} \end{array}\right. \end{equation}

2. (ii) Each arc e of the evolving graph corresponds to an interaction between two agents. Actually, each interaction is characterized by a sender identifier SrcId and a set of receivers identifiers DesId. Added to that, in an open MAS an interaction can appear and disappear a number of times, causing changes in the MAS structure. Thus, we propose to assign for each arc e of the underlying graph, the set of the structural properties of the corresponding interaction. We represent such set by:

   (3) \begin{equation}Se=<SrcId,DesId,A_{e},R_{e},P_{e}>\end{equation}
   where

   • SrcId is the sender identifier.

   • DesId is the set of the receivers identifiers.

   • $A_e$ is the number of appearances (additions) of the corresponding interaction.

   • $R_e$ is the number of disappearances (removals) of the corresponding interaction.

   • $P_e$ is the presence vector of the arc. Such vector consists in keeping a historical record of the interaction structural evolution in time. It is defined in Pign (Reference Pigné2009) as follows:

     Let $G_{i} = (V_{i}, E_{i})$ be the subgraph of the underlying graph G = (V, E) at the date ti. An arc e is said present at time ti if $e\in Ei$.

     Thus, the presence vector of an arc e of the underlying graph G is a vector of integers such that:

     (4) \begin{equation} \left\{ \begin{array}{l@{\quad}l} Pe (e,Gi)= 1 & {\rm if}\, e\in Ei \\[5pt] 0 & {\rm otherwise} \end{array}\right. \end{equation}
     Based on the description above, we give in Figure 2, a random example of a structural evolving graph which represents a MAS regardless of its domain of application.
     Figure 2

     Illustrating example of a random structural evolving graph

     

4.2.2 The second layer: a KAGR graph

In the second layer, each agent $a_i$ has a set of internal properties. They refer to the internal attributes that may be added, removed or/and changing value over time. Actually, the literature gives a conventional definition of an agent. It is defined as a computer system which is situated in a dynamic environment and which is able to communicate with other agents and to use its knowledge and experiences in order to achieve a certain goal. This definition exposes the different internal attributes of an agent namely: Knowledge, Action, Goal and Relation. Indeed, these attributes were defined in Sebai and Chaari (Reference Sebai, Chaari, Jezic, Kusek, Lovrek, Howlett and Jain2014) in order to explain and interpret multi-agent reasoning. In the same work, it was shown that the four selected attributes are in a causal relationship. Thus, a causal graph seems to be more appropriate for their modelling. They are represented as a set: $<k_i(t_j), A_i(t_j),G_i(t_j),R_i(t_j)>$ where

• $k_i(t_j)$: the set of knowledge encapsulated in the agent $a_i$ at time $t_j$.

• $A_i(t_j)$: the value of the executed action by the agent $a_i$ at time $t_j$.

• $G_i(t_j)$: the value of the goal that has to be satisfied by the agent $a_i$ at time $t_j$.

• $R_i(t_j)$: it includes a communication details namely the sender identifier, the receivers identifiers and the content of the message.

This graph was called KAGR graph in Sebai and Chaari (Reference Sebai, Chaari, Jezic, Kusek, Lovrek, Howlett and Jain2014). It allows the representation of any modification at the level of agents internal properties, in between interactional ones. In the context of open MAS, the represented modifications by the KAGR graph are:

1. (i) Knowledge addition: knowledge addition may be caused by a communication between two agents. That’s to say, when an agent $a_i$ interacts with an agent $a_j$ at time t, new knowledge can be added to $a_j$ at time t$^{\prime}$ in order to achieve a certain goal $G_i(t)$. This is graphically represented in the KAGR graph as in Figure 3. We denote by + a positive influence and by – a negative one between the two attributes.

2. (ii) Action addition: an action may be added into an agent for three reasons:

   1. (a) An already carried out action at time t can promote the possibility of realizing another one by the same agent. This causes the addition of a new action to its set of actions $A_i$ at time t$^{\prime}$.

   2. (b) The addition of new knowledge $k_i$ at time t to an agent $a_i$ may favour the execution of a new action by the same agent at time $t^{\prime}$.

   3. (c) When an agent $a_j$ interacts with another agent $a_i$ at time t, a new action may be executed by $a_i$ at time $t^{\prime}$, which causes its addition to the set of actions $A_j$.

   Action addition is graphically represented as in Figure 4.

3. (iii) Goal update: a reached goal at time t by an agent ai can favour the achievement of another goal at time $t^{\prime}$. We call this, a goal modification. It is represented as shown in Figure 5.

4. (iv) Interaction addition: an established interaction by an agent $a_i$ may be the consequence of another interaction established by an agent $a_j$. We call this modification, interaction addition. It is represented as shown in Figure 6.

5. (v) The removal of knowledge/actions/goals/interactions: such removal can be caused only by the physical suppression of agents.

Figure 3

The addition of knowledge to an agent $a_j$

Figure 4

The addition of new actions to an agent $a_i$

Figure 5

Goal update in an agent $a_i$

Figure 6

Interaction addition to an agent $a_i$

Following the description above, we propose to call our model an evolving KAGR graph. In order to more clarify it, we give an illustrating example in the following Figure 7.

Figure 7

An example of a KAGR evolving graph

The graph below shows how agents and their internal attributes evolve in an open environment. The described system is decomposed of four agents whose identifiers are $id_1, id_2, id_3$ and $id_4$. Structural openness is shown at the first layer. We find that agents $id_1, id_3$ and $id_4$ appear only once in the system at, respectively, time $t_1$ and $t_2$ and remain permanent for the rest of the system time evolution. As for the agent $id_2$, it is added once at time $t_1$ and removed once at time $t_2$. Besides, four interactions were established:

• An interaction between $id_1$ and $id_2$ is established at time $t_1$ and disappeared at time $t_2$.

• An interaction between $id_2$ and $id_3$ is established at time $t_1$ and remains until $t_2$.

• An interaction between $id_3$ and $id_4$ is established at time $t_2$.

• An interaction between $id_4$ and $id_1$ is established at time $t_2$.

In the second layer, we are interested in the internal attributes evolution for each agent. For example, at time $t_1$, agent $id_1$ establishes an interaction $R_1(t_1)$ with agent $id_2$. This causes the addition of new knowledge to the set $k_2$ at time $t_2$. As a consequence, a new action is executed by the latter agent and added to the set $A_2$ at time $t_2$ in order to reach a goal $G_2(t_2)$. Besides, agent $id_2$ establishes an interaction $R_2(t_2)$ with agent $id_3$. This interaction has a double effect: the addition of new knowledge to $k_2$ at time $t_2$ and new ones to $k_3$ at time $t_3$. The latter knowledge addition causes the execution of a new action by $id_3$ in order to realize a certain goal $G_3(t_3)$. This action promotes the execution of a new one by the same agent at time $t_4$ to reach the same goal $G_3(t_3)$. At the same time, two internal modifications are undergone in the system. The first is a goal update into agent $id_1$ from $G_1(t_1)$ to $G_1(t_4)$. The second is a new interaction between agents $id_4$ and $id_2$ through the relation $R_3(t_4)$. The latter has as a consequence the addition of new knowledge to the set $k_4$ at time $t_5$ which makes the corresponding agent able to execute new actions and to add them to the set $A_4$ in order to reach the goal $G_4(t_5)$. Also, a new relation $R_4(t_5)$ is established between agents $id_4$ and $id_1$. It adds new knowledge at both the set $k_4$ at time $t_5$ and set $k_1$ at time $t_6$. This causes the addition of new action into $A_1$ at time $t_6$ in order to reach the goal $G_1(t_4)$.