Delay and Packet-Drop Tolerant Multi-Stage Distributed Average Tracking in Mean Square

For a multi-agent plant operating through a network of devices, the capability of distributed average tracking (DAT), measured by the tracking error between each agent’s state and the average of a set of reference signals via a distributed protocol, depends on the agent dynamics, the network topology, the class of control algorithms, as well as the reference signals. It has been recognized that when the agent dynamics, the reference signals, and the network topology are given, and the control algorithm has been designed, the reference noise, input delay, and network transmission failures will also lead to degrading control performance. This paper considers the DAT problem for discrete-time multi-agent systems, in which both the agents’ states and the control inputs are updated in a discrete-time manner. The effect of linear time-invariant agent dynamics, noise-corrupted reference signals, and unreliable transmission networks subject to random packet-drop are investigated. Each agent’s local input will be implemented via a multi-stage algorithm. The objective is to investigate what may affect the tracking error in this setting, and whether it is possible to achieve practical DAT, i.e., the stationary-state tracking error can be made arbitrarily small, and how.

The capability of distributed average tracking is a significant attribute of multi-agent systems, which has proven useful for distributed sensor fusion [2, 3, 4], distributed optimization [5], and multi-agent coordination [6, 7, 8, 9, 10]. For single-integrator plants, a consensus algorithm and a proportional-integral algorithm are investigated respectively in [11] and [12], wherein both algorithms could track the average of stationary references with zero tracking errors. The proportional-integral control offers additional robustness against initialization errors. Meanwhile, more advanced design methods have been exploited to track time-varying references [13], sinusoid references with unknown frequencies [14], and arbitrary references with bounded derivatives [15]. Recently, the study on DAT has been expanded to handle complicated agent dynamics, e.g., double-integrator dynamics [16, 17], generic linear dynamics [8, 18], and nonlinear dynamics [19, 20], with performance analysis [21, 22, 23], privacy requirements [24], and for balanced directed networks [25, 26]. By introducing a “damping” factor, the algorithm of [27] ensures DAT with small errors while being robust against initialization errors. Inspired by the proportional algorithm, a multi-stage DAT algorithm was lately proposed in [28] based upon a cascade of DAT filters, which is capable of achieving DAT with bounded errors. For more details on DAT, a recent tutorial is available [29].

In spite of significant progress on DAT, the study on practical issues, such as delay and noise, is only to emerge [30]. Indeed, it is generally recognized, and intuitively clear, that the convergence of DAT algorithms can be constrained by transmission failures, input delays, as well as reference noise, which all likely result in negative effect on the convergence of the closed-loop system. For linear systems with small input delays, the control algorithm without delay compensation might still work, since linear systems possess a certain robustness margin to small delays [31]; yet the convergence will generically fail for relatively large delays. In practice, a reference signal might represent a target or a dynamic process, for which the measurement is inevitably corrupted by random noise. However, the effect of reference noise has been commonly ignored. Apart from that, since the communication network is shared by all agents, packet-drops ubiquitously exist, and therefore should be fully addressed, particularly when the data transmission rate is large.

This paper proposes a practical DAT design which can concurrently tolerate input delays, random packet-drops, and reference noise. For this purpose, a blend of the techniques from multi-stage consensus filtering, predictive control, and Kalman filtering is employed. This work extends the existing work to a more realistic setting where the idealized assumptions, which are seldom possible in practice, are removed. To the best of the authors’ knowledge, this work presents the first multi-stage design that takes reference noise, input delays, packet-drops all into consideration, which are perceived as main sources of control design difficulty for multi-agent systems. With this defining feature, the analysis reveals that an expected network topology plays a central role in ensuring the convergence of the proposed DAT algorithm, wherein the allowable values of the algorithm parameters rely upon the maximal degree of the expected network, while the convergence speed depends on the second smallest eigenvalue of the same network’s topology. It should be noted that due to the additional algorithm components and their inherent couplings, the convergence analysis is significantly more challenging than the existing ones.

The rest of this paper is organized as follows. In Section 2, notation and mathematical preliminaries are presented. In Section 3, the problem is defined. In Section 4, the DAT algorithm is designed with the aid of Kalman filtering, predictive control, and multi-stage consensus filtering. The performance of the proposed algorithm is analyzed in Section 5. Section 6 presents numerical examples to verify the theoretical results. Finally, Section 7 concludes the paper.

Consider a network of $N\in\mathbb{Z}^{+}$ agents, labeled from $1$ to $N$. Agent $i$, $i=1,\dots,N$, follows the following discrete-time multi-stage dynamics:

where $x_{i}^{p}(k)$ is the state of agent $i$ at stage $p$, $u_{i}^{p}(k-\tau)$ is the input of agent $i$ at stage $p$ subject to an input delay $\tau$, and $k\in\mathbb{Z}^{+}$ is the time variable. A graph $\mathcal{G}\triangleq(\mathcal{V},\mathcal{E})$ is used to describe the information flows among the agents, where $\mathcal{V}\triangleq\{1,\dots,N\}$ is the node set and $\mathcal{E}\triangleq\{(i,j)\,|\,\text{node $i$ can share information with $j$},\,i,j=1,\dots,N\}$ is the edge set. Throughout this paper, it is assumed that graph $\mathcal{G}$ is connected.

Because information is exchanged through the network, there usually exist packet-drops particularly when the data transmission rate is high. It is common and reasonable to delineate packet-drops by independent Bernoulli processes. Specifically, let $\theta_{ij}$ be a random variable indicating whether the transmission between two neighboring agents $i$ and $j$ is successful, i.e.,

