Observing collective knowledge state during integration

Abstract

Integration of collective knowledge becomes a more and more common task, but research rarely focuses on how it is influenced by the time dimension. In this paper we describe expanding conflict profile – a method to model the changes in collective knowledge consensus when the group is slowly adding new members with new opinions. We also describe the asynchronous aspect of group communication in a decentralized multi-agent system. We provide simulation experiments for both parts, as well as a prototype application using the results of our research. We show that our approach may be successfully used in applications, where previously only a centralized multi-agent systems were used.

Keywords

Knowledge integration multiagent system collective knowledge consensus theory

1 Introduction

In modern information society knowledge management and various related tasks become more and more important. Various applications use different methods of decision making, information retrieval or knowledge integration, often without any input from the user. Multiple methods have been developed to solve problems that may occur during these tasks. This includes the consensus theory used to handle inconsistencies in knowledge that may cause problems during integration. Inconsistency is a feature of knowledge which may be characterized by the lack of possibility for inference processes, therefore solving it is an essential task in many cases of knowledge management [16]. Many researches have proposed methods for resolving inconsistency on syntactic or semantic level. The aspect that was not previously considered from the angle of consensus theory and collective knowledge integration, is the time aspect. This paper summarizes our research into addresing this gap.

We consider two aspects: how consensus changes as the size of collective changes, and how consensus is achieved if we consider it as a process and not as an instant change of knowledge states. The first aspect was considered by enhancing the consensus methodology by expanding conflict profile. A conflict profile [16] is the set of distinct opinions from all agents. Expanding conflict profile changes over time - new agents may be added to the collective and express their own opinions. Due to this the consensus of the whole collective may change. We observe this change over time, trying to determine how it relates to the final consensus, that is calculable once the collective stops growing. The second aspect of our research is the study of centralized and decentralized multi-agent systems, as well as observations of how local and global consensus are achieved. We adopted asynchronous communication and preferred communication channels to better represent some real-world situations. We also apply this approach to agent communication in a prototype application of a weather forecast system that we use on real data, showing that it is not worse that a classic centralized system.

This is research that we have outlined in general terms in our previous papers [12 –14]. Here we summarize all those elements, providing more precise definitions, more detailed mathematical analysis, additional experiments and more results gleaned from them. We also expand the description of a practical application we used to show the usability of parts of this research. This consists of Section 3 of this paper, which is an updated version of one present in [12]; Section 4 where the experiments were repeated and the results analyzed again in greater detail compared to [12]; Section 5, where more details were provided, as well as new aspect of research presented compared to [13, 14]; Section 6, where all experiments from [13, 14] were repeated and a lot of new ones conducted, leading to more detailed observations; and finally Section 7, where we expand the experiments done in our prototype application from [13]. Additionally, we provide a list of related research topics in Section 2 and some general conclusions and possible areas of future work inSection 8.

2 Related works

In this section we will present the most relevant or similar research done into multi-agent systems and collective knowledge integration extended over time. As far as we know, the case of expanding conflict profile and the influence of asynchronous communication and the structure of the agent collective on the process of knowledge integration, have not been researched yet.

The aspect of consensus changing with time is most often considered in terms of continuous-time consensus in multi-agent systems, especially for autonomous robots and network systems [24]. It has broad application in formation control, attitude alignment, flocking, negotiations and more. Multiple researchers focus also on determining if agents reach consensus in finite time (finite-time consensus). The most often researched aspect is the stability of such multi-agent system [19], that is if the consensus is even possible and if the knowledge states of all agents are convergent to it. As an example, the authors of [21] consider the finite-time consensus problem for leaderless and leader-follower multi-agent systems with and without external disturbances. They show that without them, all agents in a leaderless system will reach the consensus in finite time. With disturbances, they show that a pair of agents will reach consensus in finite time, but this cannot be guaranteed for larger groups of agents. In [25] the authors construct local non-smooth time-invariant consensus protocols using Lyapunov function, graph theory and homogeneity with dilation to obtain finite-time consensus. In [20] the authors consider a binary consensus protocol and a pinning control scheme to help minimize the error relative to each neighbouring agent. Here, the Filippov function, set-valued Lie derivative and Lyapunov functions are used to determine the conditions necessary for finite-time consensus. In both cases, due to extensive theoretical background, the mathematical analysis of the solution may be presented. Another related problem often occurs in group decision making – what number of experts is optimal and should more experts always be added to improve the decision [23]. The most common approach is weighting the expert opinions, such that experts added to the group later will have lower influence on the final decision. Thus a cutoff may be determined for the maximum number of experts. Expert opinions may be later integrated using different possible approaches [27].

In our research, we use the mathematical model first developed in [18, 22] to determine median data or knowledge – upon which a more formal consensus theory was built. Consensus methodology has been proven to be useful in solving conflicts and is effective for knowledge inconsistency resolution and knowledge integration. The general notion of consensus and postulates for consensus choice functions (also called knowledge functions) were defined like: reliability, unanimity, simplification, quasi-unanimity, consistency, Condorcet consistency, general consistency, proportion, 1-optimality and 2-optimality [16]. Other works helped define classes of consensus functions and analyze them in relation to those postulates. This allowed developing consensus-based integration algorithms for various types of data.

