Published in: Automatica
Authors: Jin Gyu Lee and Hyungbo Shim
DOI: 10.1016/j.automatica.2020.108952 (Open Access)
Abstract: The behavior of heterogeneous multi-agent systems is studied when the coupling matrices are possibly all different and/or singular, that is, its rank is less than the system dimension. Rank-deficient coupling allows exchange of limited state information, which is suitable for the study of multi-agent systems under output coupling. We present a coordinate change that transforms the heterogeneous multi-agent system into a singularly perturbed form. The slow dynamics is still a reduced-order multi-agent system consisting of a weighted average of the vector fields of all agents, and some sub-dynamics of agents. The weighted average is an emergent dynamics, which we call a blended dynamics. By analyzing or synthesizing the blended dynamics, one can predict or design the behavior of a heterogeneous multi-agent system when the coupling gain is sufficiently large. For this result, stability of the blended dynamics is required. Since stability of the individual agent is not asked, the stability of the blended dynamics is the outcome of trading off the stability among the agents. It can be seen that, under the stability of the blended dynamics, the initial conditions of the individual agents are forgotten as time goes on, and thus, the behavior of the synthesized multi-agent system is initialization-free and is suitable for plug-and-play operation. As a showcase, we apply the proposed tool to four application problems; distributed state estimation for linear systems, practical synchronization of heterogeneous van der Pol oscillators, estimation of the number of nodes in a network, and a problem of distributed optimization.

This work is a continued effort of CDSL to the emergent behavior that arises as we enforce arbitrary precision approximate (or practical) synchronization to a heterogeneous network, where an extension to rank-deficient coupling and its application is provided. A key coordinate transformation for this characterization is given in the paper. For more technical details, I refer to the paper.

A problem of interest

In this paper, we analyze the behavior of the heterogeneous multi-agent system

$\dot{x}_i = f_i(t, x_i) + kB_i\sum_{j \in \mathcal{N}_i} \alpha_{ij}(x_j - x_i) \in \mathbb{R}^n, \quad i \in \mathcal{N},$

$\dot{x}_i = f_i(t, x_i) + k\sum_{j \in \mathcal{N}_i} \alpha_{ij}(C_jx_j - C_ix_i) \in \mathbb{R}^n, \quad i \in \mathcal{N},$

without actually solving the entire network. Of particular interest is when the matrix $B_i \in \mathbb{R}^{n\times n}$ or $C_i \in \mathbb{R}^{n\times n}$ is symmetric and positive semi-definite and when the coupling gain $k$ is sufficiently large. The approach is to consider the extreme case when $k \to \infty$ because it gives a clue to approximate the behavior of the given network when the coupling gain $k$ is finite but sufficiently large. In particular, in the end, we convert the network into a singularly perturbed system, and approximate the emergent network behavior by its quasi-steady-state subsystem, which we call “blended dynamics.” By assuming stability only on the blended dynamics, this approximation gets uniform in the infinite time interval as in the singular perturbation theory.

Why should we study this problem: Synthesis perspective

Motivated by the approximation of the emergent collective network behavior we study in this paper, one can design the blended dynamics first such that the approximation behaves as desired, and then, synthesize a multi-agent system such that it has the desired blended dynamics. For a concrete example, see below. One straightforward application will be to make the network synchronize. Synchronization achieved in this way does not depend on the initial conditions from the stability imposed on the blended dynamics. This will be particularly useful for the so-called plug-and-play operation, which means, that agents can join or leave the network on-line. Another benefit of the synchronization achieved in this way is that it is robust against external disturbance, noise, and/or uncertainty in the agent dynamics.

Why should we study this problem: Analysis perspective

First of all, the obtained observation may be interpreted as a mathematical model of the fact that unique group behavior can appear even if none of the individuals displays that behavior. In addition, as we require only the stability of the blended dynamics for the stability of the entire network, it could show that in a typical situation where there are many stable agents in a group, a few unstable (or malfunctioning, or even malicious) agents may coexist without perturbing the stability of the group. Again, this approach may explain how the stability of each agent is traded off among the connected agents, or even explain a way to maintain the public good against malicious agents by a majority of good neighbors.

Blended dynamics in special cases

To give a glimpse on how the blended dynamics look like, we represent the blended dynamics in special cases here.

First of all, if all the coupling matrices $B_i$ or $C_i$ are identical to a positive semi-definite matrix, then we have the following form of blended dynamics:

$\dot{\hat{z}}_i = Z_o^Tf_i(t, Z_o\hat{z}_i + W_o\hat{s}) \quad\quad \in \mathbb{R}^{n - p_o}, \quad i \in \mathcal{N}, \\ \dot{\hat{s}} = \frac{1}{N}\sum_{i=1}^NW_o^Tf_i(t, Z_o\hat{z}_i + W_o\hat{s}) \in \mathbb{R}^{p_o},$

