Search

One of the intensely studied concepts of network robustness is $r$-robustness, which is a network topology property quantified by an integer $r$. It is required by mean subsequence reduced (MSR) algorithms and their variants to achieve resilient consensus. However, determining $r$-robustness is intractable for large networks. In this paper, we propose a sample-based algorithm to approximately test $r$-robustness of a digraph with $n$ vertices and $m$ edges. For a digraph with a moderate assumption on the minimum in-degree, and an error parameter $0<\epsilon\leq 1$, the proposed algorithm distinguishes $(r+\epsilon n)$-robust graphs from graphs which are not $r$-robust with probability $(1-\delta)$. Our algorithm runs in $\exp(O((\ln{\frac{1}{\epsilon\delta}})/\epsilon^2))\cdot m$ time. The running time is linear in the number of edges if $\epsilon$ is a constant., Comment: 8 pages, 3 figures

As one of the most fundamental stochastic optimization algorithms, stochastic gradient descent (SGD) has been intensively developed and extensively applied in machine learning in the past decade. There have been some modified SGD-type algorithms, which outperform the SGD in many competitions and applications in terms of convergence rate and accuracy, such as momentum-based SGD (mSGD) and adaptive gradient algorithm (AdaGrad). Despite these empirical successes, the theoretical properties of these algorithms have not been well established due to technical difficulties. With this motivation, we focus on convergence analysis of mSGD and AdaGrad for any smooth (possibly non-convex) loss functions in stochastic optimization. First, we prove that the iterates of mSGD are asymptotically convergent to a connected set of stationary points with probability one, which is more general than existing works on subsequence convergence or convergence of time averages. Moreover, we prove that the loss function of mSGD decays at a certain rate faster than that of SGD. In addition, we prove the iterates of AdaGrad are asymptotically convergent to a connected set of stationary points with probability one. Also, this result extends the results from the literature on subsequence convergence and the convergence of time averages. Despite the generality of the above convergence results, we have relaxed some assumptions of gradient noises, convexity of loss functions, as well as boundedness of iterates.

The paper studies identification of linear systems with multiplicative noise from multiple-trajectory data. An algorithm based on the least-squares method and multiple-trajectory data is proposed for joint estimation of the nominal system matrices and the covariance matrix of the multiplicative noise. The algorithm does not need prior knowledge of the noise or stability of the system, but requires only independent inputs with pre-designed first and second moments and relatively small trajectory length. The study of identifiability of the noise covariance matrix shows that there exists an equivalent class of matrices that generate the same second-moment dynamic of system states. It is demonstrated how to obtain the equivalent class based on estimates of the noise covariance. Asymptotic consistency of the algorithm is verified under sufficiently exciting inputs and system controllability conditions. Non-asymptotic performance of the algorithm is also analyzed under the assumption that the system is bounded. The analysis provides high-probability bounds vanishing as the number of trajectories grows to infinity. The results are illustrated by numerical simulations.

This paper proposes a method to navigate a mobile robot by estimating its state over a number of distributed sensor networks (DSNs) such that it can successively accomplish a sequence of tasks, i.e., its state enters each targeted set and stays inside no less than the desired time, under a resource-aware, time-efficient, and computation- and communication-constrained setting.We propose a new robot state estimation and navigation architecture, which integrates an event-triggered task-switching feedback controller for the robot and a two-time-scale distributed state estimator for each sensor. The architecture has three major advantages over existing approaches: First, in each task only one DSN is active for sensing and estimating the robot state, and for different tasks the robot can switch the active DSN by taking resource saving and system performance into account; Second, the robot only needs to communicate with one active sensor at each time to obtain its state information from the active DSN; Third, no online optimization is required. With the controller, the robot is able to accomplish a task by following a reference trajectory and switch to the next task when an event-triggered condition is fulfilled. With the estimator, each active sensor is able to estimate the robot state. Under proper conditions, we prove that the state estimation error and the trajectory tracking deviation are upper bounded by two time-varying sequences respectively, which play an essential role in the event-triggered condition. Furthermore, we find a sufficient condition for accomplishing a task and provide an upper bound of running time for the task. Numerical simulations of an indoor robot's localization and navigation are provided to validate the proposed architecture.

