Design of Heterogeneous Multi-agent System for Distributed Computation

When constructing a distributed network, sometimes there is a need for each agent to know global information such as the number of agents in the network without resorting to a centralized unit. In such circumstances, Theorem 2.1 can be employed to design a distributed network that estimates the number of participating agents, under the assumption that there is one agent (whose index is 1 without loss of generality) who always takes part in the network. Suppose that agent $1$ integrates the following scalar dynamics:

while all others integrate

where $N$ is unknown to the agents. Then, the blended dynamics is obtained as

This implies that the resulting emergent motion $s(t)$ converges to $N$ as time goes to infinity. Then, it follows from Theorem 2.1 that each state $x_{i}(t)$ approaches arbitrarily close to $N$ with a sufficiently large $k$. Hence, by increasing $k$ such that the estimation error is less than $0.5$, and by rounding $x_{i}(t)$ to the nearest integer, each agent gets to know the number $N$ as time goes on.

By resorting to a heterogeneous network, we were able to impose stable emergent collective behavior that makes possible for individuals to estimate the number of agents in the network. Note that the initial conditions do not affect the final value of $x_{i}(t)$ because they are forgotten as time tends to infinity due to the stability of the blended dynamics. This is in sharp contrast to other approaches such as shames2012distributed where the average consensus algorithm is employed, which yields the average of individual initial conditions, to estimate $N$. While their approach requires resetting the initial conditions whenever some agents join or leave the network during the operation, the estimation of the proposed algorithm remains valid (after some transient) in such cases because the blended dynamics (8) remains contractive for any $N\geq 1$. Therefore, the proposed algorithm achieves the plug-and-play operation. Moreover, when the maximum number $N_{\max}$ of agents is known, the decentralized design is also achieved. Further details are found in donggil .

Distributed algorithms have been developed in various fields of study so as to divide a large computational problem into small-scale computations. In this regard, finding a solution of a given large linear equation in a distributed manner has been tackled in recent years mou2013fixed ; mou2015distributed ; anderson2015decentralized . Let the equation be given by

where $A\in\mathbb{R}^{M\times n}$ has full column rank, $x\in\mathbb{R}^{n}$, and $b\in\mathbb{R}^{M}$. We suppose that the total of $M$ equations are grouped into $N$ equation banks, and the $i$-th equation bank consists of $m_{i}$ equations so that $\sum_{i=1}^{N}m_{i}=M$. In particular, we write the $i$-th equation bank as

where $A_{i}\in\mathbb{R}^{m_{i}\times n}$ is the $i$-th block rows of the matrix $A$, and $b_{i}\in\mathbb{R}^{m_{i}}$ is the $i$-th block elements of $b$. The problem of finding a solution to (10) (in the sense of least-squares when there is no solution) is dealt with in wang2017distributed ; shi2016distributed ; shi2017network ; liu2017network . Most notable among them are shi2016distributed and shi2017network , in which they proposed a distributed algorithm given by

Here, we analyze (11) in terms of Theorem 2.2. In particular, the blended dynamics of the network (11) is obtained as

which is equivalent to the gradient descent algorithm of the optimization problem

that has a unique minimizer $(A^{T}A)^{-1}A^{T}b$; the least-squares solution of (9). Thus, Theorem 2.2 asserts that each state $x_{i}$ approximates the least-squares solution with a sufficiently large $k$, and the error can be made arbitrarily small by increasing $k$.

The idea of designing a network based on the gradient descent algorithm of an optimization problem, as in the previous subsection, can be used for most other distributed optimization problems. Among them, a particularly interesting example is the problem of finding a median, which is useful, for instance, in rejecting outliers under redundancy.

For a collection $\mathcal{R}$ of real numbers $r_{i}$, $i=1,2,\cdots,N$, their median is defined as a real number that belongs to the set

where $r_{i}^{s}$’s are the elements of the set $\mathcal{R}$ with its index being rearranged (sorted) such that $r_{1}^{s}\leq r_{2}^{s}\leq\cdots\leq r_{N}^{s}$. With the help of this relaxed definition of the median, finding a median $s$ of ${\mathcal{R}}$ becomes solving an optimization problem

Then, a gradient descent algorithm given by

will solve this minimization problem, where $\text{sgn}(s)$ is $1$ if $s>0$, $-1$ if $s<0$, and $0$ if $s=0$. In particular, the solution $s$ satisfies

Motivated by this, we propose a distributed median solver, whose individual dynamics of the agent $i$ uses the information of $r_{i}$ only:

