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

1. Problema di Riferimento

Il lavoro affronta il problema del consenso (accordo sullo stato) in sistemi multi-agente (MAS) lineari. Nonostante i risultati esistenti, la ricerca identifica due criticità principali che richiedono ulteriore attenzione:

1. Progettazione Decentralizzata: La maggior parte dei protocolli esistenti, sebbene distribuiti nell'esecuzione, richiede procedure di progettazione centralizzate o vincoli severi (es. tutti gli agenti devono utilizzare gli stessi guadagni di controllo), limitando la flessibilità.
2. Minimizzazione delle Comunicazioni: Utilizzare tutte le informazioni dai vicini riduce l'efficienza e può causare congestione di rete. L'obiettivo è ridurre il numero di collegamenti di comunicazione necessari mantenendo la stabilità del sistema.

Il paper si pone l'obiettivo di progettare un protocollo di consenso che sia completamente decentralizzato (ogni agente calcola i propri guadagni indipendentemente) e che richieda solo i collegamenti minimi necessari, basati su un albero di copertura diretto (Directed Spanning Tree - DST).

2. Metodologia

L'approccio proposto si basa su una trasformazione lineare innovativa e sulla teoria della stabilizzazione decentralizzata.

• Trasformazione basata sul DST:

  • Viene costruito un albero di copertura diretto (DST) $T$ all'interno della topologia di comunicazione $G$. Si assume che il nodo radice sia $N$ e che ogni altro nodo $i$ abbia un unico genitore $k_i$.
  • Viene definita una trasformazione lineare che mappa gli stati degli agenti in stati degli archi fondamentali ($y_i = x_{k_i} - x_i$).
  • Grazie al Lemma 1, qualsiasi stato di bordo ($x_j - x_i$) può essere rappresentato linearmente come combinazione degli stati degli archi fondamentali del DST.

• Riformulazione del Problema:

  • Il problema del consenso globale viene trasformato equivalentemente in un problema di stabilizzazione dell'uscita decentralizzata.
  • Il sistema globale viene descritto in forma centrale $\dot{y} = A^*y + B^*u$, dove l'uscita misurata $z$ dipende solo dalle informazioni disponibili sul DST.
  • La condizione necessaria e sufficiente per il consenso è legata all'assenza di Modi Fissi Decentralizzati (DFM) con parte reale non negativa nel sistema trasformato.

• Progettazione del Protocollo:

  • Invece di utilizzare le informazioni di tutti i vicini, ogni agente utilizza solo l'informazione dal proprio genitore nel DST (o una combinazione specifica se il nodo radice non è una radice nella topologia originale).
  • Vengono proposti due casi di controllo:
    1. Caso 1 (Radice del DST è radice della topologia): Gli agenti non-radice usano solo l'informazione dal genitore nel DST. Il sistema risultante ha una matrice di stato triangolare superiore a blocchi. La stabilità è garantita se ogni blocco diagonale ($A - w_{ik_i}BK_i$) è Hurwitz.
    2. Caso 2 (Radice del DST non è radice della topologia): Il nodo radice del DST riceve informazioni da un vicino nella topologia originale. Viene utilizzata una matrice a blocchi più complessa. Per garantire la stabilità in modo decentralizzato, viene applicato il Teorema dei Cerchi di Gerschgorin per blocchi. Questo permette di progettare i guadagni $K_i$ localmente, assicurando che i cerchi di Gerschgorin associati agli autovalori si trovino nel semipiano sinistro.

3. Contributi Chiave

1. Progettazione Completamente Decentralizzata: A differenza delle metodologie tradizionali che richiedono guadagni di controllo identici per tutti gli agenti o una progettazione centrale, questo metodo permette a ciascun agente di calcolare il proprio guadino $K_i$ in modo indipendente, basandosi solo sulle informazioni locali e sui parametri del proprio genitore nel DST.
2. Minimizzazione dei Collegamenti di Comunicazione: Il protocollo richiede che ogni agente comunichi solo con il proprio genitore nell'albero di copertura (un singolo collegamento in entrata), riducendo drasticamente il carico di dati rispetto all'uso di tutti i vicini.
3. Criterio di Stabilità Locale: L'uso del Teorema di Gerschgorin permette di derivare condizioni di stabilità verificabili localmente, evitando la necessità di conoscere l'intera matrice del sistema globale durante la progettazione.
4. Generalità: Il metodo è applicabile a sistemi lineari generici e non richiede vincoli specifici sulla topologia oltre alla presenza di un DST.

4. Risultati

• Teoremi Principali:
  • Teorema 1: Fornisce la condizione necessaria e sufficiente per il consenso in termini di rango della matrice del sistema e assenza di DFM.
  • Teorema 2: Dimostra che se la radice del DST è anche una radice nella topologia originale, la stabilità è garantita se i singoli blocchi diagonali sono Hurwitz.
  • Teorema 3: Estende il risultato al caso generale (radice del DST non radice della topologia), fornendo condizioni basate sui cerchi di Gerschgorin per la selezione decentralizzata dei guadagni.
• Esempi Numerici:
  • Sono stati presentati due esempi con 4 e 6 agenti rispettivamente.
  • Le simulazioni mostrano che, utilizzando guadagni diversi per ogni agente e comunicando solo attraverso i collegamenti del DST, gli stati degli agenti convergono asintoticamente allo stesso valore (consenso).
  • È stato dimostrato che anche quando il nodo radice non riceve informazioni dai vicini (caso in cui $K_N=0$), il sistema raggiunge comunque il consenso, con gli altri agenti che tracciano lo stato della radice.

5. Significato e Impatto

Questo lavoro offre un contributo significativo alla teoria del controllo distribuito:

• Efficienza delle Risorse: Riducendo il numero di collegamenti di comunicazione, il metodo aumenta l'affidabilità della rete (meno punti di fallimento) e riduce il consumo di banda e energia.
• Flessibilità Operativa: La natura completamente decentralizzata della progettazione permette di scalare il sistema e di gestire agenti eterogenei o con capacità computazionali diverse, senza bisogno di un'unità centrale di coordinamento per il calcolo dei parametri.
• Nuovo Paradigma: Sposta l'attenzione dalla stabilità basata sull'errore di stato globale alla stabilizzazione decentralizzata dell'uscita, offrendo una via alternativa e potente per la sintesi dei controllori in sistemi multi-agente complessi.

In sintesi, il paper dimostra che è possibile raggiungere il consenso in sistemi multi-agente con la minima infrastruttura di comunicazione possibile (un albero di copertura) e con una progettazione dei controllori che non richiede alcuna coordinazione centrale, rendendo il sistema più robusto, scalabile ed efficiente.