We study distributed estimation of a high-dimensional static parameter vector through a group of sensors whose communication network is modeled by a fixed directed graph. Different from existing time-triggered communication schemes, an event-triggered asynchronous scheme is investigated in order to reduce communication while preserving estimation convergence. A distributed estimation algorithm with a single step size is first proposed based on an event-triggered communication scheme with a time-dependent decaying threshold. With the event-triggered scheme, each sensor sends its estimate to neighbor sensors only when the difference between the current estimate and the last sent-out estimate is larger than the triggering threshold. We prove that the proposed algorithm has mean-square and almost-sure convergence respectively, under an integrated condition of sensor network topology and sensor measurement matrices. The condition is satisfied if the topology is a balanced digraph containing a spanning tree and the system is collectively observable. Moreover, we provide estimates for the convergence rates, which are related to the step size as well as the triggering threshold. Furthermore, as an essential metric of sensor communication intensity in the event-triggered distributed algorithms, the communication rate is proved to decay to zero with a certain speed almost surely as time goes to infinity. We show that given the step size, adjusting the decay speed of the triggering threshold can lead to a tradeoff between the convergence rate of the estimation error and the decay speed of the communication rate. Specifically, increasing the decay speed of the threshold would make the communication rate decay faster, but reduce the convergence rate of the estimation error. Numerical simulations are provided to illustrate the developed results.

We study how to jointly recover the community structure and estimate the interaction probabilities of gossip opinion dynamics. In this process, agents randomly interact pairwise, and there are stubborn agents never changing their states. Such a model illustrates how disagreement and opinion fluctuation arise in a social network. It is assumed that each agent is assigned with one of two community labels, and the agents interact with probabilities depending on their labels. The considered problem is to jointly recover the community labels of the agents and estimate interaction probabilities between the agents, based on a single trajectory of the model. We first study stability and limit theorems of the model, and then propose a joint recovery and estimation algorithm based on a trajectory. It is verified that the community recovery can be achieved in finite time, and the interaction estimator converges almost surely. We derive a sample-complexity result for the recovery, and analyze the estimator's convergence rate. Simulations are presented for illustration of the performance of the proposed algorithm.

In order to protect smart distribution grids from intrusions, it is important to understand possible risks and impacts of attacks. We study the worst-case attack strategy of a power injection attack against the physical layer of a smart distribution grid with a high penetration of photovoltaic resources. We derive both the worst attack signal and worst attack location: The worst attack signal is a step function which switches its sign at the final stage, and the worst attack location is the node with the largest impedance to the grid substation. Numerical examples on a European benchmark model verify the developed results. Finally, both theoretical and numerical results are used to discuss feasible defense strategies against power injection attacks., Comment: 7 pages

The set-based estimation has gained a lot of attention due to its ability to guarantee state enclosures for safety-critical systems. However, collecting measurements from distributed sensors often requires outsourcing the set-based operations to an aggregator node, raising many privacy concerns. To address this problem, we present set-based estimation protocols using partially homomorphic encryption that preserve the privacy of the measurements and sets bounding the estimates. We consider a linear discrete-time dynamical system with bounded modeling and measurement uncertainties. Sets are represented by zonotopes and constrained zonotopes as they can compactly represent high-dimensional sets and are closed under linear maps and Minkowski addition. By selectively encrypting parameters of the set representations, we establish the notion of encrypted sets and intersect sets in the encrypted domain, which enables guaranteed state estimation while ensuring privacy. In particular, we show that our protocols achieve computational privacy using the cryptographic notion of computational indistinguishability. We demonstrate the efficiency of our approach by localizing a real mobile quadcopter using ultra-wideband wireless devices., Comment: This paper is accepted at the European Journal of Control