A lot of multi-agent systems researched and implemented over the years are decision support systems with a centralized approach to communication. A common example are traffic control systems [4, 11]. In those basic agents are meant to control single subsystems or single functionalities, and in a few cases – small geographical regions (e.q. one crossroads for a system covering the whole city). The supervisor is a single agent that manages and optimizes the overall traffic flow in the region. The role of the supervisor is most often to prepare a solution and present it to the traffic officer for the city, who may or may not use the proposal. Similar approach occurs in multi-agent systems supporting decision making in power systems [10]. In these examples the agents gather some local information for themselves and from their neighbouring agents (small scale communication occurs on this level), then forward them to the central facilitator agent, which is the only one that may influence the decision making process. This is sometimes extended towards more tiers in the hierarchy, for example in [1] the authors use three tiers for learning, which each higher tier grouping some elements from lower ones and integrating them towards the final answer. A step towards decentralized systems is the use of verification agents [2]. A fully decentralized network of agents may work towards some goal, e.q. clustering, but the verification agents observe their behaviour and if necessary correct it. There are also fully decentralized multi-agent systems with no observing agents, e.q. in [6] the authors show that a group of diverse random agents deciding by majority vote gives better results in the game of Go that a set of uniform agents. Similar approach is used in [17], where the authors use a decentralized system for surveillance – each agent reasons individually, while being influenced by both his own knowledge and knowledge received from other agents in the system. In [26] the decentralized approach is used to cluster agents for task allocation. There are also hybrid centralized-decentralized systems [3], which may also use asynchronous agent communication. In this case the authors focus on delays in the communication process and do not take into account the problems that may occur during integrationitself.

Our approach to decentralized multi-agent systems is slightly different. We use asynchronous communication and some overlying structure of preferred communication channels, similar to those found in the area of social group communication and social networks. In those, both the centralized structure (e.q. hierarchical employee structure analyzed to improve productivity in a company) and decentralized structures (social networks with the inherent friend relationship) were analyzed using real world examples as basis. In contrast we start from theoretical side of the collective intelligence research while aiming to build similar practical applications. Similar approach was used in [9], where authors considered a group of students working on some research problems, showing that the underlying social network is not important to the final result of integration. Only if strong ties may be determined between participants, the improvement of the group results is possible. Building a model for knowledge dissemination in a social group communication was also proposed in [7], in order to improve the teaching process.

3 Dynamic conflict profile

One aspect we have previously considered [12] is the notion of consensus for inconsistent knowledge, as first given in [16]. There is some domain U, where a conflict profile X ⊆ U is a set of inconsistent data or knowledge. There exists some element C (X) ⊆ U, called the consensus, which is the best representative of the whole set X. This representative may differ depending on the criteria (postulates) used to determine it. A classic example is a set of inconsistent opinions X = {Yes, Yes, No} in the domain U = {Yes, Maybe, No}. The consensus for some criteria may be C₁ (X) = {Yes} and for others C₂ (X) = {Maybe}. When using standard criteria it is also possible for the consensus to be C₃ (X) = {Yes, No}, while the case of C₄ (X) = {No} shouldnot occur.

In [12] we have expanded the notion of conflict profile by the measure of time. This allows observing if new opinions are added or removed from it, and how it influences the resulting consensus. We use discrete time measure, denoting X (n) , n ∈ {1, …, N} as the dynamic conflict profile. With this conflict profile, we may determine the temporary consensus as C (X (n)) , n ∈ {1, …, N}. To follow the previous example, for X (1) = {Yes, No} the consensus may be C (X (1)) = {Maybe}, but once more opinion is added, conflict profiles X (2) = {Yes, Yes, No} and X (3) = {Yes, Yes, Yes, No} will lead to the same consensus C (X (2)) = C (X (3)) = {Yes}.

We have observed student behaviour during group work to find possible real-world approaches to achieving consensus with changing size of the collective. While this was not a formal study, some interesting observations were found. For example, a group of a few students after working for some time will come to some consensus (solve the task to the best of their knowledge). Introducing a single new student to this group will rarely change their result (but may do so, if the student opinion has enough weight). If opinions (solutions) of the new student differ largely from the group, the whole process of determining the consensus may start anew. On the other hand, if a student leaves a group, his opinion is mostly remembered and still considered. A fallacy may occur here – even the whole group of students may not know the correct solution to the problem. Therefore this approach is best used when the answer depends on the participants (like jury decisions) and not if it is independent of them (like weather forecasts). Based on those non-formal observations, we focused our research on expanding conflict profiles. This means that X (n + k) = X (n) ∪ {x : x ∈ U} and X (n) ⊆ X (n + k) for k ∈ {1, 2, …}. Following the methodology given in [16], the main differences from the non-dynamic situation are as follows.

