FenixEdu™

Dissertação

{en_GB=Multiagent System Optimization} {} EVALUATED

Detalhes: {pt=O consenso é uma ferramenta importante em processamento distribuído. O objectivo dos algoritmos de consenso é calcular a média das medidas de cada agente da rede. À medida que estes trocam informação, a informação que guardam aproxima-se do valor da média. Algoritmos de consenso têm duas vertentes: canais de comunicação e velocidade. Devem chegar rápido ao resultado, usando o mínimo de canais. Neste trabalho, desenvolvemos algoritmos que melhoram o estado da arte nestas duas vertentes, separadamente. Na primeira parte, desenhámos um método que reduz o número de canais de comunicação tendo um impacto pequeno na velocidade de convergência. Através de técnicas de optimização convexa e da teoria da dualidade, reduziram-se o número de canais em cerca de 80%, sofrendo apenas um impacto de 5% na performance da rede. Ou seja, encontrou-se um conjunto de canais que mantêm um rápido processamento da informação. Na segunda parte, desenhámos métodos para acelerar a velocidade de convergência. Para redes assimétricas (onde a comunicação bidireccional não é garantida), este é um problema difícil de resolver, pois o raio espectral é uma função não convexa. Propusemos uma série de aproximações convexas que aumentam a velocidade de algoritmos de consenso em cerca de 45%, para o mesmo número de canais de comunicação., en=In distributed multi-agent networks, consensus is a core tool. The goal of any consensus algorithm is to compute the average of the measurements that each agent holds. As they exchange information the average should be reached at each agent. Consensus algorithms use two key resources: communications and time. They thrive to be fast while using a modicum of communication channels. We develop consensus algorithms that substantially improve the state-of-art in these two directions, separately. In the first part, we design methods that reduce the number of communication channels needed, while having a negligible impact on the speed of the consensus algorithm. By exploring tools from convex optimization and duality theory, we are able to trim the number of channels up to 80%, while paying only about a 5% penalty in convergence speed. In other words, for a given network topology, our methods spot a subset of the available channels that still sustain a fast processing of information. In the second part, we develop methods that accelerate the speed of convergence. We address this problem for the challenging setup of asymmetric networks, i.e., networks in which agents may not communicate bidirectionally. This task translates into the minimization of the non-convex spectral radius of asymmetric matrices whose entries are constrained to a convex set. We propose several reformulations of this non-convex problem that lead to efficient convex approximations and boost the speed of existing consensus algorithms by 45% with the same number of channels.}
Keywords: {pt=Consenso, algoritmos distribuídos, redes esparsas, optimização convexa, minimização do raio espectral, en=Consensus, distributed algorithms, sparse networks, convex optimization, spectral radius minimization}

Discussão: maio 19, 2016, 11:0