High Performance Distributed Control Law for Large-Scale Linear Systems: A Partitioned Distributed Observer Approach

Consider a large-scale interconnected system composed by $N$ subsystems (corresponding to $N$ agents) and the $i$th subsystem takes the form of:

where $x_{i}\in\mathbb{R}^{n}$, $y_{i}\in\mathbb{R}^{p}$, and $u_{i}\in\mathbb{R}^{m}$ are the system states, output measurements, and control inputs of the $i$th subsystem, respectively; $x_{j}\in\mathbb{R}^{n}$ is the state of the $j$th subsystem; The matrices $A_{ii}$, $B_{i}$, and $C_{i}$ represent the system matrix, control matrix, and output matrix of the $i$th subsystem with compatible dimensions, respectively; and $A_{ij}\in\mathbb{R}^{n\times n}$ stands for the coupling matrix between the $i$th and the $j$th subsystems. Let $A=[A_{ij}]_{i,j=1}^{N}$, $B=diag\{B_{1},\ldots,B_{N}\}$, and $C=col\{C_{1},\ldots,C_{N}\}$, then the compact form of the large-scale system is given by

where $x=col\{x_{1},\ldots,x_{N}\}\in\mathbb{R}^{nN}$, $y=col\{y_{1},\ldots,y_{N}\}\in\mathbb{R}^{pN}$, and $u=col\{u_{1},\ldots,u_{N}\}\in\mathbb{R}^{mN}$.

We construct a physical network for this large-scale system by its interconnection. Let $\mathcal{V}$ be the nodes (agents) set and we say $(j,i)$ is an edge connecting $j$ and $i$ if $\|A_{ij}\|\neq 0$. Then, the set $\mathcal{E}_{p}$ is defined by $\mathcal{E}_{p}=\{(i,j):~{}\|A_{ji}\|\neq 0\}$. Accordingly, the adjacency matrix is defined as $\mathcal{A}_{p}=[\beta_{ij}]_{i,j=1}^{N}$ where $\beta_{ij}=1$ if $(j,i)\in\mathcal{E}_{p}$. Let $\mathcal{N}_{i}=\{j:~{}\beta_{ij}=1\}$ be the set of physical network neighbors of agent $i$. The physical network can be directed or undirected and the schematic diagrams in this paper all use undirected graphs, but it should be noted that when the physical network is an undirected graph, the system matrix is assumed to have constraints with $\|A_{ij}\|=\|A_{ji}\|=0$; When the physical network is a directed graph, the system matrix has no constraints. Moreover, an undirected graph $\mathcal{G}_{c}=\{\mathcal{V},\mathcal{E}_{c},\mathcal{A}_{c}\}$ represents the communication network among all nodes, where $\mathcal{E}_{c}$ and $\mathcal{A}_{c}=[\alpha_{ij}]_{i,j=1}^{N}$ are the associated edge set and adjacency matrix, respectively. Then, the set of communication network neighbors of agent $i$ is given by $\mathcal{C}_{i}=\{j:~{}\alpha_{ij}=1\}$. The Laplacian matrix associated to $\mathcal{G}_{c}$ is denoted by $\mathcal{L}_{c}=\mathcal{D}_{c}-\mathcal{A}_{c}$, where $\mathcal{D}_{c}=diag\{d_{i},~{}i=1,\ldots,N\}$ with $d_{i}=-\alpha_{ii}+\sum_{j=1}^{N}\alpha_{ij}$.

In traditional distributed observer, each local observer—the orange block in Figure 1—is required to reconstruct all the states of the entire system based on $y_{i}$ and the information exchanged via communication network. Then, each local controller—blue block in Figure 1—can use all the information of the entire system. Therefore, all local observers can jointly establish a distributed control law with centralized performance. Many existing studies, such as [2, 9], have proved this result, i.e., the distributed-observer-based distributed control law can achieve centralized control performance. However, in these studies, each local observer needs to reconstruct the states of the whole system, i.e, dimension of observers on each agent is $nN$. This is not realistic for large-scale systems. Therefore, this paper will investigate whether it is possible to achieve distributed control laws with arbitrary approximation of centralized control performance without requiring each local observer to estimate global information.

