Unreliable communication in high-performance distributed multi-agent systems: A ingenious scheme in high computing

Abstract

Designing of distributed consensus algorithms featuring accuracy, robustness, reliability, and speed of convergence is in high demand for various multi-agent applications. In this research, it has been investigated to device a novel design of distributed estimation algorithm which can tackle the problem of unreliable communication among multi-agents to achieve consensus on the average value of their initial values and must be capable of computing the total number of agents in the system under dynamically changing interaction topologies. A dynamically changing network topology is considered in this research with unreliable communication links, and four different scenarios are established to be analyzed for the proposed consensus-based distributed estimation algorithm. This study established a consensus for a dynamically changing interaction topology among agents, for addition of agents in the network with dynamically switching topology at any instant in communication, for removal of agents from the network with dynamically switching topology at any instant in communication, and for a fixed topology with link failure and a reconnection with the same agent after each iteration. The proposed algorithm paces up the rate of convergence by reducing the number of iteration, along with sure convergence of the designed algorithm using the concepts of stochastic differential equation theory, control system theory, algebraic graph theory, and algebraic matrix theory. Finally, in the end, simulation results are provided which are clear evidence to validate the effectiveness of theoretical results of the proposed algorithm in comparison to previously known consensus algorithms in terms of different performance parameters.

Keywords

Multi-agent systems unreliable communication distributed estimation distributed and consensus control

Introduction

Multi-agent system refers to a collection of distributive sub-systems which are interconnected using a communication topology. The sub-systems or agents exchange information and are capable of learning from each other to achieve a global objective.

Multi-agent system gains tremendous significance in the framework of networked systems due to its distributed nature and are widely used in various applications which range from the control of an unmanned aerial vehicle (UAV),¹ decision-making in autonomous robots,² satellite coordination and alignment,³ and flocking.⁴ Moreover, various other multi-agent applications are discussed thoroughly in Cao et al.⁵

A plethora of studies have been carried out by various researchers in the field of multi-agent systems, and one of the major issues addressed is distribution estimation under unreliable communication environment. Due to limited sensing range, limited communication capabilities, and limited resources, each agent can only interchange information with their neighboring agent to compute the local measurements to achieve distribution estimation. In this way, computation for the whole network information cannot be guaranteed. Therefore, we encouraged to design such a distributed estimation algorithm which can complete the estimation assignment in a cooperative mode using indigenous information of the agents by communicating with its neighbors in solitary. Such exchange of information in distributed multi-agent systems leads the agents to reach a mutual consensus which gives advantage over a centralized system where statistics are imperative to be communicated to a collection of agents for decision-making. Cooperative scheming and convergence investigation of distributed estimation algorithms have gained an innumerable importance. Outcomes of such algorithms result in robustness for particular agent failure, reduction in communication overhead, and lessen the computational cost.⁶

As discussed, agents in multi-agent systems communicate and share their information with their neighborhood only in a distributed manner. The primary goal in this research is to establish control and coordination between the agents without any centralized processing. Multiple techniques and algorithms are presented by various researchers for the convergence of all agents in a network on a single state value. One of the well-known practices for the convergence is the consensus algorithm. In the absence of global information and lack of centralized control, agents cooperate with each other in a form of full autonomous distributed network. Challenges posed by the other researches motivated and encouraged us to address these issues. This article explores few of the control complications in cooperative control of networked multi-agent systems. Network with switching topologies and unreliable communication is reflected in simulation results. This research considered the resource-constrained agents, where there is limited source of power, which will affect the communication capabilities and communication range of the agents.

The major contribution of this article is to propose a new method for a consensus in multi-agent systems in the existence of uncertain switching topology and unreliable communication due to any reason such as temporary communication losses. Moreover, one of the objectives of this article is to present an algorithm which minimizes the number of iterations and time to achieve the average consensus. Furthermore, computing the number of agents contributing at any prompt of time under unreliable communication is also set as one of the major objectives for the study. This research has presented four different scenarios for consensus under unreliable communication topology, which includes dynamically changing interaction topologies among agents, addition of agents in the network with dynamically switching topology at any instant of time, removal of agents from the network with dynamically switching topology at any instant of time, and finally a fixed topology with link failure and a reconnection with the same agent after each iteration. The global objective of pure coordination among the agents in a network is achieved by using the key concepts from the theory of algebraic and matrix theory, which are enlightened in detail in the forthcoming sections. Moreover, the different distributed algorithms in existing literature have also been investigated rigorously, and a comparison of the proposed and existing algorithms by considering common parameters in each scenario is made.

This article is structured as follows. Section “Related work” explains the related work for the distributed algorithms, section “Preliminaries” demonstrate the preliminaries of algebraic graph and matrix theories, section “Convergence condition” explains the proof of convergence condition, while the proposed formulated distributed algorithm is outlined in section “Proposed algorithm.” Section “Numerical examples and simulation results” is devoted to numerical example and simulation results; four different scenarios are presented to illustrate the theoretical results. Finally, section “Conclusion” concludes the article with concluding remarks and advanced future directions.

Related work

