Practical Synchronization of Heterogeneous Multi-agent System Using Adaptive Law for Coupling Gains

Published in: American Control Conference (ACC) 2018
Authors: Seungjoon Lee, Hyeonjun Yun, and Hyungbo Shim
Abstract: Practical synchronization of the heterogeneous multi-agent system is studied in this paper. In particular, we propose an adaptive law to adjust the coupling gains to achieve practical synchronization in a fully distributed manner without the need of any global information such as the total number of agents in the network or the algebraic connectivity of the communication topology. In addition, a distributed protocol is proposed such that the performance of practical synchronization becomes independent of any global information as well as the addition of new agent.

Practical synchronization of the heterogeneous multi-agent system has been the main topic of interest for CDSL. For example, see this page or this recent paper for our work. Our approaches to the problem also led us to find a solution to distributed optimization problem as shown in this paper.

However, there are additional issues when we try to apply our methods to solve for more practical problem. One main issue is how can we design the coupling gain. In particular, we should design coupling gain in a distributed manner in order to execute algorithms in the multi-agent scenario. This is the question we have dealt with in this paper, which will be explained briefly in this post.

Brief Introduction to Blended Dynamics

Before jumping into the main results of the paper, we first need to know the basics of blended dynamics. Consider heterogeneous multi-agent system given by

$$\dot{x}_i = f_i(x_i,t) + u_i$$

where the input $u_i$ is designed as

$$u_i=k \sum_{j \in \mathcal{N}_i} (x_j – x_i).$$

It was shown that (see this paper by J. G. Lee and H. Shim) with sufficiently high coupling gain $k$ , the trajectories of agents achieve practical synchronization. In addition, trajectories (practically) converge to the solution of the blended dynamics which is defined as

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

under appropriate assumptions. This property is useful since the complex behavior of the heterogeneous multi-agent system can be described by the blended dynamics which is much simpler to study.

What is this paper mainly about?

It is nice to know about the behavior of the multi-agent system and its relation to the blended dynamics. However, interesting issues arise if we try to apply it to solve a real-world problem. One main concern in applying blended dynamics is the design of the coupling gain. Specifically, it is hard to determine the actual gain required to achieve practical synchronization. Moreover, even if such gain can be found, it involves global information such as the total number of agents, algebraic connectivity or vector fields of individual agents. For example, the analytic expression for the minimum gain has been proposed for scalar case (see here), but it requires global information as mentioned earlier. Therefore, in order to deploy high gain diffusive coupling, we must have a centralized design procedure despite execution is distributed.

Can this issue be solved? Can we achieve not only the distributed execution but also do it using a decentralized design? This is the question we will try to answer in this paper.

So… How can we achieve practical synchronization using a decentralized design?

Since our solution for practical synchronization is based on high gain coupling, it is natural to think of adaptive methods to adaptively increase the gain until practical synchronization is achieved. Although the idea is straightforward, there are few technical difficulties we must overcome.

1. Practical synchronization of heterogeneous agents

It is well-known that asymptotic synchronization of heterogeneous agents requires a common internal model. Since in our work, we do not assume the existence of such an internal model, we must resort to the practical synchronization.

2. Recover the convergence to the solution of blended dynamics

Achieving practical synchronization alone is not enough. In particular, we would like to recover previous results and let the trajectories of the individual agent to (practically) converge to the solution of the blended dynamics.

Solution from this paper

Keeping these two challenges in our mind, we propose input given by

$$u_i = k_i(t) \sum_{j \in \mathcal{N}_i} (x_j – x_i), \quad \forall i \in \mathcal{N} \\ \qquad \qquad \quad \dot{k}_i = \sum_{j \in \mathcal{N}_i} \sigma_{\gamma_i}(e_{ij}^Te_{ij}) + \sum_{j \in \mathcal{N}_i}(k_j – k_i), \quad k_i(0) > 0 \label{eq:gain_dyn}$$

where $e_{ij} := x_i - x_j$ and $\sigma_{\gamma_i}:[0,+\infty) \rightarrow [0,+\infty)$ is the deadzone function with the threshold value of $\gamma_i^2$ which is shown below.

The proposed input is similar to the static diffusive coupling which was considered in previous studies. However, a major difference is now that the coupling gains are time-varying and assigned to an individual agent, instead of being a common value across agents. Dynamics of time-varying coupling gains mainly consists of two terms: an adaptive term and consensus term.