To formulate the problem, we assume that there is a centralized control law $u(x)=col\{u_{1}(x),\ldots,u_{N}(x)\}$ such that system (3) is stabilized, and denote $x_{c}(t)$ the solution of (3) with centralized control law. We further assume a distributed control law $\bar{u}_{i}(\hat{x}_{i\star})$ such that $x_{r}(t)$ solved by (3) with $u=\bar{u}(\hat{x}_{i\star})$ is stabilized, where $\hat{x}_{i\star}$ is the states estimation generated by the $i$th local observer located at the $i$th agent, and $\bar{u}(\hat{x}_{i\star})=col\{\bar{u}_{i}(\hat{x}_{i\star}),~{}i=1,\ldots,N\}$. Subsequently, the overall goal of this paper consists of the following two parts.

1) Design the partitioned distributed observer with $\hat{x}_{i\star}$ being the states of the $i$th local observer, and $\hat{x}_{i\star}$ satisfies $dim\{\hat{x}_{i\star}\}\ll dim\{x\}$;

2) Design a distributed-observer-based distributed control law $\bar{u}(\hat{x}_{i\star})$ such that $x_{r}(t)$ can approach $x_{c}(t)$ arbitrarily, i.e., $\|x_{c}(t)-x_{r}(t)\|<\varepsilon$, $\forall\varepsilon>0$ and $\forall t\geq 0$.

In this subsection, we will illustrate an example for helping readers understand the problems proposed in the above subsection. See in Figure 2, the coupling relationship of a large-scale system is shown in the physical network, in which each node represents an subsystem. Assume that each subsystem has a corresponding agent, and the communication relationship among all agents is shown as communication network. The $i$th agent has access to the information of $y_{i}$, and is supposed to establish several local observers and a local control law.

We take node $13$ as an example to demonstrate the specific issues to be studied in this paper. As seen in Figure 2, node $13$ has $5$ physical neighbors ($11,12,14,15,16$) and $3$ communication neighbors ($11,14,16$). To design a local control law to make the control performance as close as possible to the centralized control law, agent $13$ needs the states of all its physical neighbors. In traditional method, a distributed observer will be designed such that agent $13$ can reconstruct all states of the entire system. However, only the states of $11,12,14,15,16$ are required. Therefore, this paper intends to design a group of partitions and design distributed observer in each partition. In this way, the useless information estimated by each agent can be greatly reduced. For example, in Figure 2, node $13$ belongs to $3$ partitions—$\{11,12,13\}$, $\{13,15,16\}$, and $\{13,14\}$. By designing distributed observers separately in three partitions, agent $13$ only needs to estimate the states of $5$ subsystems (in traditional methods, agent $13$ needs to estimate the states of all $47$ subsystems). With partitioned distributed observers, local control laws can be established based on the results of state estimation.

Up to now, we have briefly described the main idea of this paper through an example. To achieve this idea, there are mainly three steps involved: 1) Design a reasonable and effective partitioning algorithm; 2) Design partitioned distributed observer in each partition; 3) Design distributed control law.

Before achieving these steps, we first specify two basic assumptions and an important lemma.

As mentioned in Section I and Subsection II-B, it is unnecessary to require each local observer to reconstruct the states of the whole large-scale system. Theoretically, each agent only needs to estimate part of states required by its local control law. Therefore, in order to establish a distributed observer that can only estimate the state information required by the local control law, we need to partition the network and ensure that all partitions of each agent contain all its physical network neighbors. To illustrate it in more detail, we introduce several simple examples.

In Figure 3a), there is a simple network system with $6$ nodes. One may recognize its partition by observation easily: it could be partitioned into three categories with $\{1,2,3\},\{4,5,6\}$, and $\{3,4\}$. With this partition, the physical network neighbors of all nodes have been included in their partitions. For example, $\mathcal{N}_{3}=\{1,2,4\}$, and partitions to which node $3$ belonging are $\{1,2,3\}$ and $\{3,4\}$. Obviously, $\mathcal{N}_{3}\subset\{1,2,3\}\cup\{3,4\}$. Similarly, Figure 3b) is a star network system with $9$ nodes. One can partition it with $\{1,2\}$, $\{1,3\}$, $\{1,4\}$, $\{1,5\}$, $\{1,6\}$, $\{1,7\}$, $\{1,8\}$, $\{1,9\}$ and all agents’ physical neighbors are covered by their partitions. As for Figure 3c), the acquisition of partitions is not so intuitive, but we can still partition it with $\{1,2,3,4\}$, $\{5,6,7,8\}$, and $\{3,5\}$ after the observation and analysis. Through the above examples, we know the basic idea and function of partition, but we cannot obtain reasonable partition results through observation for large-scale systems. Therefore, a reasonable partition algorithm is necessary for distributed observers of large-scale systems.

