{'fraction_non_alphanumeric': 0.050071758890129166, 'fraction_numerical': 0.017541062031573913, 'mean_word_length': 4.200663349917082, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Averaging Consensus Algorithm and Its Stopping Rule over Noisy Undirected Networks of MIMO Linear Symmetric Agents

A stochastic averaging consensus algorithm is considered for a multi-agent system over a noisy undirected network with multi-input/multi-output (MIMO) linear symmetric agents. The convergence of the algorithm is investigated, which gives an explicit relation between the number of iterations and the closeness of the agreement, i.e., a stopping rule. The result is illustrated through a numerical example.


Introduction
An averaging consensus is a basic distributed algorithm which works over a multi-agent networked systems and gives the average value of initial states of the agents. In this algorithm, each agent communicates only with its neighbors and exchanges information iteratively. Since communication noise is unavoidable and usually interferes with the information exchange, several stochastic consensus algorithms have been proposed under noisy environment [1,2]. Stopping rules, which provide a relation between the explicit number of iterations and the quality of the consensus, have also been established for stochastic noisy environment, where the agents are assumed to be first order systems [3] or higher order systems [4,5]. The latter employs a linear symmetric system [6].
Most multi-agent algorithms are considered, where each agent is a single-input/single-output (SISO) subsystem. In order to represent more complex model, multi-input/multi-output (MIMO) agents should be considered. In fact, the consensusability of MIMO multi-agent systems is studied for noise free case [7].
In this paper, we tackle a multi-agent system over noisy undirected networks, where each agent is a MIMO linear symmetric system. We give a communication gain to achieve the averaging consensus and the stop-ping rule under an appropriate assumption for the symmetric system. These results include the existing ones [3] and [4] as special cases if the agents are first order systems or SISO symmetric systems.

Multi-Agent Systems
Let us consider N linear symmetric agents having the same dynamics where and k ∈ N. We assume that there exists a positive definite matrix R = R ⊤ ∈ R m×m such that 0 < R ≤ I m and 0 ≤ A − κBRC < I n for all κ ∈ (0, 1], where I m ∈ R m×m is the identity matrix. That is, each agent can be stabilized by an arbitrary low positive-definite gain output feedback. This assumption is equivalent to three inequalities for some η ∈ (0, 1]. This η will be used later. We remark that the MIMO linear symmetric agent includes SISO one investigated in [4] when B and C are vectors and R = 1. It can be also the standard first order agent when A = B = C = R = 1 with η = 1. For this set of the symmetric agents, we introduce interactions Proceedings of the 49th ISCIE International Symposium on Stochastic Systems Theory and Its Applications Hiroshima, Nov. [3][4]2017 where r(k) ∈ R is the communication gain to be determined later, z ij (k) ∈ R m is the information which agent i receives from the agent j (i ̸ = j), and and Cov[a] denote the expectation and the covariance of a random variable a and V = V ⊤ > 0. We assume that the random variables are i.i.d. with respect to i, j, and k. Furthermore, N i ⊆ V \ {i} is the set of agents that can communicate with the agent i, which introduces a graph. We assume that the graph is undirected and connected.
The averaging consensus problem of the multi-agent system (1) with the noisy interactions (3) is to achieve for all ϵ > 0, where P is the probability measure on the noise sequence. The goal of this paper is to give a consensus algorithm and its stopping rule for this noisy network of the MIMO linear symmetric agents.

Convergence Analysis
Let us define the graph Laplacian L whose {i, j}-th Since the given graph is undirected and connected, L = L ⊤ , L1 N = 0, and rank L = N − 1, where 1 N is the N -dimensional vector whose elements are all 1. In fact, L has only real eigenvalues which are defined as 0 = λ 1 < λ 2 ≤ · · · ≤ λ N . The multi-agent system is then represented as or 0 otherwise, and ⊗ denotes the Kronecker product. Employing a state coordinate transformation Then we see that which implies that ∥x(k)∥ = ∥ξ 1 (k)∥. That is, we can consider the convergence ofx(k) as that of ξ 1 (k).
The following lemma is the key tool which will be used in the proof of the main result.

Lemma 1.
For the undirected connected graph, its graph Laplacian L satisfies where ∥ · ∥ denotes the spectral norm.

Now, let us select the communication gain as
where k 0 ∈ N. Then we have the the main result.
Note that this result includes the SISO case [4]. In fact, since the noise w ij (k) is a scalar in the SISO case, V becomes a scalar v 2 . Thus the theorem derived in [4] can basically be obtained from Theorem 1. Furthermore, when each agent is the standard first order subsystem, we see that Tr(Cov[x(k)]) = Var[x(k)]. Thus the theorem derived in [3] can also be derived from the second part of Theorem 1.

Numerical Example
Let us consider a multi-agent system with N = 4. We set m = 2, n = 5, and where the assumption (2) holds with 0 < η ≤ 0.164. The initial state was chosen as We see the graph Laplacian as  Based on Theorem 1, the number of iterations k f for (4) is 16, 094. Since ∥x(1)∥ is 25.000, the theorem says P (∥x(16, 094)∥ ≤ 3.000) ≥ 0.8.
We executed 1, 000 times with different noise sequences. Figs. 1, 2, and 3 show that the behavior of the state x(k), averagex(k), and the deviationx(k) at a certain trial respectively. Then, the worst value of ∥x(16, 094)∥ in the trials was 0.122, i.e., the inequality ∥x(16, 094)∥ ≤ 3.000 is always satisfied for all trials. According to Fig. 2, each element of the average moves around each element of the above vector when the number of iterations k is sufficiently large. These results are consistent with Theorem 1.

Concluding Remarks
We have proposed the averaging consensus algorithm and stopping rule for the multi-agent system over noisy undirected networks of MIMO multi-agent systems. The theorem establishes the relation between the closeness of the agreement and the number of iterations explicitly with a probabilistic guarantee, which gives a stopping rule for the averaging consensus algorithm.