The adaptive term given by $\sum_{j \in \mathcal{N}_i} \sigma_{\gamma_i}(e_{ij}^Te_{ij})$ takes the relative state difference of an agent with its neighbors and applies the deadzone function. This tends to increase the coupling gain as long as the relative error is larger than the threshold value. It is important to note the usage of deadzone function in the adaptive term. Since we are aiming for practical synchronization, coupling gains are no longer increased when the states of agents are sufficiently close to each other, and in particular when the error is less than the threshold value.

The consensus term given by $\sum_{j \in \mathcal{N}_i}(k_j - k_i)$ is the typical diffusive coupling among coupling gains of agents. This will tend to synchronize coupling gains among agents. Addition of consensus term on the coupling gains is also a major difference from existing works. Consensus term will drive coupling gains to achieve synchronization which will help us to recover the convergence to the blended dynamics.

In the paper, it is proven that under some technical assumptions, practical synchronization of agents as well as the asymptotic synchronization of the coupling gains are achieved.

Where can we apply this solution?

A problem where the proposed scheme can be used is the economic dispatch problem (EDP). EDP is a distributed optimization problem consisting of $N$ agents. Each agent has power demand and generation with different generation cost. The objective of the EDP is to minimize the overall cost function while meeting the overall supply and demand balance. EDP can be formulated as an optimization problem which can be written as

$$\min_{x_i} \sum_{i=1}^N J_i(x_i)$$

such that

$$\underline{x}_i \leq x_i \leq \bar{x}_i, \qquad \sum_{i=1}^N p_i^d = \sum_{i=1}^N x_i$$

holds where $J_i$ is strictly convex function, $p_i^d,\underline{x}_i,\bar{x}_i$ are the power demand of individual agent, lower and upper bound of the generation capacity. This problem was recently investigated in CDSL (see our previous result). Following their development, it is equivalent to solve

$$\max_{\lambda} g(\lambda) = \sum_{i=1}^N g_i(\lambda)$$

where $\lambda$ is the dual variable, $g(\lambda)$ is the dual function and $g_i(\lambda)$ can be computed by an agent only using the local information. In order to solve the dual problem in a distributed manner, we can execute following dynamics:

$$\dot{\lambda}_i^c = \frac{dg_i(\lambda_i^c)}{d\lambda} + k \sum_{j \in \mathcal{N}_i} (\lambda_j^c -\lambda_i^c)$$

where $\lambda_i^c$ is the estimate of $\lambda$ by an agent $i$ . Note blended dynamics of the proposed distributed algorithm is given by

$$\dot{s} = \frac{1}{N} \sum_{i=1}^N \frac{dg_i(s)}{d\lambda}$$

which is exactly same as the centralized gradient method for solving the dual problem. Therefore, we may obtain that $\lambda_i^c(t)$ practically converges to the optimal solution of the dual problem.

However, this approach still requires a centralized design for deployment of the algorithm, since the coupling gain $k$ must be designed using the global information.

Instead, we can use dynamics proposed in our paper. Then, the solution is written as

$$\dot{\lambda}_i = \frac{dg_i(\lambda_i)}{d\lambda} + k_i(t) \sum_{j \in \mathcal{N}_i} (\lambda_j -\lambda_i) \\ \qquad \qquad \dot{k}_i = \sum_{j \in \mathcal{N}_i} \sigma_{\gamma_i}(e_{ij}^2) + \sum_{j \in \mathcal{N}_i}(k_j – k_i), \quad k_i(0) > 0.$$

Applying our result from this paper, we can obtain practical synchronization of dual variables as well as asymptotic synchronization of coupling gains. Moreover, it can be shown that trajectories indeed converge to the trajectory of the blended dynamics, which is exactly the centralized gradient method. Therefore, the optimal solution can be recovered.

Therefore, we can see that the proposed solution can be used to solve the distributed optimization problem with a completely decentralized design.

Additional Results

In the paper, we further discuss the performance of the practical synchronization when the number of agents in the network is not necessarily fixed. In particular, we considered a scenario where a new agent may continue to join the network. It is shown that the overall synchronization performance degrades with the addition of new agents. In order to solve this issue, we have proposed a distributed algorithm to maintain the synchronization performance despite the addition of new agents by locally updating threshold values of deadzone function.

You may also find presentation slides used for the conference at this link.