First, let us consider the postulate for maximum consistency. Consistency c (X) is a measure used to determine if a conflict profile is homogenous (opinions are identical) or heterogeneous (opinions are different). If the profile is homogenous, then c (X) =1. For expanding conflict profile this means that: $\forall_{n \in {1, \dots, N}} : c (X (n)) = 1 = c (X)$ (1)

Consequently, either X (n) = X or ∀_n>1 : X (n) and X are multiples of some X (1). In both cases the profile is not dynamic and cannot be treated as an expanding conflict profile (ie. there is no conflict).

Another postulate that is important to consider is one of the versions of postulate for minimal consistency (P2c). It says that if X = U then c (X) =0. For expanding conflict profile this leads to an observation that if we add elements to X then c (X (n)) is non-monotonously decreasing until for X (N) = X = U we have c (X (N)) =0.

Some differences occur also for various postulates for consensus. The most basic, but very important postulate is reliability. It states that some consensus must be found, if the conflict profile is non-empty. If at some moment n₁, this postulate is satisfied, then because X (n₁) ⊆ X (n) it is also satisfied for any moment n > N₁. As this moment n₁ is also the first time moment that the conflict profile is non-empty, considering collective knowledge prior to it is impossible. Thus we may state that the reliability postulate remains unchanged in the case of expanding conflict profile.

The unanimity postulate for consensus works with a homogenous profile (X = {k · x}). As discussed previously, this means that it does not influence the process of integration for the expanding conflict profile.

Similarly, the simplification postulate may be satisfied only in very few situations. It occurs for homogenous profiles (which we consider undesirable due to the previous deliberations) and for very specific non-homogenous profiles (if X (n₂) is a multiple of X (n₁) then C (X (n₁)) = C (X (n₂))).

The postulate of quasi-anonymity states that repeatedly adding the same element {x} to the conflict profile should result in the consensus after some time moment N also being {x}. Thus it describes the specific case of expanding conflict profile, where the consistency of knowledge increases. A single step of such expansion is similar to what is described in the consistency postulate for consensus. For expanding conflict profile, with n₂ > n₁, it has the following form:

$\begin{matrix} x \in C (X (n_{1})) \land X (n_{2}) = X (n_{1}) \cup {x} \\ \Rightarrow x \in C (X (n_{2})) \end{matrix}$ (2) It may be also described as follows: if {x} is a part of the consensus in some moment, then if conflict profile is only expanded by {x}, it will still be part of the consensus.

The Condorcet consistency postulate for consensus with expanding conflict profile would be denoted as follows:

$\begin{matrix} C (X (n_{1})) \cap C (X (n_{2})) \neq \emptyset \\ \Rightarrow C (X (n_{1})) \cup C (X (n_{2})) = C (X (n_{1}) \dot{\cup} X (n_{2})) \end{matrix}$ (3) While this equation would be mathematically true, it does not work with interpretation we use. The product of past and future (n₁ and n₂) consensus could describe the changes that occur in collective knowledge, but the sum of past and future conflict profile is not possible.

The proportion postulate may be denoted asfollows:

$\begin{matrix} X (n_{1}) \subseteq X (n_{2}) \land x \in C (X (n_{1})) \land x \in C (X (n_{2})) \\ \Rightarrow d (x, X (n_{1})) \leq d (x, X (n_{2})) \end{matrix}$ (4) Where d (x, X) is the sum of distances d (x, y) for y ∈ X between the element x and each element in set X. This allows to state, that for a given x ∈ X (n₁), the distance d (x, X (n_i)) is non-decreasing for n_i > n₁ (non-decreasing over time).

The postulates: general consistency, 1-Optimality and 2-Optimality can be used for expanding conflict profile in a way analogous to the case of a static profile. The latter two are especially important to determining actual algorithms and solutions (single element consensuses).

Another aspect to consider for the case of expanding conflict profile is the quality of consensus, which is an important measure of it [16]. It is denoted as: $\hat{d} (x, X (n)) = 1 - \frac{d (x, X (n))}{card (X (n))}$ (5) We know from 4 than d (x, X (n)) is non-decreasing with n. We also have non-decreasing (no change or increase with each new element) card (X (n)). As ∀_y∈X : d (x, y) is in range [0, 1] with each increase of cardinality by 1, the overall distance d (x, X (n)) may only increase by [0, 1] in each time moment. Therefore the quality of consensus $\hat{d}$ is also non-decreasing. This short analysis leads to an important theorem:

Theorem 1. When using expanding conflict profile for knowledge integration, the quality of consensus will not decrease over time.

Another important element is whether the consensus when using expanding conflict profile is monotonically convergent with the consensus calculated for a single data set, that is:

$\begin{matrix} \forall_{(n_{1}, n_{2}) : n_{1} < n_{2}} : \\ d (C (X (n_{2})), C (X)) < d (C (X (n_{1})), C (X)) \end{matrix}$ (6)