A very rich literature of consensus algorithms is accessible for the different scenarios to achieve control and coordination within a multi-agent system. Consensus control algorithms for the distributed interaction of agents in a particle system in a unique direction were pioneered and studied by Vicsek et al.⁷ Another approach with different network topologies, introducing directed and undirected graphs and networks with time delay, was presented by Saber and Murray.⁸ Moreover, the basic concepts of graph and matrix theories were applied in multi-agent system for achieving consensus by Jadbabaie et al.⁹ Event-based triggering consensus was proposed in Fan et al.,¹⁰ and rendezvous algorithm was presented in Fan et al.¹¹ Similarly, multi-agent system with dynamic network topology has been addressed in literature by different researches from diverse fields of studies using different approaches. Consensus was achieved using Markov chains and linear matrix inequality (LMI) by using non-stochastic matrix approach for switching topology in Zhao et al.¹² A distributed algorithm established on a diffusion approach is explained in Cattivelli et al.¹³ In this algorithm, fresh information is spread across a network but at the cost of increased communication overhead, which leads the network to perform worse if the information is corrupted due to network environment uncertainties. Video-based traffic surveillance algorithm for multi-agent system named Monitorix is introduced in Abreu et al.¹⁴ In this study, the projected algorithm uses an adaptive, table-driven, and application self-governed methodology for extracting topographies from video raw data which later on are used for traffic modeling. Furthermore, another study has been carried out by Kokiopoulou and Frossard,¹⁵ where they suggest a polynomial filtering distributed algorithm that will figure its spectrum for faster convergence within a network, that is, valid for both static and dynamic network topologies. This research accelerates the convergence of distributed consensus and computes new values by aggregating the earlier estimated values of the agents for periodic update. Similarly, in another research,¹⁶ the authors propose a distributed algorithm for node counting for ad hoc networks under unreliable communication with limited resources and compare it with the other existing theories. Problems such as exponential finite time coordination in multi-agent systems are discussed in Liu et al.¹⁷ The finding of this research is to achieve consensus by introducing a pinning control strategy. It fundamentally emphases on two main arguments: (1) setting time of Lyapunov function and (2) weak connected communication topology is considered for simulation applying the key concepts of spanning tree from graph theory.

Furthermore, other framework for different applications was proposed in Shi et al.¹⁸ They address unique problem of enclosing control of second-order multi-agent systems under static and dynamic topologies. The major discovery of this research is to achieve an intermediate round formation for targeted agents. To design an algorithm for such consensus, concepts of Lyapunov function and Lasalles invariance principle are practiced to achieve the desired goal.

Distributed algorithm addressing both linear and nonlinear systems is proposed by Kar et al.¹⁹ In this framework, uncertainties such as random link failure and error in quantization are addressed. To achieve pure convergence, uninformed waver is accompanying the signal to be quantized and then transmitted. On the other hand, link failure is autonomous in network communication topology. A fresh idea to find the network agents in a communication network participating at any prompt of time in switching topologies is attaining excessive admiration. Algorithm for the agent counting in the ad hoc networks is presented in Evers et al.¹⁶ and Perkins and Royer.²⁰ Similarly, Rehan and Bansal²¹ deliver a detailed comparison of different evolutionary algorithms such as gossip algorithm, swarm optimization, and ant optimization to reach an optimum solution for large-scale networks to validate the effectiveness of these algorithms.

After briefly summarizing different frameworks and the existing approaches, we proposed a novel approach of distributed consensus algorithm which besides convergence is also responsible for agents’ estimation under switching and unreliable network topologies with less computational and processing time.

Preliminaries

In cooperative control of multi-agent systems, graph theory and stochastic matrix theory are the basic tools which are used to understand the later part of this article. In this section, a basic introduction of key concepts from both the theories is presented for better understanding of the proposed algorithm.

Graph theory

In designing of consensus algorithms, graph theory is used as a basic tool for designing and modeling of system topology for connecting agents. In simple words, graph is referred as a group of objects which are interconnected directly or indirectly in the form of pairs through connectivity links. The connectivity links in a graph are called edges $E$ while the interconnected and communicating objects are called vertices $V$ . In algebra, a graph can be represented in the form of $G = (V, E)$ where $V = {υ_{1}, υ_{2}, \dots, υ_{N}}$ where the total number of participating agents in a network can be represented by $N$ and $E = V \times V$ can be defined as a set of edges and vertices, which are considered to be the bidirectional connecting links between the agents. A graph can be categorized into types connected or unconnected, and a graph is said to be connected if there exists a communication link among all existing pairs of vertices.

Directly connected vertices in a system are called the neighbors, and algebraically they can be presented by $N_{i}$ for agent $i$ . A graph can be directed or undirected. Directed graph is defined as a set of vertices connected together through a specific direction linked with them, where edges are directed from vertex to vertex. $(υ_{i}, υ_{j})$ represents an ordered pair of vertices, where agent $j$ is receiving information from agent $i$ . Similarly, $(υ_{1}, υ_{2}), (υ_{2}, υ_{3}), \dots, (υ_{n - 1}, υ_{n})$ represents the directed path as a sequence of directed edges. On the other hand, in undirected graph, there is no direction associated with the edges. Algebraically, undirected graph can be expressed as $(v_{i}, v_{j})$ showing that agent $i$ and agent $j$ can transmit bidirectionally.

