Keywords

1 Introduction

MultiAgent Systems (MAS) are being increasingly used in industry where most environments are dynamic, complex and uncertain. Potential applications cover multiple areas such as control, diagnosis, transport, manufacturing and logistics. MAS provide a natural way to design and implement efficient distributed industrial systems as well as to design monitoring and decision support systems.

The literature review pointed out the early interest of researchers to develop MAS for industrial systems diagnosis and monitoring [1–3]. However, for such demanding and critical applications, achieving best solutions cannot be done without efficient evaluation tools. Analysis and comparison of the different alternatives for a system’s architecture, for example, should be guided by adapted evaluation methods and through relevant criteria. In multiagent technology such tools and methods are still lacking, especially at the application level, even efforts are being provided to deal with this issue [4–6].

In fact, evaluating design methodologies and development platforms and tools is undeniably of great interest but remains insufficient to make a full coverage of multiagent systems evaluation. It becomes more and more necessary to provide means for evaluating and comparing multiagent applications. That is what we address through our research works which focus on agent-oriented applications evaluation based on specific characteristics especially structural ones [7, 8]. In this paper we are interested in organization. Several metrics to characterize it are inspired from graph theory and used to evaluate and compare two versions of a multiagent application for fault detection and isolation.

The paper is organized as follows: Sect. 2 presents the particularities of organization in MAS. In Sect. 3, the adopted approach of organization evaluation in MAS is described. Section 4 presents the several versions of the diagnosis multiagent application which are evaluated and compared. The results and interpretations are also exposed in the same section. A conclusion and a look at future work are presented in Sect. 5.

2 Organization Evaluation Method

A multiagent system is a society of agents in mutual interaction sharing tasks, resources and knowledge. The several interaction patterns in a multiagent system engender complex organizational structures and interrelated acquaintances networks [9]. Organization is a very important characteristic and a basic concept of multiagent systems as it transposes their social dimension [9–11]. The evaluation of organization is a very interesting issue; it allows developing an understanding of the multiagent system and its structure. In [9] the author defines the possible ways of analysing MAS organizations. There is functional analysis which aims to identify and describe the functions that the several entities of an organization are supposed to realize. From this prospect, organization is viewed as a set of roles and relations between those roles. There is also structural analysis which focuses on the interactions between agents trying to make sense to their complex interrelations and explain the resulting organizational structures.

In this work, great importance is accorded to the structural aspect of organizations, that’s why the chosen representative model rely on graphs which expressively shapes the multiagent structure by drawing its entities and their relationships. Based on this model, the evaluation of organization is done thanks to specific metrics of graph theory which are presented in the following paragraph.

The following organization evaluation method is part of a global evaluation approach which consists in observing, modeling and measuring functional characteristics of MAS [7, 12].

The proposed solution consists in modeling the interaction network of the MAS through an oriented graph where the nodes represent the agents and the arcs represent the communication links between these agents. The arc direction is that of sending messages and each arc is weighted by the number of exchanged messages. The properties of this graph are then evaluated according to graph theory.

2.1 Degree Distribution

The degree of a node is the number of connections it has to other nodes. Here Ki designates the degree of a node i. In a graph, nodes may have different degrees. The degree distribution P(K) is defined as the fraction of nodes in the graph with degree K:

$$ P(K) \, = \, \frac{{N_{K} }}{N} $$
(1)

with NK the number of nodes having a degree K and N the total number of nodes.

Different types of networks have different characteristic degree distributions P(K). The shape of the degree distribution function allows distinguishing two main classes of networks. Homogeneous networks are characterized by a degree distribution that is concentrated around the degree mean value < K > given by:

$$ < K > { = }\sum {K \times P(K)} $$
(2)

Heterogeneous networks are characterized by a degree distribution that generally follows a power law which is the case of most networks in the real world. This means that, in such networks, there is a large majority of nodes having low degree but a small number having high degree that greatly exceeds the average. Those nodes are thought to be special and having a specific function in their networks.

2.2 Assortativity

Assortativity reflects the tendency of some nodes to be connected to other nodes having similar degrees. Assortativity is often examined in terms of correlation between nodes degrees. A simple characterization of the correlations between degrees of neighbor nodes is determined by the neighborhood degree Knn,i which expresses the average neighbors degree of a given node i.

$$ K_{nn,i} = \frac{1}{{K_{i} }}\sum\limits_{j}^{{}} {K_{j} } $$
(3)