The following counter-example shows that this does not occur:

First, assume elements of the conflict A₁ = 0, A₂ = 1, A₃ = 2 and A₄ = 3 with O₂ method used to solve the conflict (in this case, the average). The final consensus C (X (N)) =1.5.

We will first use A₂ and A₃ in n₁. Then C (X (n₁)) =1.5. The distance to final consensus is 0.

Now in time n₂ we will add A₁ to the temporary conflict profile. Then C (X (n₂)) =1. The distance to final consensus is now 0.5 > 0.

This short counter-example shows that this approach is not monotonically convergent (the quality of consensus increases (does not decrease), but the value of the temporary consensus does not). Still, as X (N) = X then C (X (N)) = C (X), the dynamic consensus is eventually convergent. We may state that:

$\begin{matrix} \forall_{n_{1} \in {1, \dots, N}} \exists_{n_{2} \in {1, \dots, N} : n_{1} < n_{2}} : \\ d (C (X (n_{2})), C (X)) \leq d (C (X (n_{1})), C (X)) \end{matrix}$ (7)

Which in borderline worst case means that n₂ = N (the last element of the data set is so important, it changes the result entirely). It is also possible that new elements added with the expanded conflict profile do not change the consensus: $d (C (X (n_{2})), C (X)) = d (C (X (n_{1})), C (X)) .$ (8)

Due to this the following equation cannot be used to determine additional interesting results: $\forall_{ε} \exists_{n \in {1, \dots, N}} : d (C (X (n)), C (X)) < ε$ (9)

If this equation was true, then we should be able to determine when the temporary consensus is close enough to the final one. In real world example, this would allow inference based on a knowledge stream, where after some time we would gather sufficient knowledge to achieve results close to results from observing the whole stream. This is an important fact that severely limits the possible uses of expanding conflict profile.

4 Simulation of consensus with expanding conflict profile

The non-monotonicity of converge when using the expanding conflict profile does not allow developing specific integration algorithms for this approach or mathematically predicting the best point to end the profile expansion. Due to this we have performed some simulation experiments to observe the behaviour of consensus in some specific cases [12]. For purposes of this paper we have expanded upon these experiments, observing additional variables and analyzing the results on a deeper level.

The experiments were conducted using JADE agent framework [5] on a standard personal computer. We used the following procedure for the simulation runs:

Create a set of N agents with randomly generated data.

Determine final conflict profile X (N) consisting of all agents data.

Determine final consensus C (N).

Set current number of agents n = 2.

Create a temporary conflict profile X (n).

Add data from random unused agents to X (n) until number of used agents is equal n, output the conflict profile.

Determine and output temporary consensus C (X (n)).

