多智能体网络中的动态一致平均算法及其应用
发布时间：2018-11-09 09:41
【摘要】：本文研究多智能体网络中的一类重要问题——动态一致平均问题,具体而言,即网络中所有智能体动态地跟踪一组时变参考输入信号的均值,并使得每个智能体的跟踪结果都等于该组时变信号的均值。本文研究的则是如何分布式地求解该问题。而分布式计算又可分为有中心分布式计算与无中心分布式计算两大类,后者相较于前者具有通信更均衡、算法更鲁棒、隐私保护性更强等优点,因而无中心分布式信息处理的应用前景更广泛。本文首先介绍了几种现有的无中心分布式动态一致平均算法,然后在前人的基础上设计开发了一种新的无中心分布式求解动态一致平均的算法DDAC。 DDAC相较于前人设计的算法,具有更好的参数可调性,在大量的数值实验中,也具有更高的收敛精度。动态一致平均算法拥有很多重要的应用,除了用于需要直接动态跟踪时变信号的一些实际应用(位置跟踪、编队控制等)之外,本文还原创性地提出将动态一致平均算法用于处理一些优化问题的子问题,并重点以低秩矩阵补全问题为例来说明这一原创性想法的有效性与先进性。本文对低秩矩阵补全问题进行了研究,并在前人提出的一种集中式求解矩阵补全问题的算法基础上,设计开发出了两种新的无中心分布式矩阵补全算法D-LMaFit与DDAC-LMaFit。在此研究过程中,我们指出将有中心分布式(并行)实现的算法改造为无中心分布式算法的关键与难点,即如何使用无中心分布式的算法取代网络中心节点。对此我们给出答案,即动态一致平均算法可以解决该难点。我们使用了两种动态一致平均算法(前人提出的EXTRA与本文中新设计的DDAC算法)解决该难点,分别对应地得到前述两种算法。并且,考虑到实际应用中有对于数据的隐私保护的需要,我们分析了分布式低秩矩阵补全问题中的隐私保护问题,并以D-LMaFit算法为例,证明了对于一系列能够将其更新式写为一个线性时不变系统的算法,若网络拓扑满足一定条件,则该算法具有对于隐私保护的性能。作为更多扩展,结合我们提出的动态一致平均算法可以替代中心节点的求平均操作,我们还对两种一阶优化算法——梯度下降法与邻近点梯度法的无中心分布化实现进行了研究,并分别设计得到了若干有效的新的无中心分布式梯度下降法(DDAC-GD算法、EXTRA-GD算法与FODAC-GD算法)与新的无中心分布式邻近点梯度法(DDAC-PG算法、EXTRA-PG算法与FODAC-PG算法)。全文致力于研究无中心分布式动态一致平均算法,设计了一种新的有效的算法；并对如何将有中心分布式(并行)实现的算法通过求解动态一致平均子问题,设计为无中心分布式的算法进行了讨论,相应地设计了若干新的用于求解不同问题的无中心分布式算法。大量的数值实验则表明了算法的有效性。本文的研究为设计无中心分布式算法提供了新思路。
[Abstract]:In this paper, we study a class of important problems in multi-agent networks, that is, the dynamic uniform averaging problem. In particular, all agents in the network dynamically track the mean value of a set of time-varying reference input signals. The tracking results of each agent are equal to the mean of the time-varying signals. In this paper, we study how to solve the problem distributed. Distributed computing can be divided into two categories: distributed computing with center and distributed computing without center. Compared with the former, the latter has the advantages of more balanced communication, more robust algorithm, stronger privacy protection, and so on. Therefore, the application prospect of distributed information processing without center is more extensive. This paper first introduces several existing distributed dynamic uniform averaging algorithms without center, and then designs and develops a new algorithm, DDAC., for solving dynamic uniform averaging without center on the basis of previous researches. Compared with the previous algorithms, DDAC has better parameter adjustability and higher convergence accuracy in a large number of numerical experiments. The dynamic uniform averaging algorithm has many important applications, except for some practical applications (position tracking, formation control, etc.) that require direct dynamic tracking of time-varying signals. This paper also proposes to apply the dynamic uniform averaging algorithm to the subproblems of some optimization problems, and takes the low rank matrix complement problem as an example to illustrate the validity and advanced nature of this original idea. In this paper, the low rank matrix complement problem is studied, and on the basis of a centralized algorithm to solve the matrix complement problem, two new non-central distributed matrix complement algorithms D-LMaFit and DDAC-LMaFit. are designed and developed. In the course of this research, we point out the key and difficulty of transforming the distributed algorithm with the center (parallel) into the distributed algorithm without center, that is, how to replace the center node of the network with the algorithm without center distribution. We give the answer that the dynamic uniform averaging algorithm can solve the problem. We use two dynamic uniform averaging algorithms (EXTRA proposed by previous authors and DDAC algorithm designed in this paper) to solve this problem and obtain the two algorithms mentioned above respectively. Considering the need of data privacy protection in practical application, we analyze the privacy protection problem in distributed low rank matrix complement problem, and take D-LMaFit algorithm as an example. It is proved that for a series of algorithms which can be written as a linear time-invariant system, if the network topology satisfies certain conditions, the algorithm has the property of privacy protection. As a further extension, the dynamic uniform averaging algorithm proposed by us can replace the averaging operation of the central node. We also study the realization of two first-order optimization algorithms, i.e. gradient descent method and adjacent point gradient method, and design several effective non-central distributed gradient descent methods (DDAC-GD), respectively. EXTRA-GD algorithm and FODAC-GD algorithm) and new non-center distributed adjacent point gradient method (DDAC-PG algorithm, EXTRA-PG algorithm and FODAC-PG algorithm). This paper is devoted to the research of distributed uniform averaging algorithm without center, and designs a new and effective algorithm. And how to design the distributed algorithm without center by solving the dynamic uniform average subproblem is discussed. Several new distributed algorithms are designed to solve different problems. A large number of numerical experiments show the effectiveness of the algorithm. The research in this paper provides a new idea for the design of distributed algorithm without center.
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
本文编号：2320048
[Abstract]:In this paper, we study a class of important problems in multi-agent networks, that is, the dynamic uniform averaging problem. In particular, all agents in the network dynamically track the mean value of a set of time-varying reference input signals. The tracking results of each agent are equal to the mean of the time-varying signals. In this paper, we study how to solve the problem distributed. Distributed computing can be divided into two categories: distributed computing with center and distributed computing without center. Compared with the former, the latter has the advantages of more balanced communication, more robust algorithm, stronger privacy protection, and so on. Therefore, the application prospect of distributed information processing without center is more extensive. This paper first introduces several existing distributed dynamic uniform averaging algorithms without center, and then designs and develops a new algorithm, DDAC., for solving dynamic uniform averaging without center on the basis of previous researches. Compared with the previous algorithms, DDAC has better parameter adjustability and higher convergence accuracy in a large number of numerical experiments. The dynamic uniform averaging algorithm has many important applications, except for some practical applications (position tracking, formation control, etc.) that require direct dynamic tracking of time-varying signals. This paper also proposes to apply the dynamic uniform averaging algorithm to the subproblems of some optimization problems, and takes the low rank matrix complement problem as an example to illustrate the validity and advanced nature of this original idea. In this paper, the low rank matrix complement problem is studied, and on the basis of a centralized algorithm to solve the matrix complement problem, two new non-central distributed matrix complement algorithms D-LMaFit and DDAC-LMaFit. are designed and developed. In the course of this research, we point out the key and difficulty of transforming the distributed algorithm with the center (parallel) into the distributed algorithm without center, that is, how to replace the center node of the network with the algorithm without center distribution. We give the answer that the dynamic uniform averaging algorithm can solve the problem. We use two dynamic uniform averaging algorithms (EXTRA proposed by previous authors and DDAC algorithm designed in this paper) to solve this problem and obtain the two algorithms mentioned above respectively. Considering the need of data privacy protection in practical application, we analyze the privacy protection problem in distributed low rank matrix complement problem, and take D-LMaFit algorithm as an example. It is proved that for a series of algorithms which can be written as a linear time-invariant system, if the network topology satisfies certain conditions, the algorithm has the property of privacy protection. As a further extension, the dynamic uniform averaging algorithm proposed by us can replace the averaging operation of the central node. We also study the realization of two first-order optimization algorithms, i.e. gradient descent method and adjacent point gradient method, and design several effective non-central distributed gradient descent methods (DDAC-GD), respectively. EXTRA-GD algorithm and FODAC-GD algorithm) and new non-center distributed adjacent point gradient method (DDAC-PG algorithm, EXTRA-PG algorithm and FODAC-PG algorithm). This paper is devoted to the research of distributed uniform averaging algorithm without center, and designs a new and effective algorithm. And how to design the distributed algorithm without center by solving the dynamic uniform average subproblem is discussed. Several new distributed algorithms are designed to solve different problems. A large number of numerical experiments show the effectiveness of the algorithm. The research in this paper provides a new idea for the design of distributed algorithm without center.
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【参考文献】
相关期刊论文 前1条
1 林安亚;凌青;;多智能体网络中的分布式动态一致平均算法[J];电子技术;2016年06期
，本文编号：2320048
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/2320048.html
