Optimal network topology design in multi-agent systems for efficient average consensus

The problem considered in the present article is optimal design of network topologies in multi-agent systems in order to make communication on the network as efficient as possible for the continuous-time average-consensus protocol. The network design problem can be posed in two different ways. (1) Assuming that the maximum communication cost, i.e. the maximum number of communication links, is known, the goal is to find the network topology which results in the fastest convergence to the consensus (in presence of communication time delays on the links). (2) If a minimum performance of the protocol is required, the design problem can be posed as finding the network with lowest possible communication cost which fulfills the required performance. In both approaches, we formulate the problem of finding the optimal communication graph among a class of directed graphs, strongly balanced digraphs, as a Mixed Integer Semidefinite Program (MISDP). By solving this MISDP, the optimal graph and the weights on communication links are obtained.