To this end, we propose a partition method based on the greedy algorithm. Before showing the algorithm details, some notations are introduced. $\mathcal{O}_{k}\subset\mathcal{V}$ is defined as the $k$th partition of the large-scale system, and $\mathscr{P}_{i}$ denotes the set of partitions that containing node $i$. For example, in Figure 3c), $\mathcal{O}_{1}=\{1,2,3,4\}$, $\mathcal{O}_{2}=\{5,6,7,8\}$, and $\mathcal{O}_{3}=\{3,5\}$. In addition, $\mathscr{P}_{1}=\{\mathcal{O}_{1}\}$, and $\mathscr{P}_{3}=\{\mathcal{O}_{1},\mathcal{O}_{3}\}$. Set $\mathcal{O}(\mathcal{P}_{i})=\bigcup_{\mathcal{O}_{j}\in\mathscr{P}_{i}}\mathcal{O}_{j}$, and denote $D(\mathscr{P}_{i})=\sum_{\mathcal{O}_{j}\in\mathscr{P}_{i}}|\mathcal{O}_{j}|$ the total number of agents that need to be estimated by local observer on the $i$th agent. Let $Pa(i,j)$ be a set of the nodes belonging to the shortest path between $i$ and $j$ in communication network $\forall i,j\in\mathcal{V}$. For example, in Figure 3c), $Pa(1,4)=\{1,2,3,4\}$. Besides, we define $r_{1},r_{2},\cdots,r_{N}$ for nodes belonging to $\mathcal{V}$, and define the symbol $\preceq$ by $r_{i}\preceq r_{j}$ if $|\mathcal{C}_{r_{i}}|<|\mathcal{C}_{r_{j}}|$, or $|\mathcal{C}_{r_{i}}|=|\mathcal{C}_{r_{j}}|$ and $|\mathcal{N}_{r_{i}}|\geq|\mathcal{N}_{r_{j}}|$. In addition, define $s_{1},s_{2},\cdots,s_{N}$ for nodes belonging to $\mathcal{V}$, and further define $\succeq$ by $s_{i}\succeq s_{j}$ if $|\mathcal{C}_{s_{i}}|>|\mathcal{C}_{s_{j}}|$, or $|\mathcal{C}_{s_{i}}|=|\mathcal{C}_{s_{j}}|$ and $|\mathcal{N}_{s_{i}}|\geq|\mathcal{N}_{s_{j}}|$.

Now, one can see Algorithm 1 for the developed partition method. For the convenience of readers to understand the algorithm, we will briefly describe the algorithm process here.

Step 1: Sort $r_{i},~{}i=1,\ldots,N$ based on symbol $\preceq$.

Step 2: Starting from the minimum $r_{i}$. Each node chooses its partitions according to the greedy algorithm in sequence (The larger the degree of node in the communication network, the more partition schemes can be selected. Therefore, priority should be given to the node with the smallest communication network degree).

Step 3: Sort $s_{i},~{}i=1,\ldots,N$ based on symbol $\succeq$.

Step 4: Starting from the maximum $s_{i}$. Each node considers whether to merge several partitions according to two criteria (Line 27–29 in Algorithm 1 and their details are shown in (D2)) in sequence (In communication networks, nodes with larger degrees are more likely to be forced to join many redundant partitions. Therefore, priority is given to nodes with larger degrees to determine whether to remove some redundant partitions through merging).

Note that the partition algorithms described in Algorithm 1 and Algorithm 2 actually solve a multi-objective optimization problem because each node has its own desired partition result, but the desired optimal partitions among different nodes are conflicting. In the complete version of this article, we prove that the partition results obtained through Algorithm 1 and Algorithm 2 are Pareto solutions to this multi-objective optimization problem.

We have the following discussions regarding Algorithm 1 and 2.