Now, the algorithm (15) finds a median approximately by exchanging their states $x_{i}$ only (not $r_{i}$). Further details can be found in jgleeTAC19 .

As another application of distributed optimization, let us consider an optimization problem

where $\lambda_{i}\in{\mathbb{R}}$ is the decision variable, $J_{i}$ is a strictly convex $C^{2}$ function, and $\underline{\lambda}_{i}$, $\overline{\lambda}_{i}$, and $d_{i}$ are given constants. A practical example is the economic dispatch problem of electric power, in which $d_{i}$ represents the demand of node $i$, $\lambda_{i}$ is the power generated at node $i$ with its minimum $\underline{\lambda}_{i}$ and maximum $\overline{\lambda}_{i}$, and $J_{i}$ is the generation cost.

A centralized solution is easily obtained using Lagrangian and Lagrange dual functions. Indeed, it can be shown that the optimal value is obtained by $\lambda_{i}^{*}=\theta_{i}(s^{*})$ where

in which $(dJ_{i}/d\lambda_{i})^{-1}(\cdot)$ is the inverse function of $(dJ_{i}/d\lambda_{i})(\cdot)$, $\text{sat}(s,a,b)$ is $s$ if $a\leq s\leq b$, $b$ if $b<s$, and $a$ if $s<a$. The optimal $s^{*}$ maximizes the dual function $g(s):=\sum_{i=1}^{N}J_{i}(\theta_{i}(s))+s(d_{i}-\theta_{i}(s))$, which is concave so that $s^{*}$ can be asymptotically obtained by the gradient algorithm:

A distributed algorithm to solve the optimization problem approximately is to integrate

because the blended dynamics of (18) is given by

Obviously, (19) is the same as the centralized solver (17) except the scaling of $1/N$, which can be compensated by scaling (18). By Theorem 2.2, the state $x_{i}(t)$ of each node approaches arbitrarily close to $s^{*}$ with a sufficiently large $k$, and so, we obtain $\lambda_{i}^{*}$ approximately by $\theta_{i}(x_{i}(t))$ whose error can be made arbitrarily small. Readers are referred to yun2018initialization , which also describes the behavior of the proposed algorithm when the problem is infeasible so that each agent can figure out that infeasibility occurs. It is again emphasized that the initial conditions are forgotten and so the plug-and-play operation is guaranteed. Moreover, each agent can design its own dynamics (18) only with their local information, so that decentralized design is achieved, except the global information $k$. In particular, the function $\theta_{i}$ can be computed within the agent $i$ from the local information such as $J_{i}$, $\underline{\lambda}_{i}$, and $\overline{\lambda}_{i}$. Therefore, the proposed solver (18) does not exchange the private information of each agent (except the dual variable $x_{i}$).

Consider a network of heterogeneous Liénard systems modeled as

where $f_{i}(\cdot)$ and $g_{i}(\cdot)$ are locally Lipschitz. Suppose that the output and the diffusive coupling input are given by

For (23) with (24), we claim that synchronous and oscillatory behavior is obtained with a sufficiently large $k$ if the averaged Liénard systems given by

has a stable limit cycle. This condition may be interpreted as the blended version of the condition for a stand-alone Liénard system $\ddot{z}+f(z)\dot{z}+g(z)=0$ to have a stable limit cycle. Note that this condition implies that, even when some particular agents $\ddot{z}_{i}+f_{i}(z_{i})\dot{z}_{i}+g_{i}(z_{i})=0$ do not yield a stable limit cycle, the network still can exhibit oscillatory behavior as long as the average of $(f_{i},g_{i})$ yields a stable limit cycle. It is seen that stability of individual agents can be traded among agents in this way, so that some malfunctioning oscillators can oscillate in the oscillating network as long as there are a majority of good neighbors. The frequency and the shape of synchronous oscillation is also determined by the average of $(f_{i},g_{i})$.

To justify the claim, we first realize (23) and (24) with $y_{i}:=az_{i}+\dot{z}_{i}$ as

and compute its blended dynamics (21) as

To see whether this $(N+1)$-th order blended dynamics has a stable limit cycle, we observe that, with $a>0$, all $\hat{z}_{i}(t)$ converge exponentially to a common trajectory $\hat{z}(t)$ as time goes on. Therefore, if the blended dynamics has a stable limit cycle, which is an invariant set, it has to be on the synchronization manifold $\mathcal{S}$ defined as

Projecting the blended dynamics (26) to the synchronization manifold $\mathcal{S}$, i.e., replacing $\hat{z}_{i}$ with $\hat{z}$ in (26) for all $i\in\mathcal{N}$, we obtain a second-order system