We study how to design a secure observer-based distributed controller such that a group of vehicles can achieve accurate state estimates and formation control even if the measurements of a subset of vehicle sensors are compromised by a malicious attacker. We propose an architecture consisting of a resilient observer, an attack detector, and an observer-based distributed controller. The distributed detector is able to update three sets of vehicle sensors: the ones surely under attack, surely attack-free, and suspected to be under attack. The adaptive observer saturates the measurement innovation through a preset static or time-varying threshold, such that the potentially compromised measurements have limited influence on the estimation. Essential properties of the proposed architecture include: 1) The detector is fault-free, and the attacked and attack-free vehicle sensors can be identified in finite time; 2) The observer guarantees both real-time error bounds and asymptotic error bounds, with tighter bounds when more attacked or attack-free vehicle sensors are identified by the detector; 3) The distributed controller ensures closed-loop stability. The effectiveness of the proposed methods is evaluated through simulations by an application to vehicle platooning.

We study how to secure distributed filters for linear time-invariant systems with bounded noise under false-data injection attacks. A malicious attacker is able to arbitrarily manipulate the observations for a time-varying and unknown subset of the sensors. We first propose a recursive distributed filter consisting of two steps at each update. The first step employs a saturation-like scheme, which gives a small gain if the innovation is large corresponding to a potential attack. The second step is a consensus operation of state estimates among neighboring sensors. We prove the estimation error is upper bounded if the filter parameters satisfy a condition. We further analyze the feasibility of the condition and connect it to sparse observability in the centralized case. When the attacked sensor set is known to be time-invariant, the secured filter is modified by adding an online local attack detector. The detector is able to identify the attacked sensors whose observation innovations are larger than the detection thresholds. Also, with more attacked sensors being detected, the thresholds will adaptively adjust to reduce the space of the stealthy attack signals. The resilience of the secured filter with detection is verified by an explicit relationship between the upper bound of the estimation error and the number of detected attacked sensors. Moreover, for the noise-free case, we prove that the state estimate of each sensor asymptotically converges to the system state under certain conditions. Numerical simulations are provided to illustrate the developed results.

We consider a community detection problem for gossip dynamics with stubborn agents in this paper. It is assumed that the communication probability matrix for agent pairs has a block structure. More specifically, we assume that the network can be divided into two communities, and the communication probability of two agents depends on whether they are in the same community. Stability of the model is investigated, and expectation of stationary distribution is characterized, indicating under the block assumption, the stationary behaviors of agents in the same community are similar. It is also shown that agents in different communities display distinct behaviors if and only if state averages of stubborn agents in different communities are not identical. A community detection algorithm is then proposed to recover community structure and to estimate communication probability parameters. It is verified that the community detection part converges in finite time, and the parameter estimation part converges almost surely. Simulations are given to illustrate algorithm performance.

In this paper, we study how to secure the platooning of autonomous vehicles when an unknown vehicle is under attack and bounded system uncertainties exist. For the attacked vehicle, its position and speed measurements from GPS can be manipulated arbitrarily by a malicious attacker. First, to find out which vehicle is under attack, two detectors are proposed by using the relative measurements (by camera or radar) and the local innovation obtained through measurements from neighboring vehicles. Then, based on the results of the detectors, we design a local state observer for each vehicle by applying a saturation method to the measurement innovation. Moreover, based on the neighbor state estimates provided by the observer, a distributed controller is proposed to achieve the consensus in vehicle speed and keep fixed desired distance between two neighboring vehicles. The estimation error by the observer and the platooning error by the controller are shown to be asymptotically upper bounded under certain conditions. The effectiveness of the proposed methods is also evaluated in numerical simulations.

The study of multiplicative noise models has a long history in control theory but is re-emerging in the context of complex networked systems and systems with learning-based control. We consider linear system identification with multiplicative noise from multiple state-input trajectory data. We propose exploratory input signals along with a least-squares algorithm to simultaneously estimate nominal system parameters and multiplicative noise covariance matrices. Identifiability of the covariance structure and asymptotic consistency of the least-squares estimator are demonstrated by analyzing first and second moment dynamics of the system. The results are illustrated by numerical simulations.