(D1) The node constraint conditions can be satisfied. The guarantee of constraint conditions (It is required that the union of all partitions where each agent is located should include all its physical network neighbor agents) is mainly in the first part “establishing partitions” Algorithm 1 because its “Partition initialization” serves the purpose of allowing each node to select partitions to cover its physical network neighboring nodes.

(D2) The central part of Algorithm 1 adopts the idea of a greedy algorithm. According to (D1), the feasible partition scheme under the constraint conditions has been reached with the first part of Algorithm 1. However, since the first part starts from the node with the smallest degree in the communication network, the node with a large degree (hub node) may have an excessive computational burden. The second part of the algorithm is mainly employed to reduce the computational burden of hub nodes. The developed method allows the hub nodes’ neighbors in the communication network to share the computing burden equally by merging the partitions of hub nodes. Whether it is shared equally depends on:

1) The increment of the local observer dimension of any neighbor node cannot be greater than the reduction of the local observer dimension of the hub node;

2) The total dimension of the local observers of the hub node and its neighbors should be reduced compared to that before the merging partition.

Therefore, the merging part will further optimize the partition results obtained by partition initialization.

(D3) Detailed description of “merging partition” part. Suppose a hub node wants to merge partitions $\mathcal{O}_{p_{m1}},\ldots,\mathcal{O}_{p_{m\ell}}$. After the partitions are merged, the local observers of all nodes in the merged partition $\mathcal{O}_{p_{m1}}$ must estimate all the states involved in $\mathcal{O}_{p_{m1}}$. Hence, the dimensions of local observers of all nodes are equal after merging, which can be denoted as $D^{*}(\mathscr{P}_{s_{i}})=|\bigcup_{k=1}^{\ell}\mathcal{O}_{p_{mk}}|$ where $s_{i}$ is the index of the hub node. Therefore, condition 1) in (D2) indicates $D^{*}(\mathscr{P}_{s_{i}})-D(\mathscr{P}_{l})\leq D(\mathscr{P}_{s_{i}})-D^{*}(\mathscr{P}_{s_{i}})$ for $l=1,\ldots,\ell_{s_{i}}$. Furthermore, after merging partitions, there are $D^{*}(\mathscr{P}_{s_{i}})$ nodes in the partition, and each node needs to estimate all states of $D^{*}(\mathscr{P}_{s_{i}})$ nodes. Therefore, condition 2) can be formulated as $\left(D^{*}(\mathscr{P}_{s_{i}})\right)^{2}\leq\sum_{l\in\bigcup_{k=1}^{\ell}\mathcal{O}_{p_{mk}}}D(\mathscr{P}_{l})$. The aforementioned explains the source of step $27$ and step $28$ in Algorithm 1.

(D4) Algorithm 1 has polynomial time complexity.

First, focus on the first part of the algorithm. The complexity of this part is reflected in the number of calculations of lines $7$ to line $9$. They are the core contents of “establishing partitions” and are calculated with at most $N\cdot\frac{1}{N}\sum_{i=1}^{N}|\mathcal{N}_{i}|$ times. Note that the average degree $\frac{1}{N}\sum_{i=1}^{N}|\mathcal{N}_{i}|$ is scarce relative to the total number $N$ in a large-scale network.

Second, we calculate the time complexity of Algorithm 2. Since Algorithm 2 is the $18$th line of Algorithm 1, its complexity is also a part of the complexity of Algorithm 1. Its core steps include line $4$ and line $6$, and they are calculated with at least $N\cdot\frac{1}{N}\sum_{i=1}^{N}\zeta_{i}$ times. According to the partition selection method, the number of partitions of each node will not exceed its communication network degree. Hence,

where $\kappa$ stands for the proportion of the average degree of communication network to $N$. Note that $2^{\kappa N}-\kappa N-1=O(N)$ when $\kappa\leq\frac{1}{N}\log_{2}[N+1]\ll N$.

Third, core steps (line $25,26,30$) of the last loop (line $15$ to line $34$) of Algorithm 1 should be calculated with $N\cdot\frac{1}{N}\sum_{i=1}^{N}\ell_{s_{i}}$ times. Besides,

In summary, the complexity of Algorithm 1 is

Therefore, Algorithm 1 has the polynomial time complexity.