Based on this measure, degree correlation is given by the mean neighbourhood degree of nodes with K degree.

$$ K_{nn} (K) = \frac{1}{{N_{K} }}\sum\limits_{{i/K_{i} = K}}^{{}} {K_{nn,i} } $$
(4)

The behaviour of Knn(K) defines two main classes of networks. We talk about assortative network when Knn(K) increases with K. This is the case of social networks when high degree nodes are preferentially associated with other high degree nodes. And we talk about disassortative network when Knn(K) decreases with K, such as in hierarchic networks where high degree nodes are connected to many nodes with low degree.

2.3 Centrality

Centrality determines the importance of a node within the network and how much it is influent. This metric is inspired from social networks analysis. Many terms are used to measure centrality such as degree centrality. Cd(i) is the degree centrality of node i.

$$ Cd(i) = \frac{Ki}{(N - 1)} $$
(5)

Where Ki is the degree of the node i and N is the number of nodes in the network.

2.4 Hierarchy

We talk about hierarchy in organizations if relations between the organization entities are determined by authority. In oriented graphs, hierarchy is defined as follows:

$$ Hierarchy = 1 - \left[ \frac{V}{MaxV} \right] $$
(6)

With V the number of pairs of nodes symmetrically connected and MaxV is the total number of pairs of nodes [13]. This measure is interesting to express structural hierarchy of the network but does not reflect hierarchy degree in multiagent systems as it does not consider semantic meaning of a link. For this reason, we propose to examine the nature of the links to determine whether there is any power relationship. The best way to do that is to pick up the nature of the message, and to deduce the existence of power relationship if the message is an order. The proposed measure for hierarchy is:

$$ Hierarchy = \frac{OrdV}{MaxV} $$
(7)

Where OrdV is the number of nodes pairs related by order messages translating a hierarchic relationship.

2.5 Leadership

In a multiagent system several agents can come together into organization structures called groups which may be teams or coalitions. In both cases, there can be an agent having the special capability of coordinating the actions of the other agents. This agent is called “leader” [10]. While in a team the leader represents a decision authority, in a coalition the leader does not have a real decisional power but is rather a point of information centralization. To pick up such agents using graph formalism, a group is assimilated to a star sub-graph, with the leader as a central node surrounded by the other group agents [10]. A star graph Sn of order n is a graph on n nodes with one node having the degree n-1 and the other nodes having the degree 1 [14]. To recognize the leaders in a multiagent system, we have to identify the star sub-graphs in the whole representative graph.

2.6 Measures Summary and Signification

The following Table 1 summarizes the used measures, the way they are computed and the possible interpretations which can be concluded from such measures.

Table 1 Summary of measures and possible interpretations
Full size table

3 Application to Fault Detection and Isolation

3.1 Evaluated Agent-Based Application

The evaluation method presented above was applied on two versions of a multiagent diagnosis application. It is a multiagent application designed in order to detect and localize failures affecting an industrial system [15]. Its functioning principle can be summed up as follows: an analytical model describes the normal functioning way of the system. To diagnose the system, a test of the coherence between the observations done on the real system and the analytical model is performed through a set of residuals or fail indicators. The studied multiagent application of diagnosis is composed of different autonomous agents; each of them is responsible of a specific task and belongs to one of the following categories:

  • Detection agents: they take the measures of the system variables to be supervised and compute the corresponding residuals. Then they send results to localization agents. Two detection methods are used: binary logic and fuzzy logic.

  • Localization agents: they retrieve the different residuals from the detection agents, to localize the failure using different methods. The used localisation methods are binary logic, fuzzy logic, Probabilistic Neural Network (PNN) and Multi-layer Perceptron (MLP). For the two latter cases localization agents don’t rely on detection agents since these methods allow both detection and localization of failures.

  • Interface agent: it coordinates the other agents’ processing by controlling the order of messages exchange and ensures communication with the application user. Interface agent sends requests to detection and localization agents to start diagnosis and display results to the user.

In addition to the detection, localization and interface agents, in the second version of the diagnosis application, a new agent DIAG is added which is an arbitrator agent that takes the diagnosis results from the several localization agents and determine the correct diagnosis if there is a conflict. It tells the several localization agents to send their credibility degree which is the number of times they emitted a good diagnosis in the past. Then it compares the different values received and takes the final diagnosis decision which corresponds to the agent having the highest credibility degree.

All these agents cooperate and communicate through message exchange to ensure the diagnosis process.

