Inoltre esaminiamo una strategia per un filtraggio di Kalman
iterativo. Questo approccio implementa un filtro distribuito in cui, ogni
nodo, dinamicamente esegue istantaneamente la fusione delle misure di
ente un
filtro di kalman locale usando le misure fuse come input e
(asintoticamente) di ottenere le performance di un filtro di Kalman
centralizzato
Nel quar lazione del filtro di
Kalm l’ausilio del
TrueTim per i sistemi
pri neightbors nodi.
input correnti e consente ad ogni nodo di eseguire indipendentem
.
to capitolo, invece, ci concentriamo sulla simu
an distribuito in una rete reale, ottenuta attraverso
e un simulatore MatLab/SimuLink based utilizzato
di controllo real-time.
Scopo di tale studio è verificare quali effetti ha un filtro di Kalman
nella sua versione distribuita, ovvero quando non esiste una
comunicazione completa di “tutti con tutti”, ma ogni nodo della rete è
abilitato a comunicare le proprie misure solo ai pro
4
Capitolo 1
Consenso su Reti di Agenti
1.1 Introduzione
Il coordinamento distribuito in reti di agenti dinamici ha attratto
numerosi ricercatori negli anni recenti, poiché sono molte le aeree di
applicazione dei sistemi multiagenti, tra cui: controllo cooperativo di
veicoli aerei UAVs (veicolo aereo telecomandato e senza equipaggio),
il controllo di formazioni, reti di sensori distribuiti, controllo di gruppi
di satelliti e controllo della congestione in reti di comunicazione.
Il problema del consenso ha una lunga storia nel campo della
scienza dei calcolatori elettronici, in particolare nella teoria
dell’automazione e il calcolo distribuito. In molte applicazioni che
implicano sistemi multiagenti/multiveicoli, i gruppi di agenti hanno
lative al movimento dei singoli agenti. Di
onseguenza, è importante rivolgere l’attenzione al problema del
Lo scopo principale di questo capitolo è analizzare i problemi di
bisogno di concordare su certe quantità di interesse, Tali quantità
possono o non essere re
c
consenso nella sua forma generale, ovvero per reti di agenti dinamici
con information flow diretto con possibilità di malfunzionamento (link
failure) e creazione di nuovi link (cioè a topologia variabile).
consenso in presenza di:
5
• topologia della rete fissata o variabile
• ritardo di comunicazione
• un information flow diretto o indiretto.
In ognuno di questi casi, si fornisce un’analisi di convergenza, inoltre,
si stabilisce un collegamento fra connettività algebrica della rete e le
prestazioni nel raggiungere un accordo.
Infine, si dimostra che il ritardo massimo che può essere
sopportato da una rete di integratori che applicano un protocollo di
consenso lineare è inversamente proporzionale all’autovalore più
grande della topologia di rete o del grado massimo dei nodi della rete.
promesso
do.
Queste considerazioni evidenziano che esiste un com
fondamentale tra prestazioni nel raggiungere un consenso e robustezza
rispetto al ritar
6
1.2 Problema di consenso su grafi
Iniziamo col dare alcune notazioni di carattere matematico.
Consideriamo un digrafo pesato
( )
ε=GV,,A di ordine n con
( ,..., )Vv v= l’insieme dei nodi, VVε = × l’insieme degli archi, e
1 n
[]
ij
A a= la matrice pesata delle adiacenze con gli elementi 0
ij
a ≥ che
rappresentano i pesi associati all’arco che connette il nodo
i
v con il
do
j
v .
Consideriamo inoltre un insieme finito {1,2,...., }n
no
Ι = che rappresenta
l’insieme degli indici dei nodi e denotiamo un arco di G come
(, )
ij i j
evv= .
Agli archi di elementi adiacenti sono associati dei pesi positivi, cioè
0
ij
ij
eaε∈⇔ > , in aggiunta si assume 0
ii
ai= ∀∈Ι .
L’insieme di tutti i nodi vicini al nodo
i
v è indicato come
{:(,)}
ij ij
NvVvvε=∈ ∈, un cluster di nodi è un sottoinsieme JV⊆ ,
l’insieme di cluster vicini tra loro è definito come:
(1) :{:,()}
j
jijiij
vJ
NNvVvJvε
∈
==∈∈ ∈
∪
Consideriamo una rete (,)
x
GGx= con
1
( ,...., )
T
n
x xx= il cui
elemento i -esimo
i
x ∈ℜ rappresenta il valore del nodo
i
v e topologia
(o information flow) G . Per valore del nodo si intende una quantità
fisica per es.: temperatura, altezza, voltaggio, ecc.
7
Se si verifica che
ij
x x= si po’ dire che
i
x e
j
x hanno raggiunto un
accordo. Quindi possiamo estendere il concetto e diciamo che i nodi in
una rete hanno raggiunto un consenso se e solo se
,,
ij
x xij ij=∀∈Ι≠. Ogni qualvolta che tutti i nodi di una rete hanno
dinami
(2)
i
raggiunto un valore comune allora si può indicare quel valore come
valore di decisione di gruppo.
Supponiamo che ogni nodo di un grafo è un agente dinamico con
ca:
(,)
ii
x fxu i Ι =∈
Un
nel qua ca della rete
(,)
grafo (o una rete) dinamico è un sistema dinamico con stato (,)Gx
le il valore di x evolve in accordo alla dinami
x Fxu= con 1,....,in = , dove (,)Fxu rappresenta la
ii
concatenazione dei vettori colonna di ( , ) con 1,....,f xu i n= .
In una rete dinamica l’information flow G è un sistema discreto a
tempo variabile.
Data una funzione :
n
χ ℜ →ℜ di n variabili ,....,
1 n
x x e (0)ax= che
denota lo stato iniziale, il problema del consensusχ − in un grafo
dinamico rappresenta una forma distribuita per calcolare ()aχ
attraverso l’applicazione degli input
i
u ; tale valore dipende solo dallo
tato del nodo
i
v e dei suoi vicini. s
Indichiamo con feedback di stato
(A)
1
( ,...., )
iij jm
ukx x=
8
un protocollo con topologia G se i cluster
1
{ ,...., }
ij jm
J vv= dei nodi
con indice
1
,....,
m
jj∈Ι soddisfano la proprietà che {}
ii i
JvN⊆∪ e in
aggiunta se ||
i
Jni<∀∈Ι (A) può essere chiamato protocollo
distribuito.
L’equazione (A) risolve il problema consensusχ − se e solo se esiste
*
uno stato di equilibrio asintoticamente stabile x di
( , ( )) con 1,....,x Fxkx i n== che soddisfa
*
((0))
i
x xiχ= ∀∈Ι.
In particolare per
1
1
() ()
n
i
i
x media x x
n
χ
=
==
∑
, () ( )
ii
x max xχ = ,
ii
() min( )x xχ = sono chiamati rispettivamente consenso-medio, max-
consenso, min-consenso.
La soluzione del problema del consenso medio è un esempio di
computazione distribuita di funzioni lineari () ()amediaaχ = usando
una rete di agenti dinamici (o integratori). Questo è un obiettivo più
stimolante che raggiungere un consenso con uno stato iniziale a
*
poiché la condizione ()
i
x aiχ= ∀∈Ι
*
collega lo stato del sistema x
allo stato iniziale .
a
9
1.3 Protocollo del consenso
In questo paragrafo si descrivono due protocolli del consenso che
risolvono il problema del consenso in una rete di agenti integratori a
tempo-continuo (CT) con dinamica:
(3) () ()
ii
x tut=
Oppure considerando il modello a tempo discreto (DT)
(4) (1) () ()
iii
x kxkukε+= + con step-size 0ε >
Si considerano 2 scenari:
i) Topologia fissa o variabile senza ritardi di tempo. In questa ipotesi
si utilizza il seguente protocollo di consenso lineare:
(A1) ()
ji
i jji
vN
uaxx
∈
=−
∑
Dove l’insieme dei nodi vicini ()
ii
NNG= è variabile in una rete a
topologia variabile.
ii) Topologia fissa
( )
ε=GV,,A e time-delay 0
ij
τ > in
corrispondenza degli archi
ij
e ε∈ . In queste ipotesi si utilizza il
protocollo del consenso lineare con time-delay:
(A2) (( ) ( )
ji
i jjijiij
vN
uaxt xtτ τ
∈
⎡⎤=−−−
⎣⎦
∑
L'obiettivo principale in questo paragrafo è l’analisi dei
protocolli (A1) e (A2) per gli scenari suddetti. Si mostra, che in ogni
caso, il consenso è asintoticamente raggiunto, inoltre si caratterizza
anche la classe di digrafi che risolvono il problema consenso medio
10
utilizzando protocollo (A1) ed infine si forniscono risultati che
collegano direttamente le prestazioni e la robustezza degli algoritmi di
questi protocolli di consenso agli autovalori della matrice che
rappresenta la topologia della rete.
11
1.3.1 Costo dei protocolli di comunicazione
Un aspetto importante riguardante la realizzazione di attività
coordinate, in un model ema multi agenti è
mantenere limitato il costo della comunicaz
delle m e. Definiamo co di comunicazione/sensing C della
topologia )V
lo distribuito in un sist
ione e dell’interazione
isur sto
(,ε come ε , oppure il numero totale degli archi diretti
del grafo (,)V ε . C viene anche denominato come
unicazione”.
r digr pesati C può ess anche definito com funzione delle
iacenz
)
,1ij=
Evidentemente, il costo comunicazione/sensing dei protocolli con un
grafo diretto di information flow è più piccolo del costo
comunicazione dei protocolli con un grafo indiretto di information
flow. Questa è la ragione principale dell'analisi di protocolli di
consenso per digrafi.
“complessità di
com
Pe afi ere e
ad e:
(7 sgn( )
ij
Ca=
∑
1.4 Reti Dinamiche
Consideriamo il protocollo (A1), lo stato di una rete di agenti
integratori a tempo-continuo (CT) evolve secondo il seguente sistema
lineare:
12
(8 () ()) x tLxt=−
Dove L rappresenta il grafo Laplaciano ricavato dall’information
flow G :
(9) l
⎧
1,
n
ij
kki
ij
aji
=≠
=
⎪
=
ij
aji
⎨
∑
do:
(10) (
k
−≠
⎪
⎩
E’ evidente che la stabilità del sistema (8) dipende dagli autovalori del
grafo Laplaciano le cui proprietà verranno discusse nel paragrafo
successivo.
In una rete con topologia switching (cioè variabile), l’analisi della
convergenza del protocollo A1 è equivalente all’analisi della stabilità
del sistema ibri
() ) ()x t
Lxt=−
Dove (
kk
LG
kst=
)ζ= aplaciano del grafo
k
G appartenente
a un insieme Γ , raccolta finita di digrafi di ordine n con un
insieme di indic
rappresenta il L
con Γ una
i
Γ
Ι⊂] . La mappatura di ():st
Γ
→Ι\ implica un
cambiamento della topologia della rete.
Per quanto ndo il
protocollo (A1) assumono la seguente dinamica:
( 1) ( ) con 1
riguarda gli agenti a tempo discreto applica
x kPxk P L
εε
ε+= =−
dove P
ε
è la matrice di Perron, matrice non negativa e stocastica con
max
1
(0, )
d
ε ∈ .
Indichiamo
max
max
ii
dl= denota il massimo grado del digrafo.
13
1.5 Rete con Topologia Fissata e Grafo Bilanciato.
La seguente classe di digrafi risulta essere ottimale alla
risoluzione di problemi di consenso medio per reti con topologie sia
fissata che variabile. Diamo dapprima una definizione digrafo
bilanciato:
Definizione 1 (Grafo bilanciato):
Definiamo nodo bilanciato
i
v di un digrafo
( )
ε=GV,,A se e solo se
il numero di archi entranti e uscenti si equivalgono, conseguentemente
si definisce grafo bilanciato un digrafo i cui nodi sono tutti bilanciati.
Ogni grafo indiretto è bilanciato.
Teorema 4:
Consideriamo una rete di integratori con una topologia fissata
ε=G(V,,A), con G digrafo fortemente connesso.
In queste ipotesi il protocollo (A1) risolve asintoticamente il problema
del consenso-medio se e solo se G è bilanciato.
Fig1. Digrafo connesso di ordine 3 che non
raggiunge il consenso medio
14
Fig.2: Esempi di digrafi bilanciati
Teorema 5:
Consideriamo una rete di integratori con una topologia fissata
ε=G(V,,A), con G digrafo fortemente connesso.
In queste ipotesi il protocollo (A1) globalmente risolve
asintoticamente il problema del consenso se e solo se =
T
1L 0
Dimostrazione ⇒ :
Dal Teorema 3 imponendo
1
r
n
=w1 atteniamo:
*
00 0
1
lim ( ) ( ) ( )
TT
rl l
t
x xt Rx x x
n
→∞
=== =ww 1 w
Cio ovviamente implica che il protocollo (A1) in modo esponenziale
per ogni nodo globalmente risolve il problema del consenso medio
con un group decision value
0
1
()
T
l
x
n
w ; nel caso in cui questo valore
coincide con la
0
()Media x allora necessariamente
0
11 1
n
llr
x
nn n
∀∈ = ⇒ = =www\ .
15