The following text explains Algorithm 1 and 2 in more detail with an example. Figure 4 shows the physical and communication network considered in this example, and The detailed steps of partitioning this network are listed in Figure 4 and Figure 5, where the former shows the initial partitioning steps and the latter shows the merging steps. To facilitate readers’ understanding, some key steps will be interpreted.

(I1) We focus on the area containing nodes $1,\ldots,10$. This area is taken as an example to show why partition design should be carried out in the order of $r_{1}\preceq r_{2}\preceq\cdots\preceq r_{N}$. In light of the sorting rule, node $1$ with $\mathcal{N}_{1}=2$ and $\mathcal{C}_{1}=1$ is the first node to be considered. Based on line $7$ to line $10$, we know $\mathcal{O}_{1}=\{1,2,5\}$. Hence, $\mathscr{P}_{1}=\{\mathcal{O}_{1}\}$, $\mathscr{P}_{2}=\{\mathcal{O}_{1}\}$, $\mathscr{P}_{5}=\{\mathcal{O}_{1}\}$. Subsequently, partitions $\mathcal{O}_{2}=\{3,4\}$, $\mathcal{O}_{3}=\{6,7\}$, $\mathcal{O}_{4}=\{5,8,9\}$, $\mathcal{O}_{5}=\{6,10\}$, $\mathcal{O}_{6}=\{10,11\}$ can be selected for nodes $4$, $7$, $8$, and $10$ in order. Then, note that $1,5\in\mathcal{O}(\mathscr{P}_{2})$; thus $\mathcal{O}_{7}=\{2,3,6\}$ is necessary included in $\mathscr{P}_{2}$. Besides, since $\mathcal{N}_{3}$ has been contained in $\mathcal{O}(\mathscr{P}_{3})$, node $3$ needs not to select partitions any more. This reflects the advantages of the proposed node sorting rule: the node with a larger degree in the communication network selects the partition in the later order, which neither affects its partition selection nor interferes with the partition selection of the previous node, but greatly reduces the computational load (most of the required partitions have been selected in advance). The same situation can also be seen at node $6$. However, the unreasonable order of nodes will lead to a large number of partitions with high repetition (See in I2).

(I2) We focus on nodes $42$, $43$, and $44$. Their selection partition order is $42\preceq 43\preceq 44$. Node $42$ selects its partition as $\{40,41,42,43\}$. Hence, only node $44$ remains in $\mathcal{N}_{43}\backslash\mathcal{O}(\mathscr{P}_{43})$. It means $\{43,44\}$ should be added into $\mathscr{P}_{43}$. However, since $41\in\mathcal{N}_{44}$, $\mathscr{P}_{44}$ must include a partition $\{41,43,44\}$. It leads to a new partition to be added to node $43$, which has completed the partition selection before that. More unreasonably, two highly repetition partitions $\{41,43,44\},\{43,44\}$ exist at the same time in $\mathscr{P}_{43}$ and $\mathscr{P}_{44}$. The reason for this phenomenon is that $|\mathcal{N}_{44}\backslash\mathcal{O}(\mathscr{P}_{44})|>|\mathcal{N}_{43}\backslash\mathcal{O}(\mathscr{P}_{43})|$ after the node $42$ selects its partitions. The above analysis shows that we have the advantage of allowing the node with a smaller communication network degree and larger physical network degree to select partitions preferentially. Otherwise, highly similar partitions like $\{41,43,44\}$ and $\{43,44\}$ will appear in large numbers. In addition, the above analysis also shows that a more reasonable sorting rule should be: node $i$ will preferentially select the partition if $|\mathcal{N}_{i}\backslash\mathcal{O}(\mathscr{P}_{i})|>|\mathcal{N}_{j}\backslash\mathcal{O}(\mathscr{P}_{j})|$ when $|\mathcal{C}_{j}|=|\mathcal{C}_{i}|$. However, this sort rule means that one has to sort the nodes again after a node selects its partition, which is adverse to the implementation of the algorithm. Therefore, we do not improve the algorithm from the perspective of the remaining physical network neighbor nodes but use the merging strategy to make up for this problem.

