Decentralized design of consensus protocols with minimal communication links based on directed spanning tree

Resumo Técnico: Projeto Descentralizado de Protocolos de Consenso com Links de Comunicação Mínimos Baseados em Árvore Geradora Direcionada

Autores: Yangzhou Chen e Lanhao Zhao
Instituição: Universidade de Tecnologia de Pequim, China

1. Problema Investigado

O artigo aborda o problema de consenso em sistemas multiagentes (MAS), onde o objetivo é que todos os agentes alcancem um estado comum assintoticamente. O foco principal reside em duas limitações críticas das abordagens existentes:

1. Projeto Centralizado: A maioria dos protocolos distribuídos exige que os parâmetros de controle (como matrizes de ganho) sejam determinados por procedimentos centralizados ou que todos os agentes utilizem os mesmos ganhos, o que reduz a flexibilidade e a adaptabilidade.
2. Sobrecarga de Comunicação: Protocolos tradicionais frequentemente exigem que cada agente comunique-se com todos os seus vizinhos simultaneamente. Isso gera grandes volumes de dados, podendo causar congestionamento na rede e reduzir a confiabilidade.

O objetivo do trabalho é desenvolver uma abordagem de projeto totalmente descentralizado que utilize apenas o mínimo número possível de links de comunicação (baseado em uma estrutura de árvore) para garantir o consenso.

2. Metodologia

A metodologia proposta baseia-se em uma transformação linear estruturada e na teoria de modos fixos descentralizados (DFM).

• Transformação Baseada em Árvore Geradora Direcionada (DST):

  • O sistema de comunicação é modelado como um grafo direcionado. Assume-se a existência de uma Árvore Geradora Direcionada (DST) dentro desse grafo.
  • Os autores constroem uma transformação linear que mapeia o problema de consenso original para um problema de estabilização de saída descentralizada.
  • Em vez de considerar o estado de todas as arestas do grafo, o método foca apenas nas "arestas fundamentais" da DST. O estado de qualquer aresta no grafo completo pode ser representado linearmente como uma combinação das arestas fundamentais da DST.

• Formulação do Problema de Estabilização:

  • O sistema dinâmico dos agentes é transformado em um sistema centralizado de estados de arestas fundamentais.
  • A condição necessária e suficiente para o consenso é derivada em termos de Modos Fixos Descentralizados (DFM). O sistema atinge o consenso se e somente se os modos fixos descentralizados do sistema transformado não possuírem autovalores no semiplano direito (ou no eixo imaginário, dependendo da estabilidade marginal).

• Projeto do Protocolo de Controle:

  • Caso 1 (Raiz na Topologia Original): Se a raiz da DST também for uma raiz no grafo original, o protocolo de controle para cada agente utiliza apenas a informação do seu único pai na DST. O ganho de controle é projetado localmente para tornar a matriz dinâmica local Hurwitz.
  • Caso 2 (Raiz não na Topologia Original): Se a raiz da DST não for uma raiz no grafo original (ou seja, ela recebe informações de vizinhos), o protocolo para a raiz utiliza a soma das informações dos seus vizinhos na DST.
  • Para garantir a estabilidade global sem conhecimento global, os autores utilizam o Teorema do Círculo de Gerschgorin aplicado a matrizes em bloco. Isso permite que cada agente projete seu próprio ganho de feedback localmente, garantindo que os círculos de Gerschgorin do sistema global fiquem no semiplano esquerdo.

3. Contribuições Principais

1. Minimização de Links de Comunicação: O trabalho demonstra que o consenso pode ser alcançado utilizando apenas as informações dos vizinhos definidos pela DST, ignorando outros vizinhos no grafo original. Isso reduz drasticamente a quantidade de dados transmitidos e aumenta a robustez da rede.
2. Projeto Totalmente Descentralizado: Diferente de métodos que exigem ganhos idênticos para todos os agentes ou sintonização centralizada, este método permite que cada agente projete sua própria matriz de ganho de feedback ($K_i$) de forma independente, baseada apenas em informações locais e na estrutura da DST.
3. Critério Necessário e Suficiente: A derivação de uma condição rigorosa baseada em Modos Fixos Descentralizados (DFM) para a estabilidade do sistema de consenso.
4. Aplicabilidade Geral: A abordagem é apresentada como genérica, capaz de lidar com diferentes topologias e dinâmicas de agentes, superando as limitações de métodos anteriores que restringem os parâmetros a faixas específicas.

4. Resultados e Validação

Os resultados foram validados através de exemplos numéricos:

• Exemplo 1: Um sistema de 4 agentes onde a raiz da DST é uma raiz no grafo original. O consenso foi alcançado com ganhos diferentes para cada agente, utilizando apenas a informação do pai na árvore.
• Exemplo 2: Um sistema de 6 agentes onde a raiz da DST não é uma raiz no grafo original (recebe informações de um vizinho). O método de Gerschgorin foi aplicado para projetar os ganhos localmente.
• Simulações: As figuras do artigo mostram que, mesmo com ganhos heterogêneos e comunicação mínima (apenas links da DST), os estados de todos os agentes convergem para o mesmo valor assintoticamente.
• Comparação: O estudo de caso 2 demonstra que, mesmo quando a raiz não recebe informações de vizinhos (caso limite), os outros agentes conseguem rastrear a raiz, validando a robustez da estrutura.

5. Significância e Impacto

Este trabalho é significativo para a área de controle de sistemas multiagentes por:

• Eficiência de Recursos: Reduz a carga computacional e de comunicação, tornando os protocolos viáveis para redes com largura de banda limitada ou com restrições energéticas (ex: sensores sem fio, drones).
• Escalabilidade: A natureza descentralizada do projeto permite que o sistema escale para um grande número de agentes sem a necessidade de um coordenador central complexo.
• Flexibilidade de Projeto: Ao permitir ganhos de controle diferentes para cada agente, o método oferece maior liberdade de sintonia para lidar com heterogeneidade nos agentes (dinâmicas diferentes).
• Fundamentação Teórica: Estabelece uma ponte clara entre a teoria de estabilização de saída descentralizada e o consenso em redes, oferecendo uma ferramenta matemática robusta para o projeto de protocolos futuros.

Em resumo, o artigo propõe uma solução elegante e eficiente para o problema de consenso, provando que a complexidade da comunicação pode ser minimizada ao máximo (apenas uma árvore geradora) sem sacrificar a estabilidade do sistema, desde que o projeto seja feito de forma descentralizada utilizando transformações lineares apropriadas.