where $B_i = \begin{bmatrix} W_o & Z_o \end{bmatrix}\begin{bmatrix} \Lambda_o^2 & 0 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} W_o^T \\ Z_o^T\end{bmatrix}$ or $C_i = \begin{bmatrix} W_o & Z_o \end{bmatrix}\begin{bmatrix} \Lambda_o^2 & 0 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} W_o^T \\ Z_o^T\end{bmatrix}$ , $\begin{bmatrix} W_o & Z_o\end{bmatrix}$ is an orthogonal matrix and $\Lambda_o$ is a positive definite matrix.

Then, the network state $x_i$ is approximated by $Z_o\hat{z}_i + W_o\hat{s}$ .

On the other hand, if all the coupling matrices $B_i$ or $C_i$ are positive definite matrices, which could be heterogeneous, then we have the following form of blended dynamics:

$\dot{\hat{s}} = \left(\sum_{i=1}^N B_i^{-1}\right)^{-1}\sum_{i=1}^N B_i^{-1}f_i(t, \hat{s}),$

$\dot{\hat{s}} = \left(\sum_{i=1}^N C_i^{-1}\right)^{-1}\sum_{i=1}^N f_i(t, C_i^{-1}\hat{s}).$

In this case, we have that the network state $x_i$ approximated by $\hat{s}$ or $C_i^{-1}\hat{s}$ .

Finally, as the combination of these two, if all the coupling matrices $B_i$ or $C_i$ are identical to a positive definite matrix, then we have the following form of blended dynamics:

$\dot{\hat{s}} = \frac{1}{N}\sum_{i=1}^N f_i(t, \hat{s}),$

where the network state $x_i$ is approximated by $\hat{s}$ .

Application of the blended dynamics

A simple application of the blended dynamics theory in the synthesis is a network that estimates the number of agents. For this, by the blended dynamics we know, we can simply construct a network as

$\dot{n}_1(t) = -n_1(t) + 1 + k\sum_{j \in \mathcal{N}_1} (n_j(t) - n_1(t)), \\ \dot{n}_i(t) = 1 + k\sum_{j \in \mathcal{N}_i}(n_j(t) - n_i(t)), \quad i = 2, \dots, N.$

The blended dynamics, in this case, can be found as

$\dot{\hat{s}}(t) = -\frac{1}{N}\hat{s}(t) + 1,$

which converges to the number of agents $N$ . Now, residing to the approximation result given above, we can see that each agent $n_i$ finds the number of agents in the network in a distributed manner, when the coupling gain is sufficiently large. Note that for any given $N$ , we have that the blended dynamics is contractive.

Other applications include

analysis of the emergent behavior of a network of heterogeneous Van der Pol oscillators,
distributed state estimation,
distributed least-squares solver,
distributed median solver,
and distributed optimization.

We refer to the following references for these applications.

1.Heterogeneous Van der Pol oscillators under strong coupling
Jin Gyu Lee and Hyungbo Shim
In Proc. of 57th IEEE Conference on Decision and Control, 2018
https://doi.org/10.1109/CDC.2018.8618901

2.Behavior of a network of heterogeneous Liénard systems under strong output coupling
Jin Gyu Lee and Hyungbo Shim
In Proc. of 11th IFAC Symposium on Nonlinear Control Systems, 2019
https://doi.org/10.1016/j.ifacol.2019.11.788

3. A distributed algorithm that finds almost best possible estimate under non-vanishing and time-varying measurement noise
Jin Gyu Lee and Hyungbo Shim
IEEE Control Systems Letters, 2019
https://doi.org/10.1109/LCSYS.2019.2923475

4. Fully distributed resilient state estimation based on distributed median solver
Jin Gyu Lee, Junsoo Kim, and Hyungbo Shim
under review, IEEE Transactions on Automatic Control (under minor revision)
available at https://arxiv.org/abs/2002.06605

Future direction

A particular future interest lies on fully decentralized design, as the current paper, requires that a common parameter $k$ has to be agreed upon all the agents, which depends on the global information such as the network topology or the individual vector field if our goal is for the network to behave approximately as the blended dynamics with a specified performance.

An interesting direction includes adaptive coupling, where especially the funnel control has been adopted for further study. We refer to the following references for this future direction.

5.A preliminary result on synchronization of heterogeneous agents via funnel control
Hyungbo Shim and Stephan Trenn
In Proc. of 54th IEEE Conference on Decision and Control, 2015
https://doi.org/10.1109/CDC.2015.7402538

6. Utility of edge-wise funnel coupling for asymptotically solving distributed consensus optimization
Jin Gyu Lee, Thomas Berger, Stephan Trenn, and Hyungbo Shim
accepted, In Proc. of European Control Conference, 2020

A Tool for Analysis and Synthesis of Heterogeneous Multi-agent Systems under Rank-deficient Coupling