A spanning tree in a graph $G$ stated as its subset has all the vertices linked with least quantity of edges. Spanning tree cannot be disengaged, and for each directed or undirected graph there should fundamentally be at least one spanning tree.^22–26

Matrix theory

Matrix theory is directly associated with the convergence analysis of multi-agent systems and is of prime importance. If all the entries in a matrix are positive, then the matrix is said to be a positive matrix, and if any of the entry is negative then the matrix is called a negative matrix. Row stochastic matrix $P$ is a fundamental matrix in investigation and scheming of distributed consensus algorithm. It is the matrix in which the result sum of all the row elements equals to positive one. Moreover, it is called stochastic, indecomposable, aperiodic (SIA) matrix, if it satisfies the condition $lim_{k \to \infty} P^{k} = 1 w^{T}$ . Here, $T$ is a transpose of the matrix, 1 is a column vector, in which the whole elements are one, and finally $w$ symbolizes a column vector again. Furthermore, if in the matrix all rows come to the same values, then it is said to be rank1 matrix.^22,26

To find the adjacent agents connected to any particular agent in a graph $G$ , an adjacency matrix $A = [a_{ij}]$ can be used, and mathematically it can be expressed as

a_{ij} = {\begin{matrix} 1 & if (v_{i}, v_{j}) \in E \\ 0 & otherwise \end{matrix}

Moreover, a diagonal matrix $D = [d_{ii}]$ is a matrix which indicates the degree of all the vertices participating in a communication network, that is, the number of adjacent agents to $i$ . It is also known as a degree matrix. Furthermore, a concept of Laplacian matrix is introduced in matrix theory, which uses the results of both adjacency and diagonal matrices. It can be formulated as $L = D - A$ . Along with these matrices, a stochastic matrix $P = [p_{ij}] \in R^{n \times n}$ and $G (P)$ is a topology graph associated with the matrix, and it plays a significant part in manipulating the distributed consensus algorithm. Stochastic matrix is also acknowledged as probability matrix and is generally used to describe transitions.^22,25,26

For better understanding of the matrix and graph theories, let us consider a network with five agents, which are denoted as $v_{1}, \dots, v_{5}$ , as shown in Figure 1. The connections shown in the graph indicate the presence of communication links to exchange information between the control agents. For the graph considered in Figure 1, we can write the following

V = {v_{1}, v_{2}, v_{3}, v_{4}, v_{5}}

where the edge sets for the vertices can be written as

\begin{matrix} E = {(v_{1}, v_{2}), (v_{2}, v_{3}), \dots, (v_{4}, v_{5})} \\ \begin{matrix} N_{1} = {v_{2}} \\ N_{2} = {v_{1}, v_{3}, v_{5}} \\ N_{3} = {v_{2}, v_{4}, v_{5}} \\ N_{4} = {v_{3}, v_{5}} \\ N_{5} = {v_{2}, v_{3}, v_{5}} \end{matrix} \end{matrix}

Figure 1.

A graph illustrating five agents and communication links to indicate the exchange of state variables between the systems.

The adjacency matrix A for the above graph can be computed as follows

A = [\begin{matrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 \end{matrix}]

The degree matrix, D, for the above graph is as follows

D = [\begin{matrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 0 \\ 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 & 3 \end{matrix}]

The Laplacian matrix, L, will be computed as follows

L = [\begin{matrix} 1 & - 1 & 0 & 0 & 0 \\ - 1 & 3 & - 1 & 0 & - 1 \\ 0 & - 1 & 3 & - 1 & - 1 \\ 0 & 0 & - 1 & 2 & - 1 \\ 0 & - 1 & - 1 & - 1 & 3 \end{matrix}]

In designing of the consensus algorithm of control and coordination for a intelligent multi-agent system, few of the lemmas from the control theory are very useful for deriving the major results to achieve convergence at a single point.

Lemma 2.1

Let us consider a set of stochastic matrices $Z_{1}, Z_{2}, \dots, Z_{n}$ . If a graph that is finally acquired by the union operation of all the graphs in matrices’ set $G (Z_{1}), G (Z_{2}), \dots, G (Z_{n})$ has a spanning tree, then the matrix product $Z_{n}, Z_{n - 1}, \dots, Z_{1}$ is said to be an SIA.^25,27

Lemma 2.2

If we consider a stochastic matrix $Z$ , then $Z$ is supposed to be SIA if there exists a spanning tree in $G (Z)$ ; moreover, a root vertex of the spanning tree also has a self-loop.^25,28

Lemma 2.1 and Lemma 2.2 express the usefulness of an SIA matrix in a graph connectivity. With regard to connected graph with a random communication topology, there should be at least one of the paths available to reach any random node. Using this concept, multiple small graphs may exist in a network, but in case of combining or taking union of all the graphs in a network all the agents must be connected through a single or multiple routes. This concept of SIA matrix and spanning tree plays a vital role in achieving the convergence value when the network experiences a unreliable communication.

Convergence condition

This research considers the problem of computing a linear iteration that produces distributed averaging consensus over a network. Fast average consensus is achieved by computing the average of initial values of the agents. It has also been concerned to satisfy the general conditions and design of the weight matrix for the linear iteration in such a way that all agents must agree on a common average value for fast convergence.

In this section, we deal with distributed linear iterations,^29,30 of the form given below

y_{i} (t + 1) = ζ_{ii} (t) y_{i} (t) + \sum_{j \in N_{i}} ζ_{ij} (t) y_{j} (t) s

(1)

where $i = 1, 2, 3, \dots, n$ , and $t = 0, 1, 2, \dots$ ; $ζ_{ij}$ is the weight on $y_{j}$ at agent $i$ and $ζ_{ii} = (1 - \sum_{j \in N_{i}} ζ_{ij})$ . Setting $ζ_{ij} = 0$ for $j \in N_{i}$ , then the vector form of equation (1) can be written as

Y (t + 1) = ζ (t) Y (t)

(2)

where

Y (t + 1) = [\begin{matrix} Y_{1} (t + 1) \\ Y_{2} (t + 1) \\ \dots \\ \dots \\ Y_{n} (t + 1) \end{matrix}]

Y (t) = [\begin{matrix} Y_{1} (t) \\ Y_{2} (t) \\ \dots \\ \dots \\ Y_{n} (t) \end{matrix}]

Here, we consider the sparsity matrix; it is a matrix whose majority of the elements are 0. The constraint on the sparsity pattern of matrix $ζ$ can be expressed as $ζ \in ψ$ , where

ψ = {ζ \in R^{nxn} | ζ_{ij} = 0 if {i, j} \notin E and i \neq j}

With the definition of a t-step transition matrix

ζ (t) = ζ (t - 1), \dots, ζ (1) ζ (0)

Equation (2) can be expressed in the form of

Y (t) = (Π_{i = 0}^{t - 1} ζ (t)) Y (0)

(3)

Equation (3) means that for all t

Y (t) = ζ (t) Y (0)

(4)

The next assignment is to choose a weight matrix such that the convergence condition is satisfied and $Y (t)$ converges to the average vector, for any initial value $Y (0)$

lim_{t \to \infty} Y (t) = (\frac{1}{n}) 11^{T} Y (0)

(5)

where n is the total number of agents

lim_{t \to \infty} Y (t) = lim_{t \to \infty} ζ (t) Y (0)

(6)

Now comparing equations (5) and (6), we get

lim_{t \to \infty} ζ (t) Y (0) = (\frac{1}{n}) 11^{T} Y (0)

(7)

The 1 in equation (7) is a vector of ones. Comparing the terms in equation (7), we get

lim_{t \to \infty} ζ (t) = (\frac{1}{n}) 11^{T}

(8)

We assume equation (8) holds the condition for asymptotic convergence factor, so asymptotic convergence factor^15,31 can be defined as

r_{a s y m} (ζ (t)) = \underset{{y (0) \neq}^{\cdot}}{s u p} {(\frac{{‖ y (t) - \overset{\cdot}{y} ‖}_{2}}{{‖ y (0) - \overset{\cdot}{y} ‖}_{2}})}^{1 / t}

(9)

where ${\overset{\cdot}{y}}^{=} lim_{t \to \infty} y (t)$ .

Now from equation (9), associated convergence time can be defined as

τ_{asym} = \frac{1}{\log (1 / r_{asym} (ζ (t)))}

(10)

Convergence time associated with equation (9) provides the (asymptotic) number of steps for computing error to minimize by the factor 1 = e.

Theorem 1

Equation (8) holds if and only if the following conditions are satisfied:

Condition 1

1^{T} ζ = 1^{T}

(11)

In equation (11), eigenvalue 1 is linked with leftward eigenvector of $ζ$ . The summation of the vector of agent values is conserved at individual iteration if it fulfills the subsequent condition $1^{T} x (t + 1) = 1^{T} x (t)$ for all t.

Condition 2

ζ 1 = 1

(12)

The rightward eigenvector of $ζ$ is connected with the eigenvalue 1, which is mentioned in equation (12). More specifically, we can describe this condition in such a way that 1 is meant to be a fixed entity associated with a linear iteration in equation (2).

Condition 3

ρ (ζ - \frac{11^{T}}{n}) < 1

(13)

In equation (13), it is specified that by uniting the primary two conditions (condition 1 and condition 2), all the eigenvalues will firmly be less than 1, other than the eigenvalue 1 that is accompanying with $ζ$ . Algebraically, matrix spectral radius is denoted as $ρ (\cdot)$ . Moreover

r_{asym} (ζ) = ρ (ζ - \frac{11^{T}}{n})

(14)

Proof of Theorem 1

If we suppose that the conditions in equations (11) and (12) are satisfied by $ζ$ , then

ζ^{t} - \frac{11^{T}}{n} = ζ^{t} (I - \frac{11^{T}}{n})

(15)

ζ^{t} - \frac{11^{T}}{n} = ζ^{t} {(I - \frac{11^{T}}{n})}^{t}

(16)

ζ^{t} - \frac{11^{T}}{n} = {(ζ (I - \frac{11^{T}}{n}))}^{t}

(17)

ζ^{t} - \frac{11^{T}}{n} = {(ζ - \frac{11^{T}}{n})}^{t}

(18)

ρ (ζ - \frac{11^{T}}{n}) < 1

(19)

where $I - (11^{T} / n)$ is a projection matrix. If applying on equation (13), it will lead the network to satisfy convergence.

Proposed algorithm

Elementary impression of a consensus algorithm is to enforce alike dynamics on the information states of every agent within the communication network. If the communication between the agents is continuous, reliable, and not time-invariant, then the agents can update their states’ value in a simpler way which can be modeled by a state differential equation. But if the communication between the agents in a system is not reliable and topology graph changes with each iteration in time domain, then it is considered as one of the hardest scenarios to achieve consensus.

In this section, a smart way is proposed for achieving consensus for the intelligent networks experiencing unreliable communication. Also, an overview of vigorous consensus algorithm is provided, in which an information state of each agent updates itself in every next iteration. The proposed technique of attaining consensus primarily focuses on achieving two major goals, one to minimize the number of iterations and second to fasten convergence rate as compared to the existing iterative methods.

The proposed algorithm can be mathematically expressed as

y_{i} (t + 1) = y_{i} (t) + \sum_{j \in N_{i}} ζ_{ij} (t) (y_{j} (t) - y_{i} (t))

(20)

where

ζ_{ij} (t) = {\begin{matrix} \frac{d_{i} (t) + d_{j} (t)}{2 d_{i} (t) d_{j} (t)} & i \neq j \\ 0 & otherwise \end{matrix}

(21)

where $d_{i}$ is the degree of agent $i$ (i.e. the number of neighbors of agent $i$ ).

This research indentures with the study of linear iteration equations distributed in nature of the specified underneath arrangement.²⁹

Proof of the algorithm

Let

Y (t) = [\begin{matrix} y_{1} (t) \\ y_{2} (t) \\ \dots \\ \dots \\ y_{n} (t) \end{matrix}], U (t) = [\begin{matrix} u_{1} (t) \\ u_{2} (t) \\ \dots \\ \dots \\ u_{n} (t) \end{matrix}]

We can write the following

Y (t + 1) = [\begin{matrix} y_{1} (t + 1) \\ y_{2} (t + 1) \\ \dots \\ \dots \\ y_{n} (t + 1) \end{matrix}]

As the main focus is on average consensus in a network, here it is important to draft a universal global equation to satisfy the average consensus in the form given below

Y (t + 1) = Y (t) + U (t)

(22)

By calculating the universal input vector, it can be written as

U (t) = ζ_{ij} (t) (A - D) Y (t)

(23)

$ζ_{ij} (t)$ is a weighting factor, and it will design and compute in such a way that ultimately it converge to an average value by substituting this value in $U (t)$ in equation (23). The design of the projected algorithm for $ζ_{ij} (t)$ will surely support to achieve the research objective uttered in $y_{i} (t + 1)$ in equation (20). In the proposed algorithm, few conditions are set to be mandatory. First, the initial conditions are set for all the agents; the first agent is assigned a value of 1 and 0 for the rest of the agents in the network. It can also be written as $x_{1} (0) = 1$ and $x_{i} (0) = 0, \forall i = 2, 3, 4, \dots, N$ . Second, graph $G$ must be connected to a connected graph and one spanning tree must exist to reach each agent in a network.

For unreliable communication, the weight matrix $ζ$ is not constant, and that is why we use notation $ζ_{ij} (t)$ in equation (23). Substituting equation (23) into equation (22), we obtain the following

Y (t + 1) = Y (t) + ζ_{ij} (t) (A - D) Y (t)

(24)

Using the definition of Laplacian matrix, that is, $L = D - A$ , we can further write the following

Y (t + 1) = Y (t) - L ζ_{ij} (t) Y (t)

(25)

Y (t + 1) = (I - L ζ_{ij} (t)) Y (t)

(26)

The linear iteration in equation (26) implies that for t = 0, 1, 2,…

Y (t) = (I - L ζ_{ij} (t)) Y (0)

(27)

lim_{t \to \infty} Y (t) = lim_{t \to \infty} (I - ζ_{ij} (t) L) Y (0)

(28)

Comparing equations (6) and (28)

lim_{t \to \infty} ζ (t) = lim_{t \to \infty} (I - ζ_{ij} (t) L)

(29)

From equation (8)

lim_{t \to \infty} ζ (t) = (\frac{1}{n}) 11^{T}

(30)

Equation (8) is one of the most important equation to guarantee the convergence of algorithm. Indulging convergence condition will guarantee that the proposed algorithm is perfect to achieve consensus. Putting equation (30) into equation (29), we get

lim_{t \to \infty} (I - ζ_{ij} (t) L) = (\frac{1}{n}) 11^{T}

(31)

As our main objective in this article is to calculate the total number of agents, we consider that the total number of agents is infinite, that is, $n \to \infty$ , then

lim_{t \to \infty} (I - ζ_{ij} (t) L) = 0

(32)

$L = D - A$ , where $D$ is the degree matrix and $A$ is the adjacency matrix. For $L$ , we select the single value, which is the harmonic mean of degree of agent $d_{i}$ and its neighboring node $d_{j}$ , $L = (2 d_{i} d_{j}) / (d_{i} + d_{j})$ . The final output of equation (32) becomes

ζ_{ij} (t) = \frac{d_{i} (t) + d_{j} (t)}{(2 d_{i} (t) d_{j} (t))}

(33)

The weight factor in equation (33) will guarantee convergence of algorithm toward the average values. This research considers the problems of unreliable communication and is more focused on computing the average value. The weighting factor in equation (33) will surely increase the efficiency to calculate the average, and it also deals with unreliable communication in a better way, even in low connectivity of the graph. It is capable of algebraic treatment and is not significantly affected by fluctuation of values.

Local degree weights

There are different approaches to designing a weight matrix $ζ$ . One simple technique is a local degree weight. In this technique, the largest degree out of two incident agents is assigned as weight on each edge³⁰

ζ_{ij} (t) = {\begin{matrix} \frac{1}{((max (d_{i} (t), d_{j} (t))))} & i \neq j \\ 0 & otherwise \end{matrix}

(34)

In case of local degree weights, it is necessary that each node knows the outdegrees of all its neighboring agents.

Metropolis hasting weights

Another simple approach similar to local degree weights for weight matrix is metropolis hasting weights, denoted as follows^32,33

ζ_{ij} (t) = {\begin{matrix} \frac{1}{((max (d_{i} (t), d_{j} (t)))) + 1} & i \neq j \\ 0 & otherwise \end{matrix}

(35)

In case of metropolis hasting weights, it is necessary that each agent knows the outdegrees of all its neighboring agents, but the set of neighbors varies with time.

Numerical examples and simulation results

This section presents numerical examples that illustrate the applicability of our proposed method for four different scenarios under unreliable communication. To show that the method can indeed provide interesting results in practical problems, four different parameters, that is, total number of iterations, central processing unit (CPU) time, asymptotic convergence factor, and convergence time, have been considered to compute the performance of the proposed algorithm with the existing protocols, and simulated results are presented for each scenario. The weighting factor is computed using the proposed theorem. This section also represents an error graph of the proposed method and other existing approaches. In all examples, the initial values are assigned to agents as $x_{n} (0) = 1$ and $x_{i} (0) = 0, \forall i = 1, 2, 3, \dots, n - 1$ . The error tolerance considered is $e = 10^{- 15}$ . Where NI is used for the number of total iterations.

where

e_{i} (t) = \sum_{j \in N_{i}} | x_{i} (t) - x_{j} (t) |, i = 1, 2, \dots, n

(36)

Case 1: a dynamically changing interaction topologies among agents

This case deals with the network under dynamic topology, which is changing continuously. The change in network topology will directly affect the degree of the agents. The adjacency matrix changes randomly and makes it complex in achieving group consensus which directly affects the performance of a system. The main objective is to tackle the main issues of cooperative control problems in unreliable communication and to propose a solution which is well suitable to overcome these problems. As the number of agents working in the system is unknown and selected randomly, therefore it is also difficult to count the total number of agents in the system. Both cases, that is, agent counting and consensus under unreliable communication, are the main issues in cooperative control problems. Solving the main issues will actually evaluate how much better the method is for the system. Four different parameters, that is, number of iterations, CPU time, asymptotic convergence factor, and convergence time, are used to compare the performance of the proposed method with other existing well-known methods. The graph of communication topology considered in case 1 is shown in Figure 2. Fifty agents are considered in this case and all agents have to develop consensus along value $0.02$ . In Figure 3, the error is plotted for the proposed method, metropolis, and local degree method, respectively. The number of iterations, CPU time, convergence time, and asymptotic convergence factor for all three methods are shown in Table 1. From the results of Figure 3, it is observed that the proposed method performs better than the known metropolis and local degree algorithms. The consensus graphs of the proposed method, metropolis method, and local degree method are shown in Figures 4 –6, respectively.

Figure 2.

Communication topology considered in case 1.

Figure 3.

Error plot graph generated for case 1.

Table 1.

Comparison results of case 1 for different parameters.

Methods	NI	CPU_Min	$ρ (W - \frac{11^{T}}{n})$	$τ_{asym}$
Proposed method	64	0.4361	0.5600	1.7251
Metropolis method	103	0.5813	0.6975	2.776
Local degree method	92	0.5095	0.6681	2.479

NI: number of total iteration.

Figure 4.

Agents approaching a consensus value using proposed algorithm in case 1.

Figure 5.

Agents approaching a consensus value using metropolis method in case 1.

Figure 6.

Agents approaching a consensus value using local degree method in case 1.

Case 2: addition of agents in the network with dynamically switching topology at any instant of time

The second case is the continuity of case 1. After having randomly selected some number of agents, now few more agents are to be added in the system. The continuity cases are one of the best ways to analyze the performances of iterative methods. In this scenario, 50 agents are selected in the start, and then after $t = 20 ms$ , seven more agents are added in the system. From $t = 0$ to $t = 20 ms$ , the consensus value is 1/50, but after $t = 20 ms$ the consensus value changes to 1/57. Changing the consensus value and adjacency matrix at the mid of the operation will create difficulties for agents to develop consensus on a common value. So this case can be considered the best if compared with the performance of different methods. An error graph is shown in Figure 7. The consensus graphs of the proposed method, metropolis method, and local degree method are shown in Figures 8 –10, respectively. The simulation results are shown in Table 2.

Figure 7.

Error plot graph generated for case 2.

Figure 8.

Agents approaching a consensus value using proposed algorithm in case 2.

Figure 9.

Agents approaching a consensus value using metropolis method in case 2.

Figure 10.

Agents approaching a consensus value using local degree method in case 2.

Table 2.

Comparison results of case 2 for different parameters.

Methods	NI	CPU_Min	$ρ (W - \frac{11^{T}}{n})$	$τ_{asym}$
Proposed method	79	0.6696	0.6264	2.1382
Metropolis method	106	0.8007	0.7057	2.8689
Local degree method	98	0.6953	0.6681	2.6524

NI: number of total iteration.

Case 3: removal of agents from the network with dynamically switching topology at any instant of time

This case is the second continuity scenario of case 1. In case 1, a random number of agents with continuously changing network topology were considered and consensus was developed. In this case, some agents are randomly selected, and after some instant of time few of the agents are removed from the system. This case is interesting and can be considered as a forced consensus case. At the start of operation, the agents have to develop consensus at some low value, that is, 1/50, but after sometime, that is, $t = 30 ms$ , some agents are removed from the system and now the agents are forced to develop consensus at some higher value, that is, 1/40. Now the number of iterations is unnecessarily increased instead of decreasing. Fifty agents are selected in the beginning in this case, and after $t = 30 ms$ , 10 agents are removed from the system. In Figure 11, the error is plotted for the proposed method, metropolis, and local degree method, respectively. Consensus graph for this case is shown in Figures 12 –14. The number of iterations, CPU time, asymptotic convergence factor, and convergence time for all three methods are shown in Table 3. From the results, it is observed that the proposed method takes the lead in all the performance parameters.

Figure 11.

Error plot graph generated for case 3.

Figure 12.

Agents approaching a consensus value using proposed algorithm in case 3.

Figure 13.

Agents approaching a consensus value using metropolis method in case 3.

Figure 14.

Agents approaching a consensus value using local degree method in case 3.

Table 3.

Comparison results of case 3 for different parameters.

Methods	NI	CPU_Min	$ρ (W - \frac{11^{T}}{n})$	$τ_{asym}$
Proposed method	76	0.2982	0.7662	3.7558
Metropolis method	97	0.3482	0.8117	4.7936
Local degree method	91	0.3105	0.8006	4.4971

NI: number of total iteration.

Case 4: a fixed topology with link failure and a reconnection with same agent after each iteration

In this case, the most common situation for unreliable communication is under consideration. Here, we consider that the link between agents fails, and then after some time the reconnection of link occurs. The link failure and reconnection continuously change the degree of agents. The adjacency matrix changes after each iteration, and the method performance disturbs continuously and it will become more difficult for agents to develop consensus on the required value. In all, 35 agents are considered in this case and we consider that there are chances that two to eight links of every agent break after each iteration and then a reconnection occurs. An error is plotted in Figure 15 for the proposed method, metropolis, and local degree method, respectively, to evaluate the performances of methods. Similarly, consensus graphs of the proposed method, metropolis method, and local degree method are shown in Figures 16 –18, respectively. Simulation results are presented in Table 4. From the simulation results, it is clear that the proposed method takes much less time and has faster convergence to consensus value as compared to metropolis and local degree methods.

Figure 15.

Error plot graph generated for case 4.

Figure 16.

Agents approaching a consensus value using proposed algorithm in case 4.

Figure 17.

Agents approaching a consensus value using metropolis method in case 4.

Figure 18.

Agents approaching a consensus value using local degree method in case 4.

Table 4.

Comparison results of case 4 for different parameters.

Methods	NI	CPU_Min	$ρ (W - \frac{11^{T}}{n})$	$τ_{asym}$
Proposed method	100	0.2683	0.6953	2.7522
Metropolis method	120	0.3155	0.7452	3.4006
Local degree method	108	0.2751	0.7213	3.0605

NI: number of total iteration.

Conclusion

In this article, we have presented a distributed average consensus algorithm in a network for intelligent multi-agent systems. The proposed algorithm produces a better result in terms of performance, number of iterations, CPU time, and computational cost and is capable of operability in large dynamic networks with unreliable communication. Simulation and computed results in the end of the article are themselves a clear evidence of better performance of the proposed technique.

This research considered the resource-constrained agents with limited source of power, which will affect the communication capabilities and communication range of the agents. In future, the scope of the proposed algorithm will be extended to investigate more complex multiple scenarios under asynchronous transmission for unreliable communication with communication delays to evaluate the performance of different parameters and to study its behavior. As the subject of this work, we aimed to develop and investigate the extension of our model and analysis by implementing an algorithm to incorporate communication delays for a multi-agent communication within a network. Such extensions will enable the study of other realistic networks, where clock timing of each agent differs from the other agents, but to achieve their final global objective they must reach the consensus value in less number of iterations.

Footnotes

Handling Editor: Salvatore Distefano

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

Ali Mustafa

References

Ren

Beard

Atkins

. Information consensus in multivehicle cooperative control. IEEE Contr Syst Mag 2007; 27: 71–82.

Pimenta

LCA

Pereira

GAS

Michael

et al . Swarm coordination based on smoothed particle hydrodynamics technique. IEEE T Robot 2013; 29(2): 383–399.

Beard

Lawton

Hadaegh

. A coordination architecture for spacecraft formation control. IEEE T Contr Syst T 2001; 9(6): 777–790.

Reynolds

. Flocks, herds, and schools: a distributed behavioral model. In: Proceedings of the 14th annual conference on computer graphics and interactive techniques (SIGGRAPH ’87), Anaheim, CA, vol. 21, 4 July 1987, pp.25–34. New York: ACM.

Cao

Ren

et al . An overview of recent progress in the study of distributed multi-agent coordination. IEEE T Ind Inform 2013; 9(1): 427–438.

Zhang

J-F

. Distributed parameter estimation over unreliable networks with Markovian switching topologies. IEEE T Automat Contr 2012; 57(10): 2545–2560.

Vicsek

Czirók

Ben-Jacob

et al . Novel type of phase transition in a system of self-driven particles. Phys Rev Lett 1995; 75(6): 1226–1229.

Saber

Murray

. Consensus problems in networks of agents with switching topology and time-delays. IEEE T Automat Contr 2004; 49(9): 1520–1533.

Jadbabaie

Lin

Morse

. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE T Automat Contr 2003; 48(6): 988–1001.

10.

Fan

Liu

Feng

et al . Self-triggered consensus for multi-agent systems with Zeno-free triggers. IEEE T Automat Contr 2015; 60(10): 2779–2784.

11.

Fan

Liu

Feng

et al . Virtual neighbor based connectivity preserving of multi-agent systems with bounded control inputs in the presence of unreliable communication links. Automatica 2013; 49(5): 1261–1267.

12.

Zhao

Yuan

. An LMI approach to consensus in second-order multi-agent systems. Int J Control Autom 2011; 9(6): 1111–1115.

13.

Cattivelli

Lopes

Sayed

. Diffusion recursive least-squares for distributed estimation over adaptive networks. IEEE T Signal Proces 2008; 56(5): 1865–1877.

14.

Abreu

Botelho

Cavallaro

et al . Video-based multi-agent traffic surveillance system. IEEE Int Veh Sym 2000; 4: 457–462.

15.

Kokiopoulou

Frossard

. Polynomial ﬁltering for fast convergence in distributed consensus. IEEE T Signal Proces 2009; 57: 342–354.

16.

Evers

Kiss

Kowalczyk

et al . Node counting in wireless ad-hoc networks. In: Proceedings of the 79th European study group mathematics with industry, Amsterdam, 24–28 January 2011, pp.49–73. Technische Universiteit Eindhoven, University of Technology.

17.

Liu

Cheng

Tan

et al . Distributed exponential finite-time coordination of multi-agent systems: containment control and consensus. Int J Control 2015; 88(2): 237–247.

18.

Shi

Teo

. Cooperative enclosing control for multiple moving targets by a group of agents. Int J Control 2015; 88(1): 80–89.

19.

Kar

Moura

Ramanan

. Distributed parameter estimation in sensor networks: nonlinear observation models and imperfect communication. IEEE T Inform Theory 2012; 58: 3575–3605.

20.

Perkins

Royer

. Ad-hoc on-demand distance vector routing. In: Proceedings of the second IEEE workshop on mobile computing systems and applications, New Orleans, LA, 25–26 February 1999, pp.90–100. New York: IEEE.

21.

Rehan

Bansal

. Performance comparison among different evolutionary algorithms in terms of node count reduction in BDDs. Int J VLSI Embed Syst 2013; 4: 491–496.

22.

Meng

Chen

. Event based agreement protocols for multi-agent networks. Automatica 2013; 49(7): 2125–2132.

23.

Liu

Lin

Chen

. Graph-theoretic characterisations of structural controllability for multi-agent system with switching topology. Int J Control 2013; 86(2): 222–231.

24.

Feng

Zhang

. Group consensus control for double-integrator dynamic multiagent systems with fixed communication topology. Int J Robust Nonlin 2014; 24(3): 532–547.

25.

Mustafa

Ahmed

Islam

et al . An efficient agent scheming in distributed time varying networks. In: Bi

Kapoor

Bhatia

(eds) Proceedings of SAI intelligent systems conference (IntelliSys) 2016. Cham: Springer, 2016, pp.804–809.

26.

Ren

Beard

Atkins

. A survey of consensus problems in multi-agent coordination. In: Proceedings of the American control conference, Portland, OR, 8–10 June 2005, pp.1859–1864. New York: IEEE.

27.

Ren

Beard

. Consensus seeking in multiagent systems under dynamically changing interaction topologies. IEEE T Automat Contr 2005; 50(5): 655–661.

28.

Xiao

Wang

. State consensus for multi-agent systems with switching topologies and time-varying delays. Int J Control 2006; 79(10): 1277–1284.

29.

Merris

. Laplacian matrices of graphs: a survey. Linear Algebra Appl 1994; 197–198: 143–176.

30.

Xiao

Boyd

. Fast linear iterations for distributed averaging. IEEE Decis Contr P 2003; 5: 4997–5002.

31.

Kar

Moura

. Sensor networks with random links: topology design for distributed consensus. IEEE T Signal Proces 2008; 56: 3315–3326.

32.

Hastings

. Monte Carlo sampling methods using Markov chains and their applications. Biometrika 1970; 57: 97–109.

33.

Metropolis

Rosenbluth

et al . Equation of state calculations by fast computing machines. J Chem Phys 1953; 21: 1087–1092.