This paper studies the problem of recursively estimating the weighted adjacency matrix of a network out of a temporal sequence of binary-valued observations. The observation sequence is generated from nonlinear networked dynamics in which agents exchange and display binary outputs. Sufficient conditions are given to ensure stability of the observation sequence and identifiability of the system parameters. It is shown that stability and identifiability can be guaranteed under the assumption of independent standard Gaussian disturbances. Via a maximum likelihood approach, the estimation problem is transformed into an optimization problem, and it is verified that its solution is the true parameter vector under the independent standard Gaussian assumption. A recursive algorithm for the estimation problem is then proposed based on stochastic approximation techniques. Its strong consistency is established and convergence rate analyzed. Finally, numerical simulations are conducted to illustrate the results and to show that the proposed algorithm is insensitive to small unmodeled factors.

We study distributed filtering for a class of uncertain systems over corrupted communication channels. We propose a distributed robust Kalman filter with stochastic gains, through which upper bounds of the conditional mean square estimation errors are calculated online. We present a robust collective observability condition, under which the mean square error of the distributed filter is proved to be uniformly upper bounded if the network is strongly connected. For better performance, we modify the filer by introducing a switching fusion scheme based on a sliding window. It provides a smaller upper bound of the conditional mean square error. Numerical simulations are provided to validate the theoretical results and show that the filter scales to large networks.

In this paper, we consider a secure distributed filtering problem for linear time-invariant systems with bounded noises and unstable dynamics under compromised observations. A malicious attacker is able to compromise a subset of the agents and manipulate the observations arbitrarily. We first propose a recursive distributed filter consisting of two parts at each time. The first part employs a saturation-like scheme, which gives a small gain if the innovation is too large. The second part is a consensus operation of state estimates among neighboring agents. A sufficient condition is then established for the boundedness of estimation error, which is with respect to network topology, system structure, and the maximal compromised agent subset. We further provide an equivalent statement, which connects to 2s-sparse observability in the centralized framework in certain scenarios, such that the sufficient condition is feasible. Numerical simulations are finally provided to illustrate the developed results.

This paper studies the estimation of network weights for a class of systems with binary-valued observations. In these systems only quantized observations are available for the network estimation. Furthermore, system states are coupled with observations, and the quantization parts are unknown inherent components, which hinder the design of inputs and quantizers. To fulfill the estimation, we propose a recursive algorithm based on stochastic approximation techniques. More precisely, to deal with the temporal dependency of observations and achieve the recursive estimation of network weights, a deterministic objective function is constructed based on the likelihood function by extending the dimension of observations and applying ergodic properties of Markov chains. It is shown that this function is strictly concave and has unique maximum identical to the true parameter vector. Finally, the strong consistency of the algorithm is established. Our recursive algorithm can be applied to online tasks like real-time decision-making and surveillance for networked systems. This work also provides a new scheme for the identification of systems with quantized observations.

In this paper, we study a distributed parameter estimation problem with an asynchronous communication protocol over multi-agent systems. Different from traditional time-driven communication schemes, in this work, data can be transmitted between agents intermittently rather than in a steady stream. First, we propose a recursive distributed estimator based on an event-triggered communication scheme, through which each agent can decide whether the current estimate is sent out to its neighbors or not. With this scheme, considerable communications between agents can be effectively reduced. Then, under mild conditions including a collective observability, we provide a design principle of triggering thresholds to guarantee the asymptotic unbiasedness and strong consistency. Furthermore, under certain conditions, we prove that, with probability one, for every agent the time interval between two successive triggered instants goes to infinity as time goes to infinity. Finally, we provide a numerical simulation to validate the theoretical results of this paper.

Social sampling is a novel randomized message passing protocol inspired by social communication for opinion formation in social networks. In a typical social sampling algorithm, each agent holds a sample from the empirical distribution of social opinions at initial time, and it collaborates with other agents in a distributed manner to estimate the initial empirical distribution by randomly sampling a message from current distribution estimate. In this paper, we focus on analyzing the theoretical properties of the distributed social sampling algorithm over random networks. Firstly, we provide a framework based on stochastic approximation to study the asymptotic properties of the algorithm. Then, under mild conditions, we prove that the estimates of all agents converge to a common random distribution, which is composed of the initial empirical distribution and the accumulation of quantized error. Besides, by tuning algorithm parameters, we prove the strong consistency, namely, the distribution estimates of agents almost surely converge to the initial empirical distribution. Furthermore, the asymptotic normality of estimation error generated by distributed social sampling algorithm is addressed. Finally, we provide a numerical simulation to validate the theoretical results of this paper.

