Network topology control for connectivity maintenance and information spreading manipulation in multi-robot systems

Abstract

A cooperação é uma propriedade desejada para muitos sistemas interconectados, uma vez que lhes permite resolver tarefas complexas de forma distribuída. O aumento no uso de processos cooperativos (caracterizados pelo compartilhamento de informações) diminui o esforço individual exigido por cada agente. No entanto, esta diminuição do esforço local aumenta a complexidade do sistema em sua totalidade, devido aos acoplamentos intrínsecos entre os agentes que podem originar comportamentos emergentes, os quais são altamente dependentes da topologia de comunicação. Um destes comportamentos, chamado consenso, é necessário para se garantir a coesão entre as informações trocadas. Tal comportamento é essencial para sistemas multi-agentes que são empregados para executar tarefas cooperativas, uma vez que seus indivíduos devem compartilhar informações coesas, que garantam que seus colegas de equipe estejam tentando resolver o mesmo problema. Assim, para manter a cooperação, um sistema interligado deve assegurar a coesão através de dinâmicas de difusão baseadas em consenso. Neste contexto, este trabalho visa dois objetivos distintos ao manipular a topologia de rede de um sistema interconectado composto por agentes autônomos: i) assegurar a conectividade do sistema mesmo quando há falhas em um agente, durante a execução da tarefa cooperativa. ii) controlar a disseminação da informação para dirigir a convergência do consenso, de acordo com a distribuição de informação pretendida para o sistema. Os dois objetivos são abordados separadamente. O primeiro objetivo é resolvido através da solução do Problema do Caixeiro Viajante (TSP) aplicado sobre indicadores de força de sinal em redes sem fio para criar uma topologia virtual bi-conectada em um sistema multiagente. Em seguida, utiliza-se um Controlador Preditivo baseado em Modelo (MPC), executado de forma descentralizada, para aproximar os agentes, transformando os links virtuais em reais e conectando a topologia de rede do sistema. Este procedimento pode transformar qualquer rede conectada em uma rede tolerante a falhas em pelo menos um nodo. Durante o procedimento, uma abordagem baseada em Programação Convexa Sequencial (SCP) aplicada sobre a estrutura do MPC garante a não colisão entre os agentes. Para o segundo objetivo, utiliza-se uma abordagem baseada em Programação Semidefinida (SDP) para se projetar os pesos ótimos da matriz de adjacências da rede, de modo a controlar a convergência de um protocolo distribuído de consenso aleatório para variáveis no domínio de espaço discreto. A teoria de Markov e a inspiração biológica das epidemias são utilizadas para se deduzir um modelo dinâmico de difusão que possa prever como as informações se espalham sob este protocolo de consenso. Além disso, as propriedades de convergência e pontos de equilíbrio do modelo proposto são apresentados em relação à topologia da rede. Finalmente, extensas simulações numéricas e experimentos realizados em uma plataforma robótica comercial avaliam a eficácia das abordagens propostas para ambos os objetivos.

Abstract: Cooperation is a desired property for many interconnected systems since it allows them to solve complex tasks distributively. The increase in the use of cooperative processes (characterised by information sharing) decreases the individual effort demanded by each agent. Nevertheless, this decrease of local effort increases the system complexity as a whole due to the intrinsic couplings between the agents that could give rise to emerging behaviours, which are highly dependent on the communication topology. One of these behaviours, called consensus, is necessary to ensure cohesion among all the exchanged information. This property is an essential and desirable feature in multi-agent systems that are employed to execute cooperative tasks since their individuals must share pieces of information that ensure their teammates are trying to solve the same global problem. Thus, to keep the cooperation, an interconnected system must ensure cohesion through consensus-based diffusion dynamics. In such a context, this work aims two distinct objectives by manipulating the network topology of an interconnected system composed of autonomous agents: i) ensure the system connectivity even when there are faults in one agent, during the performed cooperative task. ii) control the information spreading to drives the consensus convergence, according to the intended information distribution of the system. This thesis undertakes both objectives separately. It solves the first objective through the solution of the Travelling Salesman Problem (TSP) applied over indicators of signal strength in wireless networks to create virtual bi-connected topology in a multi-agent system. Then, it uses a Model Predictive Controller (MPC) executed in a decentralised way to move the agents toward each other, turning the virtual links into real ones and bi-connecting the network topology of the system. This procedure can turn any connected network into a fault-tolerant one. During the procedure, an approach based on Sequential Convex Programming (SCP) applied over the aforementioned MPC framework ensures non-collision among the agents. For the second objective, this thesis uses an approach based on Semidefinite Programming (SDP) to design the optimal weights of a network adjacency matrix, in order to control the convergence of a distributed random consensus protocol for variables at the discrete-space domain. It uses Markov theory and the biological inspiration of epidemics to find out a dynamical spreading model that can predict the information diffusion under this consensus protocol. Also, it presents convergence properties and equilibrium points of the proposed model regarding the network topology. Finally, extensive numerical simulations and experiments performed in a commercial robotic platform evaluate the effectiveness of the proposed approaches for both objectives.