Calculate and output distance d(C(N), C(X(n)).

If n < N, increment n and repeat from step 6.

The first series of simulations use multiple Boolean attributes for each member of the collective (computer agent). The most interesting results were obtained for N = 1000 agents and 100 attributes. Each temporary consensus and the final one was a set of 100 binary values. We used Hamming distance and majority vote to determine consensus (in this case, majority vote is equivalent to O1 criterion). The results presented in Fig. 1 clearly show the non-monotonicity of convergence to the final consensus. Even after averaging ten different runs the results are not decreasing consistently. In a single run, there are a lot more random increases during the expansion of the conflict profile. This is in large part due to selecting elements to the profile at random. If elements were added in ordered fashion, the results would be more homogenous. Unfortunately, in real world situations this requires using statistical approach to selecting representative members of the collective. In many cases this is not feasible and the required group of representatives may be a vary large part of the collective.

In the next series of simulations we used multiple numerical attributes and the O2 consensus choice function for real values (a simple average for each attribute). Once again we used N = 1000 computer agents to simulate conflict participants. We also used standard Euclidean distance measure for numerical values. The real numbers domain is limited to [0, k) and for each participant for each attribute it is generated with uniform distribution. The final consensus, as well as all temporary consensuses are a set of real numbers. Interesting results may be seen in the example of k = 100 and 100 attributes presented in Fig. 2. The results are still non-monotonically convergent for any single example, but the average of 10 runs is non-increasing. In each case the results are convergent to the final consensus. Our opinion is that the larger range of possible consensus values leads to better averaging it in each case, resulting in a smoother convergence.

We repeated the experiment with the same settings, but for O1 consensus choice function (Fig. 3). In this case the convergence is once again more erratic, but even the first results are as much as ten times closer to the final one, than the first results in the case of O2 approach. Other simulations for different parameters show similar results – in general the expanding conflict profile case with O1 consensus choice function is much closer to the final consensus, even for first few results; on the other hand the O2 consensus choice function allows for a much smoother curve – it is much closer to being monotonically convergent.

5 Knowledge integration as a process

The other aspect we consider in this paper is treating the knowledge integration as a longer process and not an instantaneous change of knowledge states [13, 14]. Both approaches assume the same inputs (knowledge of collective members) and output (integrated collective knowledge), but the latter does not consider how the process occurs in real world situations and how it may influence the result. It is especially represented by centralized multi-agent systems, where a single supervisor is used to determine the consensus. Some decentralized multi-agent systems don’t use the supervisor, but the only consideration in developing them is that the consensus is achieved (see Reliability postulate above) – if the consensus algorithm is stable.

In contrast we focus on how the decentralized approach influences the process of knowledge integration. We use a model of asynchronous group communication for social agents (people or computer programs) with the following assumptions[13, 14]:

Agents communicate in irregular intervals. Every time moment each agent has a chance P_c that it will initiate communication. The probability that it will communicate in the first moment is P₁ = P_c and in each following moment it is P_n = P_c · (1 - P_c). The chance of communication P_n is a limited sequence and outgoing communication is not guaranteed (but for P_c → 1 it is more and more probable).

Communication between agents is unidirectional. Each agents selects at random (semi-random) a receiver agent and sends him his knowledge state. After sending messages, the agents do not wait for replies. Agents do not verify if the knowledge was received correctly.

Different approaches may be used to process incoming knowledge. An agent may immediately try to integrate it with his own knowledge state, store it and try to integrate a larger group of collected knowledge states, or it may even discard it entirely. For the integration process itself, different algorithms may be used (in our research we mostly focus on integration algorithms based on O2 postulate).

Agents have groups of preferred receivers. When the agent selects the target of his communication there is a chance that he will select an agent from the overall population, or an agent from his preferred group.

In a centralized approach, the assumptions are often opposite:

The agents communicate regularly, either every discrete time period or once its information updates. Agents only send information to the supervisor.

There is a single supervisor agent (or a hierarchy of supervisor agents, similar to a rooted tree), that only functions to gather and integrate the knowledge of the collective.

Supervisor agent regularly sends updated collective knowledge state to all other agents.

One may note that other approaches to multi-agent systems and agent communication are possible. For example, there are decentralized multi-agent systems with synchronization via the so-called heartbeat – regular synchronization cycles. As those rarely deal with knowledge integration and were not observed to appear spontaneously in real-world group communication, they will not be discussed in this paper.

We may roughly estimate the time needed to achieve consensus in each case. To this purpose we introduce the following notation:

A = {a_i : i ∈ {0, 1, …, n}} is the set of n observation agents and, if it is necessary, one supervisor agent (denoted by a₀).

T_i,j is the average time between communication from a_i to a_j.

The centralized approach requires each agent to send its knowledge state to the supervisor and the supervisor to send the results to all other agents. This is based on an additional assumption, that we have not stated in our previous papers, that is we require each agent to have the same knowledge state at the end of integration process. The time required to spread the consensus in this way is:

$\begin{matrix} T_{C} & = & \max_{i \in {1, \dots, n}} (T_{j, 0}) \\ + \max_{i \in {1, \dots, n}} (T_{0, j}) \end{matrix}$ (10)

The asynchronous decentralized approach, as outlined above, requires each agent to receive communication from each other agent (directly or indirectly). The time required for this may be estimated as:

$\begin{matrix} T_{D} & = & \max_{i, j \in {1, \dots, n}} (\min {T_{i, j}, T_{i, x_{1}} + T_{x_{1}, j}, \dots, \\ T_{i, x_{1}} + \sum_{z = 1}^{n - 1} T_{x_{z}, x_{z + 1}} + T_{x_{n}, j}}) \end{matrix}$ (11) For any single node the worst case here assumes that the information from some other node will need to travel through all the other nodes – as long as it is faster than using a shorter route. As a whole decentralized system this is somewhat analogous to a ring topology network. Agent a₁ can only communicate to a₂ and receive from a_n, agent a₂ only to a₃ and receive from a₁, etc. In that case the time may be estimated as: $T_{R} = 2 \sum_{i = 1}^{n - 1} T_{i, i + 1} + T_{n - 1, n} + T_{n, 1}$ (12)

This is an especially dangerous case. In a fully decentralized multi-agent system, no single agent is critical to performing knowledge integration. In a centralized system, the supervisor is the only agent that has access to all the knowledge of the collective, and the only one that can perform integration. In a ring decentralized system, each agent is critical, as without it knowledge would not be forwarded beyond this point in the agent network. As such, this situation should be avoided in any practical application.

As with expanding conflict profile, we have prepared simulation experiments to observe how integration behaves when decomposed into a longer process. The details are presented in the next section.

6 Influence of mode of communication on collective knowledge integration

For purposes of our research we have developed a simulation environment in Java using JADE agent framework [5]. This environment is independent from the one described in Section 4. We used this environment to study both centralized and decentralized approach to collective knowledge integration. For the decentralized approach we also allowed the option to enable preferred receivers for each agent and allow studying the influence of ad-hoc grouping of agents on the final consensus.

While the JADE framework is centralized due to its architecture, its mechanisms allow the simulation of decentralized approach as required in our research. For most practical application to properly gain advantages of the decentralized approach, other frameworks should be used. We implement two types of agents, a basic SocialAgents that represents a member of the collective, and a SupervisorAgent that is used only in the centralized approach. Social agents generate their knowledge at random and the aim of the whole multi-agent system is to determine the collective knowledge of the group. In the basic case used in most simulation runs, the internal knowledge of social agents was simply an integer value between 0 and K generated with uniform distribution. In the centralized case, the social agents communicate their knowledge to the supervisor, which integrates it and sends the resulting knowledge state back to all the social agents. In the decentralized case, the social agents communicate between each other. We use discrete time intervals as ticksT (time moments) in system. Each tick every social agent has a chance to initiate communication using the mode selected and there is an estimated time to communicate for each agent T_a. In the centralized case the social agents will communicate only to the supervisor, while in the decentralized one they will select a receiver at random (with uniform distribution; or first selecting whether to communicate to his preferred contacts or to the general population of agents – with probability p and (1 - p), respectively, and then in each group with uniform distribution). Every few cycles the agents also write their knowledge state to the output for the purposes of observing it. We may randomize the number of agents up to several thousands (a hardware limitation of the PC platform used) and may increase the number of issues that the collective knowledge consists of. For ease of readability, we limit the number of issues in examples below to one.

We allowed the option to use different strategies for Integration, upon receiving foreign knowledge, however early experiments have shown that the 2-Optimality criterion [16] working on some given number L of outside inputs (and the interior knowledge state of an agent) gives the best results. For social agents we allowed the option of L = 0 and L = 1, where the agent immediately integrates the outside knowledge with his own. Otherwise it gathers up to L foreign communicates and only then integrates them with his own knowledge state. Supervisor agents gathers results from all the agents before integration. After the consensus is reached, the agent changes its own knowledge state, and in case of supervisor agent awaits its time to communicate to send it to all social agents.

Our first round of experiments was a general comparison of centralized and decentralized systems. We used groups of between 200 and 5000 agents with the same hardware specifications and system parameters. The observed variables were the time needed to achieve consensus in all social agents, with observation of the system state every second. We also observed the value of the final consensus and how much the decentralized one differed from the centralized one. We did not use any preferred communication channels between agents. The overview of the results averaged over 100 runs is presented in Table 1. The error columns refer to incomplete runs (no consensus achieved in finite time) in case of centralized approach and to the averaged difference between the centralized consensus and decentralized one for the decentralized approach (we assume the centralized consensus is correct).

Due to hardware limitations the centralized approach starts having problems with around 1000 agents and fully stops working at 2000 agents, while with the same parameters the decentralized one continues to work up to 5000 agents (limitation of the whole simulation environment). This is due to the supervisor agent receiving to many incoming communicates and not being able to process them. The decentralized approach does not have this problem. Additionally, even for the most basic method of integration (L = 0) the decentralized approach leads to better results for a larger number of agents. Our conclusion is that in the most basic cases, the centralized systems should be used up to the hardware limitations of agent number, while for larger required number of agents a decentralized system would continue to work with no need of updating the hardware and with less than 1% of error.

In the next series of experiment runs, we also used higher values of L and observed how the group consensus is reached in decentralized systems with different approaches to preferred communication. Figures 4 and 5 show interesting examples of such runs with 100 social agents per run. For ease of readability, we only show three variables - the collective knowledge (calculated in centralized way from temporary knowledge states of agents in the output file), and knowledge states of agents most distant from the consensus in each direction (due to using integer values, the minimum and maximum of agent knowledge states).

We have gathered a number of initial observations from these experimental runs. We are planning more, expanded experiments to further verify these observations, and if possible - proposing some statistically verifiable hypotheses.

In general, a large chance of preferred communication may lead to excluding some agents from achieving the final consensus in finite time. In some experimental runs some agents had no incoming connections, thus they would not be influenced by any other agent. While they still changed the knowledge of the group (by outgoing connections), their own knowledge did not change in the time allotted for the experiment. We call this situation the local consensus of the group. While this was a random occurrence, it was more common with higher chances of communication to the preferred group. This observation may be simplified to the statement: as probability of communication to some agent decreases, the time required by it to reach group consensus increases. An example is visible in Fig. 5.

On the other hand, small chance of preferred communication usually increases the time to achieve consensus by the group. The temporary grouping occurring with a friend network acts somewhat similar to multistage integration [15], and analogically to that approach reduces the time required to calculate the final consensus. Note that this does not always occur, as in Fig. 4 the consensus is reached by agents faster than in Fig. 5 (excluding the local consensus problem).

A small number of inputs gathered by the agent before integration (small L) usually leads to large errors in integration (the difference between the final consensus in the decentralized group and a consensus that would be achieved with using a supervisor in a centralized system). In this case agents knowledge state changes rapidly and often this leads to changes in the knowledge of the whole group. While in some cases this may be desirable, more often the situation should be avoided. On the other hand the larger number of agents required for integration (large L) may increase the time required to achieve the consensus – the agent communication networks may become similar to the ring topology described above.

7 Application: Weather forecast system

Concurrently to our theoretical research, we have been developing a multi-agent based weather forecast system. The common element with the research presented above is the need to integrate different forecasts between agents. To this purpose we have applied the approaches described in Sections 5 and 6.

The general architecture of the system [8] consists of three different layers of agents:

Source layer - where in the prototype system a group of agents downloaded weather forecasts from Internet websites or created own forecasts based on historical data (using regression and other mathematical methods). Further iterations of the system will also use real-time weather observations.

Integration layer - where a single supervisor agent integrated forecasts from the source agents using consensus theory and created a single forecast. When the decentralized approach was used, the agents of the source layer had the functionality of the integration layer (similar to social agents in Section 6).

Interaction layer - where the single forecast was displayed to the user.

The implemented multi-agent system allowed any number of source agents to drop out, displaying some forecast to the user in any case. In the centralized system we used various approaches to data integration, based on consensus and choice theory. The only one applicable to decentralized approach was the O2 consensus choice function.

We used this system on current real-world data in Wroclaw, Poland in April-May 2015 (centralized), October 2015 (centralized and decentralized with L = 0) and April-May 2016 (all approaches). The results for the first period are described in detail in [8]. The main points of interest are that the centralized system had smaller errors than the worst forecast in the source when using consensus theory, but also smaller error than the average of those sources when using choice theory [6]. The result of temperature prediction, only for 2-Optimality consensus choice function (choice theory is not applicable to decentralized approach), are shown in Table 2, as compared to real temperature that day.

The results of the system were slightly worse in the second period, even after additional tuning the parameters. Surprisingly, the basic decentralized approach was marginally better than the centralized one. This could be due to used forecast sources being more biased towards high or low predictions in this period or due to specific weather patterns. This initial experiment has shown that the decentralized approach may be successfully used and even achieve better results in practical applications.

In our next round of experiments, we added the option to use higher values of L. We determined some initial parameters based on simulation runs (based on those shown in Section 6) and further fine tuned them in each version of the system. In this case the weather predictions were virtually identical. Once again, the result may be influenced by specific weather patterns in the period or bias in the forecast sources.

This few short runs show that the decentralized approach to collective knowledge integration may be successfully used in practical applications that previously required a central supervisor agent. Currently, we are working on other prototype applications using the decentralized approach to find any possible issues that may occur.

8 Conclusions

This paper contains the extended descriptions of our research into collective knowledge integration and how it occurs over time. We briefly described some basic notions on expanding the size of the collective during continuous-time integration of its knowledge, providing some basic observations on its influence on the process of integration. We also describe asynchronous group communication in a decentralized multi-agent system, both with and without some additional network of preferred communication channels. We observe how this approach influences the final consensus reached by the collective, as well as some additional aspects, like the creation of local consensus for some sub-groups of agents.

In both cases we have also conducted some simulation experiments to find some patterns in the integration process or influence on the consensus function. We briefly describe those experiments and their results, expanded upon those present in our previous papers [12 –14]. We have also conducted experiments on a prototype weather prediction system based on this research, showing that there is no significant difference between different types of agent communication in this practical application.

Additional prototype applications are the main point of our intended future research into this area. One may consider a system that observes the behavior of a car driver in different traffic situations. Such system may for example be mounted in a car of known traffic-offender and monitor him continuously. If one gathered all the observations from a longer period of time, the consensus of them would show if this driver is a good or a bad one. In real world situation we would receive the data as a stream, with periodically added new information. Using the methodology briefly discussed in this paper, we could observe the changing consensus of those data-points. Once a certain threshold is crossed, we know that long-term, the driver will only behave more and more similar to this temporary consensus (but with possible temporary breaks of the trend). Thus further observation is unnecessary. Other potential applications we consider are economic prediction and warning systems and industrial grain analysis systems - both areas in which there are already centralized multi-agent systems.

Acknowledgment

This research was co-financed by Polish Ministry of Science and Higher Education grant.

References

Abed-alguni

B.H.

, Chalup

S.K.

, Henskens

F.A.

and Paul

D.J.

, A multi-agent cooperative reinforcement learning model using a hierarchy of consultants, tutors and workers, In: Vietnam Journal of Computer Science2(4) (2015), 213–226, Springer.

Chaimontree

, Atkinson

and Coenen

, A multi-agent based approach to clustering: Harnessing the power of agents, Agents and Data Mining Interaction, Springer Berlin Heidelberg, 2012, pp. 16–29.

Hale

M.T.

, Nedic

and Egerstedt

, Cloud-Based Centralized/ Decentralized Multi-Agent Optimization with Communication Delays. 2015, arXiv preprint arXiv: 1508.06230.

Iscaro

and Nakamiti

, A supervisor agent for urban traffic monitoring, IEEE International Multi-Disciplinary Conference on Cognitive Methods in Situation Awareness and Decision Support (CogSIMA), IEEE2013, pp. 167–170.

JADE, Java Agent Development Framework, available at: http://jade.tilab.com/

Jiang

, Marcolino

L.S.

, Procaccia

A.D.

, Sandholm

, Shah

and Tambe

, Diverse randomized agents vote to win. Advances in Neural Information Processing Systems, 2014, pp. 2573–2581.

Maleszka

, Nguyen

N.T.

, Urbanek

and Wawrzak-Chodaczek

, Building Educational and Marketing Models of Diffusion in Knowledge and Opinion Transmission. Computational Collective Intelligence, Technologies and Applications, Lecture Notes in Artificial Intelligence, Springer International Publishing, 2014, pp. 164–174.

Mercik

, Tolkacz

, Wojciechowska

and Maleszka

, Wykorzystanie integracji wiedzy do zwiekszenia efektywnosci prognozowania w warunkach niepewnosci. Porebska-Miac

(Ed.), Systemy Wspomagania Organizacji 2015, Wydawnictwo Uniwersytetu Ekonomicznego w Katowicach, Katowice, 2015.

De Montjoye

Y.-A.

, Stopczynski

, Shmueli

, Pentland

and Lehmann

, The Strength of the Strongest Ties in Collaborative Problem Solving. Scientific reports 4, Nature Publishing Group, 2014.

10.

Nagata

and Sasaki

, A multi-agent approach to power system restoration, IEEE Transactions on Power Systems17(2) (2002), 457–462. IEEE.

11.

Nakamiti

, da Silva

V.E.

, Ventura

J.H.

and da Silva

S.A.

, Urban traffic control and monitoringâĂŞan approach for the Brazilian intelligent cities project. Practical Applications of Intelligent Systems, Springer Berlin Heidelberg, 2012, pp. 543–551.

12.

Maleszka

, Consensus with Expanding Conflict Profile. New Trends in Intelligent Information and Database Systems Studies in Computational Intelligence Vol. 598, Springer, 2015, pp. 291–299.

13.

Maleszka

, Knowledge in Asynchronous Social Group Communication. Intelligent Information and Database Systems, Lecture Notes in Computer Science Vol. 9621, Springer, 2016, pp. 364–373.

14.

Maleszka

, Local and Global Consensus in Asynchronous Group Communication. Proceedings of IEEE SMC, 2016, (in print).

15.

Maleszka

, On Decomposing Integration Tasks for Hierarchical Structures. Computational Collective Intelligence Technologies and Applications, Lecture Notes in Computer Science Vol. 8733, Springer, 2014, pp. 434–443.

16.

Nguyen

N.T.

, Advanced methods for inconsistent knowledge management, Springer, 2007.

17.

Peterson

C.K.

, Newman

A.J.

and Spall

J.C.

, Simulation-based examination of the limits of performance for decentralized multi-agent surveillance and tracking of undersea targets. SPIE Defense+ Security, International Society for Optics and Photonics, 2014, pp. 90910F–90910F.

18.

Barthelemy

J.P.

and Janowitz

M.F.

, A formal theory of consensus, In: Siam Journal of Discrete Mathematics4 (1991), 305–322.

19.

Bhat

S.P.

and Bernstein

D.S.

, Finite-time stability of continuous autonomous systems, In: Siam J Control Optim38(3) (2000), 751–766.

20.

Chen

, Lewis

F.L.

and Xie

, Finite-time distributed consensus via binary control protocols, In: Automatica47 (2011), 1962–1968.

21.

, Dua

and Lin

, Finite-time consensus algorithm for multi-agent systems with double-integrator dynamics, In: Automatica47 (2011), 1706–1712.

22.

McMorris

F.R.

and Powers

R.C.

, The median procedure in a formal theory of consensus, In: Siam Journal of Discrete Mathematics14 (1995), 507–516.

23.

Nguyen

V.D.

and Nguyen

N.T.

, An Influence Analysis of the Inconsistency Degree on the Quality of Collective Knowledge for Objective Case. Intelligent Information and Database Systems, Lecture Notes in Computer Science Vol. 9621, Springer, 2016, pp. 23–32.

24.

Ren

, Beard

R.W.

and Atkins

E.M.

, A Survey of Consensus Problems in Multi-agent Coordination. American Control Conference, 2005 Proceedings of the 2005 IEEE, 2005, pp. 1859–1864.

25.

Wang

and Hong

, Finite-Time Consensus for Multi-Agent Networks with Second-Order Agent Dynamics. Proceedings of the IFAC World Congress, Seoul, 2008, pp. 15185–15190.

26.

Yin

, Li

, Zhang

and Zhu

, Task allocation via coalition formation in agent networks, In: Journal of Intelligent & Fuzzy Systems30(1) (2015), 197–210.

27.

Zhang

, Ge

, Jiang

and Yang

, A new consensus model for group decision making using fuzzy linguistic preference relations with heterogeneous experts, In: Journal of Intelligent & Fuzzy Systems30(1) (2015), 171–182.