where $0\leq p_{ij}<1$ is the packet-drop rate. For non-neighboring agents, $\theta_{ij}=0$ with probability $1$. Due to the random packet-drops, the de facto information exchange network, denoted by $\widetilde{\mathcal{G}}\triangleq(\mathcal{V},\widetilde{\mathcal{E}})$, is by nature a random network. At each time instant, $\widetilde{\mathcal{G}}$ takes a value from the set $\{\mathcal{G}_{1},\dots,\mathcal{G}_{s}\}$, $s=2^{|\mathcal{E}|}$, with the probability

where $m=1,\dots,s$ and and $[\cdot]_{m}$ means that it takes values from the graph indexed by $m$.

Each agent has a reference signal $r_{i}$, which is governed by

where $v_{i}(k)\in\mathbb{R}$ is the input, $z_{i}(k)\in\mathbb{R}$ is the measurement, and $h_{i}\in\mathbb{R}^{+}$ is the measurement gain. The process noise $w_{i}(k)\in\mathbb{R}$ and measurement noise $\vartheta_{i}(k)\in\mathbb{R}$ follow independent normal probability distributions, i.e.,

where $\phi_{i}(k)\triangleq\mathbb{E}[w_{i}(k)^{2}]$ is the variance of the process noise, and $\psi_{i}(k)\triangleq\mathbb{E}[\vartheta_{i}(k)^{2}]$ is the variance of the measurement noise. The following assumption is made on the reference signals.

The primary objective of this paper is to design distributed input sequence for the system (3) such that all agents can track the average of the $N$ noisy reference inputs in the sense that, for all $i=1,2,\dots,N$,

where $\delta$ is a pre-desired constant, which can be arbitrarily small.

In this section, the control input sequence is designed for the multi-stage system (3) to track the average signal of the noisy references (4), which gives the following DAT algorithm:

where $\hat{x}_{i}^{p}(k|k-\tau)$ and $\hat{r}_{i}(k|k-\tau)$ are respectively the predicted states of agent $i$ and reference $i$ at time instant $k$ using the measurement information up to time instant $k-\tau$, and $\epsilon>0$ and $\alpha>0$ are two gain parameters to be designed.

The agent state predictor is given by

where $k_{x}>0$ is the predictor gain, while the states of agent $i$ from $k-\tau+2$ to $k$ are predicted by

Because the reference signals are subject to both input delay and noise, its design needs a combination of the predictive control and Kalman filtering techniques. Specifically, the following predictor for the reference signals is designed:

where $k_{r}>0$ is a predictor gain and $\hat{r}_{i}(k)$ is the estimate obtained via the Kalman filter

in which $k_{i}(k)\in\mathbb{R}$ is the Kalman gain, $\hat{r}_{i}^{-}(k)\in\mathbb{R}$ and $\hat{r}_{i}(k)\in\mathbb{R}$ are, respectively, the priori and posteriori estimates of $r_{i}(k)$, $p_{i}^{-}(k)\triangleq\mathbb{E}\left[(r_{i}(k)-\hat{r}_{i}^{-}(k))^{2}\right]$ is the mean-squared priori estimate error, and $p_{i}(k)\triangleq\mathbb{E}\left[(r_{i}(k)-\hat{r}_{i}(k))^{2}\right]$ is the mean-squared posteriori estimate error. The initial states of the Kalman filter, $\hat{r}_{i}(0)$ and $p_{i}(0)\geq 0$, are chosen randomly.

The estimate process alluded to above is delineated in Fig. 1. As shown, the Kalman filter performs two operations: time update and measurement update. The time update equations are (9a) and (9b), while the measurement update equations are (9c)–(9e). The time update equations “predict” the state and estimate errors at time $k+1$ from those at time $k$, while the measurement update equations adjust the priori estimate by using the measurement $z_{i}(k)$ according to the Kalman gain $k_{i}(k)$, which is obtained by minimizing $p_{i}(k)$.

Substituting the input (4) into system (3) leads to the closed-loop system

which can be written in a vector format as

where

Here, $\widetilde{L}$ is a stochastic Laplacian matrix, changing within the possible set $\{L_{1},L_{2},\dots,L_{s}\}$, where $L_{m}=\left[l_{ij}\right]_{m}$ is the Laplacian matrix associated with $\mathcal{G}_{m}$, i.e.,

For future use, let

The following gives a useful result regarding the expecation of the Laplacian matrix $\tilde{L}$. The result will be employed in the convergence analysis in the next section.

The advantages of the multi-stage DAT system (10) are as follows: firstly, it does not involve integral control actions or input derivatives, thus exhibits robustness to initialization errors; secondly, the proposed multi-state scheme enables the possibility of making a trade-off among the communication/computation cost (i.e., the number of stages), the tracking error and the convergence time; thirdly, the proposed scheme takes input delay, packet-drops, and reference noise into consideration, making it more feasible for practical applications.

In this section, the convergence of the proposed algorithm embedded in system (10) is analyzed. It is first to show that the Kalman filter (9) is stable.

In what follows, the performance of the multi-stage DAT system (10) is analyzed. Let

where $r_{i}^{*}\triangleq\lim_{k\to\infty}\mathbb{E}[r_{i}(k)],i={1,\dots,N}$. Note that $\boldsymbol{r}^{*}$ is well defined due to Assumption 1. The following result characterizes agents’ stationary states in terms of $\boldsymbol{r}^{*}$.