Therefore, (27) should have a stable limit cycle if the blended dynamics has a stable limit cycle. It turns out that (27) is a realization of (25) by $s=az+\dot{z}$, and thus, existence of a stable limit cycle for (25) is a necessary condition for the blended dynamics (26) to have a stable limit cycle. Further analysis, given in jingyuNOLCOS , proves that the converse is also true. Then, Theorem 3.2 holds with the limit cycle of (26) as the compact set ${\mathcal{A}}_{b}$, and thus, with a sufficiently large $k$, all the vectors $(z_{i}(t),\dot{z}_{i}(t))$ stay close to each other, and oscillate near the limit cycle of the averaged Liénard system (25). This property has been coined as ‘phase cohesiveness’ in Dorfler14 .

Consider a linear system

where $\chi\in{\mathbb{R}}^{n}$ is the state to be estimated, $o$ is the measurement output, and $n$ is the measurement noise. It is supposed that there are $N$ distributed agents, and each agent $i$ can access the measurement $o_{i}\in{\mathbb{R}}^{q_{i}}$ only (where often $q_{i}=1$). We assume that the pair $(G,S)$ is detectable, while each pair $(G_{i},S)$ is not necessarily detectable as in bai2011distributed ; kim2016distributed . Each agent is allowed to communicate its internal state to its neighboring nodes. The question is how to construct a dynamic system for each node that estimates $\chi(t)$. See, e.g., mitra2016approach ; kim2016distributedlue for more details on this distributed state estimation problem.

To solve the problem, we first employ the detectability decomposition for each node, that is, for each pair $(G_{i},S)$. With $p_{i}$ being the dimension of the undetectable subspace of the pair $(G_{i},S)$, let $[Z_{i},W_{i}]$ be an orthogonal matrix, where $Z_{i}\in{\mathbb{R}}^{n\times(n-p_{i})}$ and $W_{i}\in{\mathbb{R}}^{n\times p_{i}}$, such that

and the pair $(\bar{G}_{i},\bar{S}_{i})$ is detectable. Then, pick a matrix $\bar{U}_{i}\in{\mathbb{R}}^{(n-p_{i})\times q_{i}}$ such that $\bar{S}_{i}-\bar{U}_{i}\bar{G}_{i}$ is Hurwitz. Now, individual agent $i$ can construct a local partial state observer, for instance, as

to collect the information of the state $\chi$ as much as possible from the available measurement $o_{i}$ only; each agent $i$ can obtain a partial information $b_{i}$ about $\chi$ in the sense that

where $z_{i}$ denotes the estimation error that converges to zero by (28) if $n_{i}=0$. When we collect (29) and write them as

detectability of $(G,S)$ implies that ${\rm col}(Z_{1}^{T},\dots,Z_{N}^{T})=A$ has full-column rank. Therefore, the least-squares solution $\hat{\chi}(t)$ of $A\hat{\chi}(t)=b(t)$ can generate a unique estimate of $\chi(t)$. This reminds us of the problem in Section 2.2; finding the least-squares solution in a distributed manner.

Based on the discussion above, we propose a distributed state estimator for the given linear system as

where $b_{i}$ comes from (28), and both $\kappa$ and $k$ are design parameters. Note that the least-squares solution $\hat{\chi}$ for $A\hat{\chi}(t)=b(t)$ is time-varying, and so, in order to have asymptotic convergence of $\hat{\chi}_{i}(t)$ to $\chi(t)$ (when there is no noise $n$), we had to add the generating model of $\chi(t)$ in (31), inspired by the internal model principle.

To justisfy the proposed distributed state estimator (28) and (31), let us denote the state estimation error as $y_{i}:=\hat{\chi}_{i}-\chi$, then we obtain the error dynamics for the partial state observer (28) and the distributed observer (31) as

The blended dynamics (21) is obtained as

For a sufficiently large gain $\kappa$, the blended dynamics (3.2) becomes contractive, and thus, Theorem 3.1 guarantees that the error variables $(z_{i}(t),y_{i}(t))$ of (32) behave like $(\hat{z}_{i}(t),s(t))$ of (3.2). Moreover, if there is no noise $n$, Theorem 3.2 asserts that all the estimation errors $(z_{i}(t),y_{i}(t))$, $i\in{\mathcal{N}}$, converge to zero because ${\mathcal{A}}_{x}=\{0\}$. Even with the noise $n$, the proposed observer achieves almost best possible estimate whose detail can be found in JGLeeLCSS20 .