This paper considers the distributed filtering problem for a class of stochastic uncertain systems under quantized data flowing over switching sensor networks. Employing the biased noisy observations of the local sensor and interval-quantized messages from neighboring sensors successively, an extended state based distributed Kalman filter (DKF) is proposed for simultaneously estimating both system state and uncertain dynamics. To alleviate the effect of observation biases, an event-triggered update based DKF is presented with a tighter mean square error bound than that of the time-driven one by designing a proper threshold. Both the two DKFs are shown to provide the upper bounds of mean square errors online for each sensor. Under mild conditions on systems and networks, the mean square error boundedness and asymptotic unbiasedness for the proposed two DKFs are proved. Finally, the numerical simulations demonstrate the effectiveness of the developed filters.

This paper studies the distributed state estimation problem for a class of discrete-time stochastic systems with nonlinear uncertain dynamics over time-varying topologies of sensor networks. An extended state vector consisting of the original state and the nonlinear dynamics is constructed. By analyzing the extended system, we provide a design method for the filtering gain and fusion matrices, leading to the extended state distributed Kalman filter. It is shown that the proposed filter can provide the upper bound of estimation covariance in real time, which means the estimation accuracy can be evaluated online.It is proven that the estimation covariance of the filter is bounded under rather mild assumptions, i.e., collective observability of the system and jointly strong connectedness of network topologies. Numerical simulation shows the effectiveness of the proposed filter.

This paper studies the distributed state estimation problem for a class of discrete time-varying systems over sensor networks. Firstly, it is shown that a networked Kalman filter with optimal gain parameter is actually a centralized filter, since it requires each sensor to have global information which is usually forbidden in large networks. Then, a sub-optimal distributed Kalman filter (DKF) is proposed by employing the covariance intersection (CI) fusion strategy. It is proven that the proposed DKF is of consistency, that is, the upper bound of error covariance matrix can be provided by the filter in real time. The consistency also enables the design of adaptive CI weights for better filter precision. Furthermore, the boundedness of covariance matrix and the convergence of the proposed filter are proven based on the strong connectivity of directed network topology and the global observability which permits the sub-system with local sensor's measurements to be unobservable. Meanwhile, to keep the covariance of the estimation error bounded, the proposed DKF does not require the system matrix to be nonsingular at each moment, which seems to be a necessary condition in the main DKF designs under global observability. Finally, simulation results of two examples show the effectiveness of the algorithm in the considered scenarios., Comment: 11 pages, 9 figures

In this paper, we investigate a distributed estimation problem for multi-agent systems with state equality constraints (SEC). First, under a time-based consensus communication protocol, applying a modified projection operator and the covariance intersection fusion method, we propose a distributed Kalman filter with guaranteed consistency and satisfied SEC. Furthermore, we establish the relationship between consensus step, SEC and estimation error covariance in dynamic and steady processes, respectively. Employing a space decomposition method, we show the error covariance in the constraint set can be arbitrarily small by setting a sufficiently large consensus step. Besides, we propose an extended collective observability (ECO) condition based on SEC, which is milder than existing observability conditions. Under the ECO condition, through utilizing a technique of matrix approximation, we prove the boundedness of error covariance and the exponentially asymptotic unbiasedness of state estimate, respectively. Moreover, under the ECO condition for linear time-invariant systems with SEC, we provide a novel event-triggered communication protocol by employing the consistency, and give an offline design principle of triggering thresholds with guaranteed boundedness of error covariance. More importantly, we quantify and analyze the communication rate for the proposed event-triggered distributed Kalman filter, and provide optimization based methods to obtain the minimal (maximal) successive non-triggering (triggering) times. Two simulations are provided to demonstrate the developed theoretical results and the effectiveness of the filters., Comment: 16 pages, 11 figures