(I3) Figure 5 displays the steps of merging partitions. Note that the actual calculation is not complex, although the complexity of the partition merging part is $O(N^{2})$. It is because after the partitions of some nodes are merged, many other nodes that initially needed to merge partitions no longer need to perform the merging steps. For example, in Figure 4, all nodes $41,43,44$ need to merge partitions. However, $M_{s_{i}}$ (defined by Algorithm 2) with respect to node $43$ and $44$ are both empty after $41$ merging its partitions, and thus they need not perform the merging steps anymore.

This subsection designs distributed observer for each partition based on the partition method in the previous subsection. Suppose that $\mathcal{O}_{p}$ is a partition belonging to $\mathscr{P}_{i}$, and then the state observer on the $i$th agent to itself takes the form of:

where $\hat{x}_{ii}^{(p)}$ is the estimation of $x_{i}$ generated by observers on agent $i$ in partition $\mathcal{O}_{p}$; $\bar{x}_{ij}=1/N_{j,\mathscr{P}_{i}}\cdot\sum_{\mathcal{O}_{p}\in\mathscr{P}_{i}}\hat{x}_{ij}^{(p)}$ with $N_{j,\mathscr{P}_{i}}$ being the number of occurrences of $j$ in $\mathcal{O}(\mathscr{P}_{i})$; $\hat{x}_{ij}^{(p)}$ stands for the state estimation of the $j$th subsystem generated by the $i$th agent. $\Gamma_{\epsilon}=diag\{\epsilon^{n-1},\ldots,\epsilon,1\}$ is the high-gain matrix with $\epsilon=1/\theta$ and $\theta$ being the high-gain parameter; $H_{i}\in\mathbb{R}^{n\times p}$ and $\gamma$ are, respectively, the observer gain and coupling gain; $\tilde{P}_{i}=\Gamma_{\epsilon}P_{i}\Gamma_{\epsilon}^{-1}$ is the so-called weighted matrix and $P_{i}$ is a symmetric positive definite matrix that will be designed later; $\hat{u}_{ii}^{(p)}$ is the control input relying on $\bar{x}_{ij}$.

The dynamics of $\hat{x}_{li}^{(p)}$ $\forall l\in\mathcal{O}_{p}$ can be expressed as

where $\hat{x}_{li}^{(p)}$ is the estimation of $x_{i}$ generated by observers on agent $l$ in partition $\mathcal{O}_{p}$, and $\hat{u}_{li}$ is the control input relying on $\bar{x}_{lj}$.

Denote $e_{ii}^{(p)}=x_{i}-\hat{x}_{ii}^{(p)}$ and $e_{li}^{(p)}=\hat{x}_{li}^{(p)}-x_{i}$, we have

where $\bar{e}_{lj}=1/N_{j,\mathscr{P}_{i}}\cdot\sum_{\mathcal{O}_{p}\in\mathscr{P}_{l}}e_{lj}^{(p)}$; and $\bar{u}_{i}$ is the actual control law employed in the closed-loop system.

State feedback control law can be employed in the large-scale system (3) and (4). By observing the dynamics of the $i$th subsystem (1) and (2), the globally asymptotically stable control law gives rise to

where $K_{ij}$ is designed so that $A+BK$ is a Hurwitz matrix with $K=[K_{ij}]_{i,j=1}^{N}$. However, (12) is the state feedback control law with precise system states. Hence, one should replace them with the state estimations generated by the observers on the $i$th agent. In the case of the traditional distributed-observer-based distributed control law [2, 9, 10, 11], the exact states of (12) can be directly replaced by state estimations of the $i$th local observer. However, since this paper studies large-scale systems and does not want every agent to reconstruct all the states of the whole system, the concept of partition is introduced and thus leads to a fusion estimation problem (See Remark 4. For example, agent $31$ in the example of Figure 4 and Figure 5 has estimated its states three times in three partitions). Hence, $\bar{x}_{ii}=1/|\mathscr{P}_{i}|\cdot\sum_{\mathcal{O}_{p}\in\mathscr{P}_{i}}\hat{x}_{ii}^{(p)}$, and $\bar{x}_{li}=1/N_{i,\mathscr{P}_{l}}\cdot\sum_{\mathcal{O}_{p}\in\mathscr{P}_{l}}\hat{x}_{li}^{(p)}$ (note that $1/N_{i,\mathscr{P}_{i}}=1/|\mathscr{P}_{i}|$) are expected to be employed in the control law of the $i$th subsystem, i.e.,