3.2 Results and Interpretations

In the following paragraphs, the results of the organization evaluation carried out on the two versions of the multiagent application for fault detection and isolation are presented and discussed. Visualization of the resulting graphs helps characterizing and comparing the several diagnosis architectures. Figure 1 illustrates the graph corresponding to the first version of the diagnosis MAS.

Fig. 1
figure 1

Generated graph of the first agent-based diagnosis application

Full size image

The graph presented in Fig. 2 highlights the presence of the agent DIAG which is an arbitrator agent. There is lot of communication added by the inclusion of this agent.

Fig. 2
figure 2

Generated graph of the second agent-based diagnosis application

Full size image

We notice that the detection agents DET1-5 and DETFL do not communicate with each other. They rely on the localisation agents LOCBN and LOCFL which are solicited more than the other agents. This is due to the fact that while detecting a fault, the detection agents send the residual values to the localisation agents whereas the agent INTER sends messages and does not receive any. This is because it is an organiser agent; it transmits to the detection agents a diagnosis request and informs the localisation agents to receive the residual values from the detection agents. In the following we try to give some interpretations according to the obtained evaluation results. We start by examining the obtained values of the several used measures.

Figure 3 shows the several agents’ degrees in the two versions of the diagnosis application.

Fig. 3
figure 3

Agents’ degrees in the two application’s versions

Full size image

Two categories of agents can be distinguished:

  • Agents whose degrees didn’t change from a version to another such as detection and interface agents.

  • Agents whose degrees have increased due to the addition of an arbitrator agent such as localization agents.

This is due to the fact that localization agents are those that emit diagnosis conclusions and are the more likely to be in conflict situations which explains resorting to an arbitrator agent.

Figure 4 illustrates the aspect of degrees distributions corresponding to the two versions of the diagnosis application.

Fig. 4
figure 4

Degrees distribution in the two application’s versions

Full size image

The obtained curves correspond to heterogeneous graphs; which means that there is no significant mean value around which the degrees are concentrated. In both cases, there is a majority of nodes with low degrees and a small number of nodes with high degrees exceeding the average. We also notice that the difference between the number of agents with a low degree and that of agents with a significant degree is much more pronounced in the first version of the application (without arbitration).

This is also what we see through Fig. 5 which shows the degrees correlation for both versions of the diagnosis application.

Fig. 5
figure 5

Degrees correlation in the two application’s versions

Full size image

The correlation expresses the graph’s assortativity degree. Both architectures are disassortatives. The disassortativity is a characteristic of hierarchical systems in which agents of significant degree tend to be associated to agents of lesser degree. We notice that in the case of diagnosis without arbitration, assortativity is slightly different compared to the case of diagnosis with arbitration. In the latter, the disassortativity is accentuated by the addition of the arbitrator agent whose degree is important compared to other agents. Figure 6 shows the centrality degrees of the different agents for both versions of diagnosis application.

Fig. 6
figure 6

Centrality degrees distribution in the two application’s versions

Full size image

We notice through these results that the centrality degrees of detection agents decreased by introducing the arbitrator agent and centrality degrees of localization agents have instead increased. This is explained by the fact that localization agents are connected to the arbitrator agent; which had increased the centralization within this acquaintance of the MAS.

The introduction of the arbitrator agent didn’t change significantly the organizational structure of the MAS. The communication induced by adding the agent DIAG is a useful one since this will help the user in the decision making process. In fact, in the case of conflicts, the user has not to choose which diagnosis is the correct one; he will rely on the arbitrator agent which will take the decision instead of him according to the information retrieved from each localisation agent.

4 Conclusion and Future Work

In this paper we presented a multi-agent model as well as an appropriate evaluation method to analyse and compare different multiagent diagnosis architectures for fault detection and isolation. The evaluation approach focuses on the organization as it is an important characteristic in MAS. It is based on measures and indices stemming from graph theory. It should be noted that the purpose of the evaluation is not only to analyse and compare different MAS from a technological point of view. It aims also to help industrialists making choices between various architectural alternatives of the fault detection and isolation system. The evaluation allows industrialists to have a clear idea on the different diagnosis architectures specificities. In extension to this study, our future work includes two points. The first consists in extending the test-case diagnosis multiagent application in order to move to a larger scale and thus reconsider the evaluation results. The second point is to focus on the evaluated system’s dynamics and the evolution of the proposed measures over time. For this purpose, the proposal of an evolving graph model instead of a static one is actually addressed.