Optimal strategies in the average consensus problem |
| |
Authors: | Jean-Charles Delvenne Ruggero Carli Sandro Zampieri |
| |
Affiliation: | 1. Université catholique de Louvain, Department of Applied Mathematics, 4 Avenue Lemaître, 1348 Louvain-la-Neuve, Belgium;2. Department of Information Engineering, Università di Padova, Via Gradenigo 6/a, 35131 Padova, Italy |
| |
Abstract: | Let a set of communicating agents compute the average of their initial positions, where every agent is restricted to communicate to a given small number of other agents (average consensus problem). We prove that the optimal topology of communication is given by a de Bruijn graph. Consensus is then reached in finitely many steps. This solution is valid when the number of agents is an exact power of the out-degree of the communication graph. We introduce an algebraic tool, the shifted Kronecker product, and a more general family of strategies, also based on a de Bruijn communication graph. Those strategies are compared to Cayley strategies in terms of the speed of convergence. We also show that quantized communication between the agents still allows finite convergence, to a consensus, which is not in general the average of the initial positions. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|