Results on distributed state estimation for LTI systems facing communication failures

Results on distributed state estimation for LTI systems facing communication failures A. Rodr´ıguez del Nozal ∗L. Orihuela ∗∗ P. Mill´an ∗∗ A. Seuret ∗∗∗ L. Zaccarian ∗∗∗,∗∗∗∗ ∗Department of Electrical Engineering, Universidad de Sevilla, Seville, Spain (e-mail: [email protected]) ∗∗ Departamento de Ingenier´ıa, Universidad Loyola Andaluc´ıa, Sevilla, Spain (e-mail: {dorihuela, pmillan}@uloyola.es) ∗∗∗ LAAS-CNRS, Universit´e de Toulouse, CNRS, Toulouse, France (e-mail: {aseuret,zaccarian}@laas.fr) ∗∗∗∗ Department of Industrial Engineering, University of Trento, Italy Abstract: We address distributed estimation of the state of a linear plant by a set of agents. The problem is cast in a setting where the communication capabilities of an agent might be deactivated from time to time, due to failures in the communication devices or malicious attacks. An observer architecture is proposed to achieve our estimation goal, based on a multi-hop subspace decomposition, which allows each agent to identify its observable and unobservable subspaces and asymptotically estimate the plant state by using its own measurement and the information exchanged with the neighboring agents. Uniform exponential convergence to zero of the estimation errors is proven in the presence of communication failures, under a persistence of excitation assumption. Finally, the observer performance is evaluated in simulation, showing the merits of the proposed method and suggesting directions for future developments. Keywords: Distributed estimation, Link failures, Multi-agent systems, Linear time-invariant systems, Switching topologies. 1. INTRODUCTION Traditional control systems consist of a centralized controller that collects all the measurements from a plant and carries out the necessary computations to assign the control input. To accomplish this goal, it is of crucial importance to place the controller node close to the plant, namely both near the sensors and the actuators. An alternative is to introduce point-to-point communication networks exclusively devoted to the control loop. In contrast to this centralize framework, the concept of Networked Control Systems (NCS) arose at the end of the last century. NCSs are spatially distributed systems for which the communication among the sensors, actuators and controllers is supported by a shared communication network. The use of a multipurpose shared network to connect spatially distributed elements results in flexible architectures and generally reduces both installation and maintenance costs. Despite of the apparent advantages of NCS, new challenges arise for the scientific community, some of them being summarized in Zhang et al. (2015); Ge et al. (2017). One of the problems that received a great deal of attention in the last years is distributed estimation, as a first step towards achieving distributed control, or simply for monitoring purposes. The distributed estimation goal is to estimate the state of a plant by a network of agents that need to share (partial) information to accomplish a collective estimation goal. The reader is referred to Rego et al. (2019) for a recent survey of results in this area. The above-mentioned survey papers emphasize that distributed estimators must deal, among several issues related to communications, with the occurrence of failures in the communication links/devices. These failures may suddenly isolate one agent or limit its ability to receive and send information. Therefore, proposing a distributed estimator capable of coping with link and communication failures, is the main purpose of this paper. The problem itself fits perfectly one of the challenges of the cyber-physical systems community, which is the operation continuum, see Engell et al. (2015). The literature on distributed estimation is huge and many approaches can be found. This revision will start by presenting the main active research lines in the last years from a broad point of view. Later, the scope will be narrowed to the end of framing the paper contributions against the latest advances in this area. When considering perturbed systems, there are mainly three families of distributed observers, namely, distributed Kalman, H∞and set-membership filters, each one valid and optimized for specific models of disturbances and noises. Distributed Kalman filters (DKF) (first presented in Olfati-Saber (2007)) provide an optimal state estimation when the system model and the measurements of the agents are affected by Gaussian noises. However, an accurate model of these noise distributions is needed and sometimes this is difficult to obtain. The H∞filtering theory is used to develop distributed estimators providing state estimates with guaranteed performance. This strat- egy have been successfully applied in Ugrinovskii (2011) and Shen et al. (2010). Usually, distributed H∞filters rely on costly LMI design methods. Finally, set-membership approaches aim at finding a compact set where the plant state is certainly confined, see Orihuela et al. (2018); Wang et al. (2017). They are conservative approaches that are adequate when the exogenous signals satisfy known bounds. Regarding unperturbed and noiseless systems, different modifications of distributed Luenberger observers have been proposed. In pursuing of a decentralized design of the observers with minimum information, the authors of Park and Martins (2017) use state augmentations. With similar objectives, but using subspace decompositions (observable and unobservable modes), recent results have been presented in del Nozal et al. (2019); Kim et al. (2016); Mitra and Sundaram (2018). The most interesting feature of these approaches is that they can provide necessary and sufficient design conditions, based on detectability properties accounting for the presence of the communication network, and to exploit this fact in the proposed observer structure. The literature of distributed observers dealing with link failures and communication losses is less dense. The communication failures are modeled with different methods. For instance, in Ugrinovskii (2013), Markov processes are employed to model random communication topologies. However, the local mode information of the entire network topology is non-Markovian, which complicates the problem solvability. To overcome this difficulty, Ugrinovskii (2013) emploies a two-step design procedure. The corresponding solution requires solving linear matrix inequalities subject to rank constraints, which are generally difficult. A different approach to model the communication failures can be found in Liu et al. (2017) where Bernoulli variables are used. Liu et al. (2017) introduces a weighted matrix in the consensus steps in order to implement distributed filtering. In addition, boundedness properties are thoroughly investigated, using statistic information of the random link failures. Regarding the strategy used to deal with the distributed estimation problem two main approaches can be found in the literature. On the one hand, the use of H∞strategies as discussed in Yan et al. (2017) and Yu et al. (2013). In Yan et al. (2017), neural networks are used to estimate the system state using learning methods for the corresponding matrices. Instead, Yu et al. (2013) designs a filter on each node in the sensor network ensuring that the dynamics of the filtering error is meansquare stable and the prescribed average H∞performance constraint is met. On the other hand, the behaviour of the Kalman filter dealing with communication problems has been also studied. In Battilotti et al. (2018) a failure detection device is introduced in every agent to detect link failures in the network at the receiving side. In addition, by using the maximum a posteriori probability decision rule, the authors propose a method to identify online the generally correlated multiple-valued stochastic output delay which guarantees (with some approximation) the minimum probability of error, given the available observations. Finally, the algorithm presented in Alonso-Rom´an and Beferull-Lozano (2016) provides unbiased estimations when the steady-state value of the average consensus process becomes a random variable. Within this setting, we focus here on distributed estimation in the presence of communication losses, and provide: •A distributed observer structure based on a multi-hop decomposition, which decomposes the state space in the observable subspace of each agent and the innovation introduced by the neighbors at each hop. •A sufficient condition on the distributed observer gains ensuring uniform global exponential stability of the error dynamics over all possible communication losses satisfying a suitable persistence of excitation assumption. •A set of assumptions (some necessary and some sufficient) under which it is always possible to design the gains of the distributed observers in order to meet the above mentioned sufficient conditions. This paper is organized as follows. Section 2 states the main problem and presents the necessary assumptions. Section 4 presents the proposed observation structure and the main results of the paper concerning stability and feasibility. Section 5 shows the observer performance in simulations. Finally, conclusions are drawn in Section 6. Notation. A graph is a pair G= (V,E) comprising a set V={1,2, . . . , p}of vertices or agents, and a set E ⊂ V ×V of edges or links. A directed graph is a graph in which edges have orientations, so that if (j, i)∈ E, then agent iobtains information from agent j. A directed path from node i1to node ikis a sequence of edges such as (i1, i2), (i2, i3), . . ., (ik−1, ik) in a directed graph. The neighborhood of i,Ni,{j: (j, i)∈ E}, is defined as the set of nodes with edges incoming to node i. Given ρ∈Z+, the ρ-hop reachable set of i,Ni,ρ, is defined as the set of nodes with a direct path to iinvolving ρedges. Note that the 1-hop reachable set of icorresponds to the neighborhood of iand the 0-hop reachable set of imatches with i. Operators col(·,·),row(·,·) stacks subsequent matrices into a column/row vector, e.g. for Aand Bof appropriate dimensions, col(A, B)=[A>B>]>and row(A, B) = [A B]. |x|is the Euclidean norm of vector x.||A|| stands for the induced matrix norm of matrix A. 2. PROBLEM STATEMENT Consider a set of agents V={1,2, . . . , p}intending to distributedly estimate the state of the discrete-time LTI system x(k+ 1) = Ax(k),(1) yi(k) = Cix(k),∀i∈ V,(2) where xis the state vector, Ais the system matrix, yi∈Rmiis the output locally measured by agent iand Ci∈Rmi×nis its output matrix. Since the agents are not able to reconstruct the whole state xbased only on the local measurement yi(i.e. detectability of (Ci, A) is not assumed), a communication network among them is required. Thus, let G= (V,E) represents the directed graph modelling the communication network where no communication failures are allowed. For this directed graph, E ⊂ V×V represents every communication channel between pairs of agents. 2.1 Collective detectability assumption We introduce here some key concepts, useful for the developments of the rest of the paper. Definition 1. For the communication graph G, the ρ-hop output matrix of agent i,Ci,ρ, is defined as: Ci,ρ := Ci,ρ−1 col(Cj,ρ−1)j∈Ni,∀ρ≥1,(3) where Ci,0:= Ci. Intuitively speaking, the ρ-hop output matrix Ci,ρ of agent i, recursively defined in (3), comprises its output matrix Ciand the output matrices of all the agents jwith a direct path to iinvolving ρor less edges. Based on this concept, we can formulate our first assumption. A similar assumption was introduced in del Nozal et al. (2019). Definition 2. System (1)-(2) is collectively detectable if, for any i∈ V, there exists a finite number of hops `i∈Z>0 such that pair (Ci,`i, A) is detectable. Assumption 1. System (1)-(2) is collectively detectable. As shown in del Nozal et al. (2019), Assumption 1 is necessary for the existence of a converging distributed state estimator. According to Definition 2, system (1)-(2) is collectively detectable if, for each agent, the complete information provided by the network (that is, the ρ-hop output matrix with ρsufficiently large) is sufficient to build a converging state observer. Recall that a strongly connected communication network is not required in contrast with other approaches as Wang et al. (2019) 2.2 Communication model and persistence assumption In this paper, we consider that the topology of the network Gcan vary with time due to failures in the communication devices, jamming attacks (see Jin (2010)) or packet dropouts. To this end, a logic variable k7→ δi(k)∈ {0,1}is associated to each node ito represent communication failures for agent iat time k. Using δi, the set of links pointing to agent i, (i, j) : ∀j∈ Ni, are active at time k if and only if δi(k) = 1. Otherwise, when δi(k) = 0, these links are inactive due to a communication failure. As a result, E(k) and G(k) = (V,E(k)) represent, respectively, the set of active links at time kand characterize the timevarying graph at time k. Whenever a loss occurs, agent icannot receive information from its neighborhood. Consequently, it would be reasonable to operate based only on the system model and on the local measurement yi. However, if this situation is extended in time, the plant state cannot be detected in the directions that are not observable from that output. To rule out this scenario, we assume the following persistence of excitation property. Definition 3. Graph k7→ G(k) = (V,E(k)) enjoys a uniform local persistence property if for each i∈ V there exist a finite time horizon τi∈Z>0and an integer nτi∈Z>0such that τi−1 X h=0 δi(k+h)≥nτi,∀k∈Z≥0,(4) namely, for each time interval {k, . . . , k +τi−1},k∈Z>0, there exist at least nτidistinct values of s∈ {k, . . . , k + τi−1}satisfying δi(s) = 1. Assumption 2. The graph k7→ G(k) = (V,E(k)) enjoys a uniform local persistence property. Assumption 2 requires that each agent iexperiences no more than τi−nτicommunication losses in each time window spanning τitime instants. This implies that the agent receives enough information from the neighboring agents, which corresponds to some kind of persistence of excitation. While Assumption 2 is not necessary, in general, we emphasize that it does not hold true only in cases where the communication instants (when δi= 1) become increasingly rare as time flows. Such a scenario is quite undesirable if one wants to achieve uniform convergence properties like those in our problem statement below. 2.3 Problem statement Based on our standing Assumptions 1 and 2, we are ready to state our problem statement. Problem 1. Consider system (1)-(2) and an interconnection graph G(k)=(V,E(k)). Under Assumptions 1 and 2, design a distributed observer providing, at each node i, an estimate ˆxiof the state xof (1)-(2), such that these estimates converge uniformly and exponentially to x. In particular, for each δi,i= 1, . . . , p, satisfying Assumption 2, there must exist scalars M > 0 and λ∈(0,1) such that, for any x(0) and any ˆxi(0), i∈ V, |x(k)−ˆxi(k)|2≤Mλk p X j=1 |x(0) −ˆxj(0)|2,∀i∈ V.(5) The distributed observer that we design to solve the problem above generalizes the linear time-invariant solution in del Nozal et al. (2019). The novelty that we propose here is that we focus on linear dynamics subject to the “external” time-varying logical inputs δi(k). Due to these extra inputs, the linear cascaded arguments of del Nozal et al. (2019) cannot be adopted, but we may resort to nonlinear Input to State Stability (ISS) results for timevarying systems. 3. MULTI-HOP SUBSPACE DECOMPOSITION Before presenting the observer dynamics, we recall the basic concepts behind the multi-hop subspace decomposition presented in del Nozal et al. (2019). There always exists a coordinate transformation matrix ¯ Vi,ρ Vi,ρ∈Rn×nassociated to pair (Ci,ρ, A), such that the change of variable [ ¯ Vi,ρ Vi,ρ]>x∈Rntransforms the original state-space representation into the observability staircase form Hespanha (2009). Note that ¯ Vi,ρ ∈Rn×n¯o i,ρ is composed by n¯o i,ρ column vectors in Rnthat form an orthogonal basis of the unobservable subspace of pair (Ci,ρ, A). Correspondingly, Vi,ρ ∈Rn×no i,ρ is an orthogonal basis of its orthogonal complement. Definition 4. The ρ-hop unobservable subspace from agent i, denoted ¯ Oi,ρ, is composed of all system modes that cannot be observed from the output locally measured by agent iand those measured by all the agents belonging to the s-hop reachable nodes from i,∀s∈ {0, . . . , ρ}. Equivalently, the ρ-hop unobservable subspace from agent iis the unobservable subspace related to pair (Ci,ρ, A) using the above coordinate transformation: ¯ Oi,ρ := Im( ¯ Vi,ρ). The orthogonal complement of ¯ Oi,ρ, with some abuse of notation, is denoted ρ-hop observable subspace from agent i,Oi,ρ := Im(Vi,ρ). We denote no i,ρ = dim(Oi,ρ). According to Definition 4, it is clear that: Oi,ρ−1⊆ Oi,ρ,∀i∈ V, ρ ≥0.(6) where we consider Oi,−1=∅. Then, the vectors of the “innovation” basis that generates Oi,ρ ∩(Oi,ρ−1)⊥can be stacked into a matrix Wi,ρ ∈Rn×ni,ρ , where ni,ρ =no i,ρ − no i,ρ−1, in such a way that: Im(Wi,ρ) := Oi,ρ ∩(Oi,ρ−1)⊥, ρ ≥0,(7) Let us define `i∈Z>0, to be selected later, as an arbitrary number of hops. From these definitions it is clear that for all ρ∈ {0, . . . , `i}and all i∈ V, it holds that Im(Vi,ρ) = Im ([Wi,ρ Vi,ρ−1]) ,(8) Im( ¯ Vi,ρ−1) = Im Wi,ρ ¯ Vi,ρ,(9) with ¯ Vi,−1:= In. It is worth pointing out that Im(Wi,ρ) corresponds to the innovation introduced by the ρ-hop reachable set Ni,ρ of agent i, that is, the observable modes for agent iat hop ρ that are not observable at hop ρ−1. Accordingly the transformation matrix Ti∈Rn×n, defined as Ti= [¯ Vi,`iVi,`i], can be partitioned as follows, using the innovations at each hop: Ti:= | {z } ¯ Vi,ρ ¯ Vi,`iWi,`i· · · Wi,ρ+1 | {z } Vi,ρ Wi,ρ · · · Wi,0,(10) for all ρ∈ {0, . . . , `i}, where it is easy to identify the observable and unobservable subspaces of the system by agent iat hop ρ. Note also that Tiis orthogonal by construction, namely T−1 i=T> i. The following lemma, proven in (del Nozal et al., 2019, Lemma 3), introduces some important properties that are central for the derivations of this paper. Lemma 1. (del Nozal et al., 2019, Lemma 3) For each agent i∈ V, and any `i>Z>0, the next properties hold, ∀ρ,ρ0∈ {1, . . . , `i}such that ρ6=ρ0: (i) W> i,ρWi,ρ0= 0, (ii) Im(Wj,ρ−1)⊆Im(Vi,ρ),∀j∈ Ni, (iii) Im(Wi,ρ)⊆L j∈Ni Im(Wj,ρ−1). 4. OBSERVER DESIGN FOR STABILITY DEALING WITH COMMUNICATION FAILURES This section contains the main results of the paper. First we present the observer structure and then we derive the ensuing error dynamics. Finally, we provide design rules for the observer gains solving Problem 1 and we show that, under the prescribed assumptions, the design of these gains is feasible. 4.1 Observer structure and error dynamics For any agent i, we propose the following observer structure: ˆxi(k+ 1) = Aˆxi(k) + Wi,0Li(yi(k)−ˆyi(k)) +δi(k) `i X ρ=0 X j∈Ni Wi,ρNi,j,ρW> j,ρ−1(ˆxj(k)−ˆxi(k)),(11) where Liand Ni,j,ρ are, respectively, a local gain and consensus gains to be selected later in such a way that Problem 1 is solved. The value of `iis chosen so that collective detectability is fulfilled as per Assumption 1. This structure was presented in del Nozal et al. (2019) for δi(k) = 1,∀k. For a more detailed explanation of the proposed observer structure, the reader is referred to that paper. For each agent i∈ V, let us define the corresponding estimation error ei(k) := x(k)−ˆxi(k). Similarly, it is possible to define the transformed estimation error as εi:= col(εi,`i+1, . . . , εi,0) := T> iei,(12) using the multi-hop subspace decomposition (10) introduced in Section 2. More specifically, the estimation error of agent i∈ V, at hop ρ, is defined as: εi,ρ(k) := W> i,ρei(k),∀ρ= 0, . . . , `i+ 1,where we denote Wi,`i+1 =¯ Vi,`icorresponding to the collectively unobservable but detectable system modes. The following proposition clarifies the dynamics of these estimation errors. Its proof is a straightforward extension of the results in del Nozal et al. (2019) and is therefore omitted. Proposition 1. Consider the network of agents described by the graph G(k), where every agent iimplements the observer structure (11) to estimate the state of system (1). Then the dynamics of the errors in (12) corresponds to εi,0(k+ 1) = (W> i,0AWi,0−LiCiWi,0)εi,0(k),(13) εi,ρ(k+ 1) = ρ X r=0 Di,(ρ,r)(δi)εi,r(k) (14) +δi(k)X j∈Ni Ni,j,ρεj,ρ−1(k), ρ ∈ {1, . . . , `i}, with Di,(ρ,r)(δi) = W> i,ρAWi,r −δiX j∈Ni Ni,j,ρW> j,ρ−1Wi,r. The dynamics in Proposition 1 for ρ∈ {1, . . . , `i}can be compactly written as (we remove the dependence on kfor simplicity): ε+ i,0= (W> i,0AWi,0−LiCiWi,0)εi,0,(15a) ε+ i,ρ =Di,(ρ,ρ)(δi)εi,ρ +Bi,ρ(δi)ui,ρ,if ρ6= 0 (15b) where Bi,ρ(δi) = hrow Di,(ρ,r)(δi)r∈{0,...,ρ−1}| |row (δiNi,j,ρ)j∈Nii, ui,ρ(k) = col(εi,r)r∈{0,...,ρ−1} col(εj,ρ−1)j∈Ni, which shows an interesting cascaded structure exploited in our main results of the next section. 4.2 Main result and tuning of the observer gains By exploiting the cascaded dynamics (15), this section presents a design requirement that will be proven to be sufficient to guarantee the exponential estimation properties of Problem 1. Note that, since the evolution of the transformed estimation error at hop ρ= 0 does not depend on the agents connectivity, the local gain Lican be easily tuned to ensure uniform exponential convergence to zero of the solutions to (15a). Instead, the connectivity properties in Assumption 2 are fundamental for the effectiveness of the design of the consensus gains Ni,j,ρ, for which the cascade structure revealed with the multi-hop decomposition becomes crucial. Property 1. For each agent i, the local gain Liand consensus gains Ni,j,ρ for hops ρ∈ {1, . . . , `i}are designed in such a way that the matrix (W> i,0AWi,0−LiCiWi,0) (16) is Schur, and the following inequalities are met: Di,(ρ,ρ)(δi)>Pi,ρDi,(ρ,ρ)(δi)< µi,ρ(δi)Pi,ρ, δi∈ {0,1} (17) µi,ρ := µi,ρ(0)τi−nτiµi,ρ(1)nτi<1,(18) where µi,ρ(δi), δi= 0,1 are two a scalar parameters depending on the switching signal δi, satisfying µi,ρ(1) ≤ µi,ρ(0) and Pi,ρ is a positive definite matrix with appropriate dimensions. Now, we are in position to introduce the main result of the paper in Theorem 1, which establishes that observer (11) solves Problem 1 whenever Property 1 is satisfied. Its proof is postponed to Section 4.3 to avoid breaking the flow of the exposition. Theorem 1. Consider plant (1) observed by a set of agents that can measure their local outputs (2), each of them implementing the observer structure (11). Under Assumptions 1 and 2, if the observer gains are designed according to Property 1, then Problem 1 is solved, namely the estimation errors satisfy (5). The next theorem completes the statement of Theorem 1. Theorem 2. It is always possible, under Assumptions 1 and 2, to design matrices Li, Ni,j,ρ,∀i, ρ and j∈ Ni, that satisfy Property 1. Proof. According to (del Nozal et al., 2019, Theorem 14), in the absence of communication failures, namely δi(k) = 1 for all iand for all k, under Assumption 1 it is possible to design gain matrices Li, and Ni,j,ρ to fix the convergence rate of the estimator arbitrarily fast (a detailed design method is presented there). In other words the value µi,ρ(1) can be selected arbitrarily close to zero by appropriate choices of the gains. Due to the fact that the value of µi,ρ(0) is determined by the open-loop system dynamics, and therefore independent of the observer gains, it is then possible to choose µi,ρ(1) sufficiently small to ensure µi,ρ(0)τi−nτiµi,ρ(1)nτi<1 for any given pair τi, nτi from Assumption 2. 2 4.3 Proof of Theorem 1 Before proving the theorem, we introduce some preliminary results. Our proof is based on Input to State Stability (ISS) properties for systems of the form ξ(k+ 1) = f(ξ(k), u(k), k),(19) which well represent dynamics (15b). In particular, we make use of the following property. Definition 5. System (19) is uniformly globally exponentially finite-gain ISS with respect to uif there exist scalars M > 0, λ∈(0,1) and γ > 0, such that for any initial time k0, any initial condition ξ(k0) and any uniformly bounded input k7→ u(k), the corresponding solution k7→ ξ(k) satisfies 1 |ξ(k)|2≤Mλk−k0|ξ(k0)|2+γkuk2 ∞,∀k≥0, where kuk∞:= supk≥k0|u(k)|denotes the l∞norm of the input u. To prove the above ISS property for each one of the subsystems in (15b), for each i∈ V and each ρ∈ {1, . . . , `i}we will use the following quadratic Lyapunov function Vi,ρ(εi,ρ(k)) = εi,ρ(k)>Pi,ρεi,ρ(k),(20) where Pi,ρ is a symmetric positive definite matrix. With some abuse of notation, we will use Vi,ρ(k) in place of Vi,ρ(εi,ρ(k)) in the next derivations. Lemma 2. If Property 1 holds, then for each i∈ V and each ρ∈ {1, . . . , `i}there exists a scalar γi,ρ ∈R+such that the Lyapunov function (20) satisfies Vi,ρ(k+ 1) < µi,ρ(δi)Vi,ρ(k) + γi,ρ |ui,ρ(k)|2(21) along the solutions to (15b). Proof. Let us write the derivative of the Lyapunov function (20) along the error dynamics in (15). To this end, and to keep the notation more compact, let us denote Vi,ρ(k) merely by Vi,ρ and Vi,ρ(k+ 1) by V+ i,ρ (and similarly for δi and εi,ρ and ui,ρ). We then have V+ i,ρ = (ε+ i,ρ)>Pi,ρε+ i,ρ =ε> i,ρDi,(ρ,ρ)(δi)>Pi,ρDi,(ρ,ρ)(δi)εi,ρ + 2ε> i,ρDi,(ρ,ρ)(δi)>Pi,ρBi,ρ(δi)ui,ρ +u> i,ρBi,ρ(δi)>Pi,ρBi,ρ(δi)ui,ρ ≤ε> i,ρDi,(ρ,ρ)(δi)>Pi,ρDi,(ρ,ρ)(δi)εi,ρ + 2 Di,(ρ,ρ)(δi)>Pi,ρBi,ρ(δi)· |εi,ρ|·|ui,ρ| +Bi,ρ(δi)>Pi,ρBi,ρ(δi)· |ui,ρ|2. 1Note that the standard definition of ISS does not include square powers in signals norms. Nevertheless, if this expression is fulfilled it is trivial to go back to the standard definition. By completing squares and using the Cauchy–Schwarz inequality, the following bound holds for any selection of ηi,ρ ∈R+: 2|εi,ρ| |ui,ρ| ≤ ηi,ρ |εi,ρ|2+1 ηi,ρ |ui,ρ|2(22) Moreover, from Property 1, there exists a positive scalar νi,ρ ∈R+such that Di,(ρ,ρ)(δi)>Pi,ρDi,(ρ,ρ)(δi)< µi,ρ(δi)Pi,ρ −νi,ρI. Therefore, selecting ηi,ρ in (22) small enough to satisfy Di,(ρ,ρ)(δi)>Pi,ρBi,ρ(δi)ηi,ρ < νi,ρ, we may combine the previous bounds to prove (21) with the selection γi,ρ = max δi∈{0,1}η−1 i,ρ Di,(ρ,ρ)(δi)>Pi,ρBi,ρ(δi)+ Bi,ρ(δi)>Pi,ρBi,ρ(δi).2 Based on the previous lemma, we can now prove an ISS property, in the sense of Definition 5, for dynamics (15b) for each i∈ V and each ρ∈ {1, . . . , `i}. This is established next. Lemma 3. If Property 1 and Assumption 2 hold, then for each i∈ V and each ρ∈ {1, . . . , `i}the error system with dynamics (15b) is uniformly globally exponentially finitegain ISS with respect to ui,ρ. Proof. The proof is based on demonstrating that the system error dynamics meets Definition 5 and consequently, it is exponentially finite-gain ISS with respect to ui,ρ. First, exploiting µi,ρ(1) ≤µi,ρ(0) in Property 1 and using Assumption 2, we may recursively apply expression (21) to τisuccessive time instants to obtain Vi,ρ(k+τi)< µi,ρVi,ρ(k) + γi,ρ||ui,ρ||2 ∞,(23) where ||ui,ρ||∞= supk≥0|ui,ρ(k)|the bound on ui,ρ(k),∀k, µi,ρ <1 is defined in (18), and γi,ρ = τi−2 X t=0 τi−1 Y s=t+1 µi,ρ(δi(k+s))!+ 1!γi,ρ, By recursively applying equation (23) evaluated at times of k=hτi, we obtain (we focus on the case k0= 0 because the extension to the case k06= 0 is straightforward) Vi,ρ((h+ 1)τi)< µi,ρVi,ρ(hτi) + γi,ρ||ui,ρ||2 ∞ . . . (24) < µh+1 i,ρ Vi,ρ(0) + γi,ρ||ui,ρ||2 ∞, where we used the fact that µi,ρ <1 implies that the following geometric series converges: γi,ρ := γi,ρ 1 1−µi,ρ =γi,ρ +∞ X s=0 µs i,ρ ≥ h X s=0 µs i,ργi,ρ. Consider now the intersample behavior of Vi,ρ and note that linearity of the dynamics (15b) implies that there exists a large enough scalar σsuch that Vi,ρ(hτi+s)≤σVi,ρ(hτi) + σ||ui,ρ||2 ∞,∀s∈ {0, . . . , τi−1}. (25) Combining bounds (24) and (25), we obtain the following bound for some suitable λV∈(0,1), MV>0 and γV>0: Vi,ρ(k)≤MVλk VVi,ρ(0) + γVkuk2 ∞,∀k≥0.(26) Finally, from standard properties of positive definite matrices, we get λmin(Pi,ρ)|εi,ρ(k)|2≤Vi,ρ(k)≤λmax(Pi,ρ)|εi,ρ(k)|2, which can be used twice in (26) to prove the desired ISS bound |εi,ρ(k)|2<λM(Pi,ρ) λm(Pi,ρ)MVλk V|εi,ρ(0)|2+γV λm(Pi,ρ)||ui,ρ||2 ∞, as to be proven. 2 From Lemma 3, the proof of Theorem 1 can be presented. Proof of Theorem 1. Since matrix (16) in Property 1 is Schur by assumption, the dynamics of the estimation error at hop ρ= 0 is exponentially stable for all agents, namely there exist M0>0 and λ0∈(0,1) such that |εi,0(k)| ≤ M0λk 0|εi,0(0)|for all k > 0 and all i∈ V. Using this bound, and due to the cascaded-like expression of ui,ρ in (15b), we may concatenate the ISS bounds established in Lemma 3 to obtain that there exits λε∈ (0,1) and Mε>0 such that vector ε= col(ε1, . . . , εp) satisfies the ISS bound |ε(k)|2≤Mελk ε|ε(0)|2.(27) Since εis equivalent (through linear transformation) to e= col(e1, . . . , ep) (where we recall that ei=x−ˆxi), then the previous bound implies bound (5) in Problem 1, thus completing the proof. 2 Remark 1. We emphasize that the proof technique of this section, based on the time-varying dynamics (19), ensures that for each persistently exciting selection of δi, i= 1, . . . , p, as per Definition 3, there exist Mεand λεsatisfying (27) (equivalently (5) in Problem 1). However, we don’t give here a guarantee that those scalars be uniform over the infinitely many persistently exciting selections of δi. Nevertheless, we conjecture that a different proof technique may be used to prove a uniform exponential bound, valid for all such selections. Proving this uniform exponential convergence property is left as future work. 5. SIMULATION RESULTS This section presents some simulation results that demonstrate the effectiveness of the proposed estimation algorithm. To this end, let us consider the following LTI autonomous system:    x1 x2 x3 x4    + =   0.95 0 0 0 0 0.8606 −1.3368 0 0 0.1485 0.9315 0 0 0 0 1.015      x1 x2 x3 x4   . The system is observed by a set of three agents that communicate according to the following diagram 1 ↔2↔ 3. Then, the interconnection graph is composed by V= {1,2,3}and the set of edges is E={(1,2),(2,1),(2,3), (3,2)}, generating graph G= (V,E). In all of the examples discussed below, we consider the following output matrices for the three agents: C1=   1 0 0 0 0 0 0 1    > , C2=   0 1 0 0    > , C3=   1 0 0 0 0 0 0 1    > . Example 1. Let us assume a scenario where the agents experience communication failures. We assume that at every time interval {k, . . . , k+τi−1}, where τi= 100,∀i∈ V, there exists at least nτi= 20 times when every agents i= 1,2,3, can communicate with their neighborhood. According to (11), when the agent icannot communicate, the observer dynamics only uses the local measurements yi. Thus, the error dynamics of the locally unobservable subspaces will evolve in open loop. In the case of unstable dynamics, the estimation error will accordingly grow. 0 0.5 1 1.5 2 2.5 3 10 20 30 40 50 60 70 80 90 100 1 0 Fig. 1. Estimation error of agent 2 in Example 1. Figure 1 shows the evolution of the estimation error of agent 2, estimating states x1and x4. Recall that these states are measured by agents 1 and 3 and, according to the communication topology, these agents are one hop away from agent 2. When agent 2 can communicate, the estimation error decreases significantly. This is a consequence of the fast convergence rate fixed in the observer design. However, when agent 2 is not able to communicate with its neighbors the estimation error grows according to the unstable open-loop dynamics. Example 2. This second example shows the unstable response of the state estimation error when Property 1 is not met. The consensus matrices designed in the previous example for τi= 100, nτi= 20, do not satisfy Property 1 in the worsened scenario with τi= 100, nτi= 2, for all i∈ V, namely with increased communication losses. By performing a parallel simulation to the one of the previous example, we now observe a diverging error response. In particular, Figure 2 shows the evolution of the estimation error of agent 2 estimating state x4. Note that the estimation error decreases when the communications are active. However, this is not enough to stabilize the estimation error. Example 3. Let us present in this example an extension of the work proposed in this paper in which, instead of total communication losses, we consider that each link in the network can individually fail. In this case one may select the same observer structure (11) by setting δi(k) = 0 when just one link incoming to agent iis failing. However this approach may be quite conservative. Here we propose an alternative observer structure where the failure-related logical variables δare associated to the links (that is, we call them δi,j (k)) rather than to the nodes. In particular, we may modify (11) as follows 1 2 3 4 5 10 20 30 40 50 60 70 80 90 100 1 0 Fig. 2. Estimation error of agent 2 estimating state x4in Example 2. 0 1 2 0 0.5 1 10 20 30 40 50 60 70 80 90 100 0 0.5 1 (4) Fig. 3. Estimation error of Agent 2 estimating state x4in Example 2. ˆxi(k+ 1) = Aˆxi(k) + Wi,0Li(yi(k)−ˆyi(k)) + `i X ρ=0 X j∈Ni δi,j(k)Wi,ρNi,j,ρW> j,ρ−1(ˆxj(k)−ˆxi(k)), where δi,j(k) is a binary variable indicating whether link (i, j) is active (δi,j (k) = 1) or not (δi,j (k) = 0) at time k. Due to the topology considered in our example, only agent 2 can benefit from the proposed modification. Hence, Figure 3 shows the evolution of the estimation error of Agent 2 estimating state x4when using this revised structure. With the same gains Ni,j,ρ used in the previous examples, the new structure successfully estimates the fourth state. This last example encourages the authors to work towards a generalization of our approach to the case where the agents have partial communication or link failures, but still can make use of the information received from the rest their neighbors. 6. CONCLUSIONS In this paper, the distributed state estimation problem of an autonomous LTI system by a lossy network of agents has been addressed. By using an observer structure based on a multi-hop subspace decomposition, each agent involved in the network can identify its observable subspace and the innovations introduced (whenever a communication loss does not occur) by its neighbors at each hop. Under some reasonable assumptions on the network connectivity, we have shown that it is always possible to find observer gains guaranteeing uniform exponential convergence to zero of all the estimation errors. Our architecture has been tested by means of simulations and the main results of the paper have been illustrated by a network of three agents. Future work includes proving a uniform version of our exponential bound. ACKNOWLEDGEMENTS Research partially supported by grant TEC2016-80242- P founded by AEI/FEDER through the Laboratorio de Simulaci´on Hardware-in-the-loop, and by ANR via grant HANDY, number ANR-18-CE40-0010. REFERENCES Alonso-Rom´an, D. and Beferull-Lozano, B. (2016). Adaptive consensus-based distributed Kalman filter for WSNs with random link failures. In 2016 International Conference on Distributed Computing in Sensor Systems (DCOSS), 187–192. IEEE. Battilotti, S., Cacace, F., d’Angelo, M., and Germani, A. (2018). Distributed Kalman filtering over sensor networks with unknown random link failures. IEEE control systems letters, 2(4), 587–592. del Nozal, A.R., Mill´an, P., Orihuela, L., Seuret, A., and Zaccarian, L. (2019). Distributed estimation based on multi-hop subspace decomposition. Automatica, 99, 213–220. Engell, S., Paulen, R., Reniers, M., Sonntag, C., and Thompson, H. (2015). Core research and innovation areas in cyber-physical systems of systems. In International Workshop on Design, Modeling, and Evaluation of Cyber Physical Systems, 40–55. Springer. Ge, X., Yang, F., and Han, Q. (2017). Distributed networked control systems: A brief overview. Information Sciences, 380, 117–131. Hespanha, J.P. (2009). Linear systems theory. Princeton university press. Jin, H. (2010). Handbook of Research on Developments and Trends in Wireless Sensor Networks: From Principle to Practice. IGI Global. Kim, T., Shim, H., and Cho, D.D. (2016). Distributed Luenberger observer design. In Proceedings of the IEEE Conference on Decision and Control (CDC), 6928–6933. Las Vegas. Liu, Q., Wang, Z., He, X., and Zhou, D. (2017). On Kalman-consensus filtering with random link failures over sensor networks. IEEE Transactions on Automatic Control, 63(8), 2701–2708. Mitra, A. and Sundaram, S. (2018). Distributed observers for LTI systems. IEEE Transactions on Automatic Control, 63(11), 3689–3704. Olfati-Saber, R. (2007). Distributed Kalman filtering for sensor networks. In Proceedings of the IEEE Conference on Decision and Control (CDC), 5492–5498. LA. Orihuela, L., Mill´an, P., Roshany-Yamchi, S., and Garc´ıa, R.A. (2018). Negotiated distributed estimation with guaranteed performance for bandwidth-limited situations. Automatica, 87, 94–102. Park, S. and Martins, N.C. (2017). Design of distributed LTI observers for state omniscience. IEEE Transactions on Automatic Control, 62(2), 561–576. Rego, F., Pascoal, A., Aguiar, A., and Jones, C. (2019). Distributed state estimation for discrete-time linear time invariant systems: A survey. Annual Reviews in Control. Shen, B., Wang, Z., and Hung, Y.S. (2010). Distributed H∞-consensus filtering in sensor networks with multiple missing measurements: The finite-horizon case. Automatica, 46(10), 1682–1688. Ugrinovskii, V. (2011). Distributed robust filtering with H∞consensus of estimates. Automatica, 47(1), 1–13. Ugrinovskii, V. (2013). Distributed robust estimation over randomly switching networks using H∞consensus. Automatica, 49(1), 160–168. Wang, L., Liu, J., Morse, A.S., and Anderson, B.D.O. (2019). A distributed observer for a discrete-time linear system. In 2019 Conference on Decision and Control, Nice, France. Wang, Y., Alamo, T., Puig, V., and Cembrano, G. (2017). Distributed zonotopic set-membership state estimation based on optimization methods with partial projection. IFAC-PapersOnLine, 50(1), 4039–4044. Yan, H., Yang, Q., Zhang, H., Yang, F., and Zhan, X. (2017). Distributed H∞state estimation for a class of filtering networks with time-varying switching topologies and packet losses. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 48(12), 2047–2057. Yu, H., Zhuang, Y., and Wang, W. (2013). Distributed H∞filtering in sensor networks with randomly occurred missing measurements and communication link failures. Information Sciences, 222, 424–438. Zhang, X., Han, Q., and Yu, X. (2015). Survey on recent advances in networked control systems. IEEE Transactions on Industrial Informatics, 12(5), 1740– 1752.