Stima ed algoritmi di consensus
distribuito:
considerazioni su IKF
e decomposizione del modello
Facoltà di Ingegneria
Corso di Laurea in Ingegneria dell'Automazione
Corso di Progettazione di Sistemi di Controllo
A.A. 2008/09
Docente: Luca Schenato
Loris Antoniazzi
Marco Bortolomiol
Introduzione
• Reti di sensori (WSN)
- Stima distribuita
• Premessa:
- Varietà di sistemi fisici ai quali si possono applicare tecniche di stima
distribuita
Quindi:
- Focalizzazione su sistemi su vasta scala, scomponibili in sottosistemi che
condividono tra loro un numero limitato di componenti di stato
Introduzione
1. IKF con algoritmi di consensus
•
Il tentativo di replicare il filtro centralizzato attraverso il consensus non
fornisce la scelta migliore nel caso ci siano poche comunicazioni per ogni
periodo di campionamento
•
Per i sistemi ai quali è destinata la trattazione non è necessario che ogni nodo
conosca l’intero stato del sistema, nel caso del consensus sono sufficienti un
numero ridotto di comunicazioni
•
Riferimenti: R. Carli, A. Chiuso, L. Schenato, S. Zampieri - Distributed kalman filtering based on
consensus strategies.
2. Decomposizione del modello
•
Il modello globale del sistema viene decomposto in più modelli ridotti
•
L’implementazione di filtri locali IKF sui modelli ridotti fornisce le stesse
prestazioni del caso centralizzato
•
Riferimenti: Usman A. Khan, José M. F. Moura - Model Distribution For Distributed Kalman
Filters: A Graph Theoretic Approach.
Indice
• Filtri
di Kalman in forma di informazione
• Centralizzato
• Locali
• con algoritmi di consensus
• Filtri distribuiti su modello ridotto
• Distribuzione del modello per filtraggio distribuito
• Calcolo della matrice di covarianza dell’errore
• Fusione dei vettori di informazione
• Applicazione alla conduzione del calore
• Simulazioni e commento dei risultati
Modello del sistema
• Modello del sistema:
• Ipotesi:
- Rumore di osservazione associato a ciascun sensore è scorrelato da quello
dei rimanenti
Filtro di Kalman in forma di informazione
• Filtro centralizzato
xˆ
c
k 1|k 1
N
T
1
 1

 Pk 1|k 1  Pk 1|k xˆk 1|k   C i R i yki 1 
i 1


N
T
1
 1

Pk 1|k 1   Pk 1|k 1   C i R i C i 
i 1


1
• Filtri locali distribuiti
- Predizione:
xˆki 1|k  Axˆki |k
Pk 1|k  APk |k AT  Q
- Aggiornamento:
T
1
xˆki 1|k 1  Pk 1|k 1 Pk11|k xˆki 1|k  Pk 1|k 1C i R i yki 1
T

T

1
Pk 1|k 1  Pk 1|k  Pk 1|k C i C i Pk 1|k C i  R C i Pk 1|k
Filtro di Kalman in forma di informazione
• Con algoritmi di consensus
- Centralizzato:
xˆkc 1|k  Axˆkc|k
xˆ
c
k 1|k 1
N
T
1
 1

 Pk 1|k 1  Pk 1|k xˆk 1|k   C i R i yki 1 
i 1


 Lxˆ
- Locali:
c
k 1|k
 NP|
1
N
N
 C i R i yki 1
T
1
xˆki 1|k  Axˆki |k
T
1
xˆki 1|k 1  Lxˆki 1|k  NP|C i R i yki 1
1
Filtro di Kalman in forma di informazione
• Iterazione di consensus
- Inizializzazione
xˆki 1|k 1,0  Lxˆki 1|k  Myki 1
xˆki  2|k 1,0  Axˆki 1|k 1, L 1
- Evoluzione
xˆki 1|k 1,l 1 
xˆ
i
k 1|k 1, L 1
QC
j( i )
ij
 Q xˆ
j( i )
1

N
jT
R
j 1
j
ij k 1|k 1,l
N
 xˆ
j 1
y
j
k 1
j
k 1|k 1, 0
1 N j T j 1 i
  C R yk 1
N j 1
Grafo del sistema e
suddivisione in modelli ridotti
• Ogni cerchio rappresenta una componente dello stato x
• L’arco (i,j) є E (matrice delle adiacenze), cioè Ej,i = 1 se Aj,i ≠ 0,
• I sottosistemi locali, racchiusi negli ovali, comprendono tutti gli stati che un
sensore può osservare direttamente o indirettamente
Definizione dei modelli ridotti a partire
dal grafo del modello globale
• Le matrici dei sistema ridotti, associate a ciascun sensore l, si ricavano
direttamente da quelle del sistema globale
• d(l) vettore delle componenti dello stato x coinvolte nella dinamica di x (l)
xk( l)1  A( l ) xk(l )  D (l ) d k(l )  B (l )uk( l )
yk(l )  C (l ) xk(l ) wk(l )
 a11 0  (1)
x 
 xk 
a
a
 21 22 
a13 0   x3,k  b12 

  x    0 u2,k
a
0
 
24   4 , k 

(1)
k 1
yk(1)  c11 c12 x1(1)  wk(1)
Calcolo della matrice locale di covarianza
dell’errore di stima P(l)
• Le matrici locali di covarianza dell’errore di stima sui modelli ridotti P(l), sono
funzione della matrice di covarianza globale P = Z-1 (Z matrice di informazione
supposta L-banded)
• E’ possibile esprimere il passo di predizione di P(l) in funzione di sole variabili
locali
Pk(l 1)|k  Al Pk |k AlT  B (l )Q ( l ) B (l )
Pk(l 1)|k  A(l ) Pk(|lk) A(l )  A(l ) Pkx|k
T

 A P
(l )
x( l )d ( l )
k |k
 B (l )Q (l ) B (l )
D
T
( l )T
 D
T
T
(l ) (l )
(l )
d
D (l ) 
(l ) (l )
Pkd|k
d
T
D (l ) 
T
Derivazione dei filtri locali dal filtro
centralizzato in forma di informazione
Definizione della simbologia per il filtro centralizzato:
Pk |k  Z k|1k
zˆk |k  Z k |k xˆk |k
,
il ,k  ClT Rl1 yl( l )
zˆk 1|k  Z k 1|k xˆk 1|k
Conversione dallo stato x all’informazione z
I l  ClT Rl1Cl
Vettore e matrice di informazione distribuiti
,
N
ik  C R yk   il ,k
T
Varianza dell’errore di stima e relativa inversa
Pk 1|k  Z k11|k
,
1
l 1
,
N
I  C R C   Il
T
1
l 1
Vettore e matrice di informazione
globali
• Aggiornamento
Z k |k  Z k |k 1  I
,
zˆk |k  zˆk |k 1  ik
,
Z 0|1  P01
• Predizione

Z k 1|k  Pk|k1  AZ k|1k AT  BQB T

1
,

zˆk 1|k  Z k 1|k AZ k|1k zˆk |k

,
zˆ0|1  Z 0|1 x0
Derivazione dei filtri locali dal filtro
centralizzato in forma di informazione
Fusione dei vettori di informazione locali ik(l):
• Il metodo prevede che ad ogni nodo, le componenti del vettore d’informazione
ik(l) vengano sommate a quelle relative alla medesima componente xj dello stato,
provenienti dagli altri sensori che la osservano e riescono a comunicare
direttamente.
• In modo analogo si determina If(l) fusione delle matrici di informazione I(l)
Vettore e matrice di informazione locale:
 R
ik( l )  C
(l ) T
(l )
 
T
1
(1)
k
i
yk( l )
ik(1, )x1 
  (1)  , ik( 2 )
ik , x2 
ik( 2, x)2 
ik(3, x)4 
 ( 2) 
( 3)
 ik , x3  , ik   (3) 
ik , x5 
ik( 2, x) 
 4
1
I (l )  C (l ) R (l ) C (l )
Esempio di
fusione dei vettori
di informazione
i
(1)
f ,k
 i

  (1)
, i (f 2,k)
( 2) 
ik , x2  ik , x2 
(1)
k , x1
ik( 2, x)2  ik(1, )x2 
( 2)
( 3)


i

i


k , x4
k , x4
( 2)
( 3)
  ik , x3  , i f ,k  

( 3)
i
 k , x5 
ik( 2, x)  ik(3, x) 
4 
 4
Derivazione dei filtri locali dal filtro
centralizzato in forma di informazione
Implementazione dei filtri locali di ordine ridotto:
• Condizioni iniziali: da x0 , P0 si ricavano facilmente x0(l) , P0(l). Da queste
attraverso il lemma di inversione di matrice con inversa L-banded si trova Z0(l) e
quindi z0(l)
• Aggiornamento:
Z k(l|k)  Z k(l|k) 1  I (f l )
zˆk(l|k)  zˆk(l|k) 1  i (fl,)k
,
Attraverso l’algoritmo per l’inversione di matrice DICI si calcola Pk|k = Zk|k-1
xˆk(l|k)  Pk(|lk) zˆk(l|k)
si passa poi alle variabili in x utilizzando
xˆk(l)1|k  A(l ) xˆk(l|k)  D (l ) dˆk(|lk)
• Predizione:
(l )
k 1|k
P
A P A
(l )
(l )
k |k
( l )T
A P
(l )
x(l )d ( l )
k |k
D
( l )T

 A P
(l )
x(l )d ( l )
k |k
D
( l )T
 D
T
(l )
(l ) (l )
Pkd|k
d
D (l )  B (l )Q (l ) B (l )
T
attraverso il lemma di inversione di matrice con inversa L-banded si trova Zk+1|k(l) e
quindi zk+1|k(l)
T
Applicazione: conduzione del calore
• Fenomeno descritto tramite equazione differenziale alle derivate parziali (PDE)
  2u  2u  2u 
u
 k  2  2  2 
t
y
z 
 x
• Approssimazione secondo il metodo delle differenze finite:
u nj 1  u nj 
kt n
u j 1  2u nj  u nj1  q u nj1  u nj1  1  2q u nj
2
x

 

Applicazione: conduzione del calore
• La matrice di evoluzione dello stato è di tipo circolante
q
0
0
q 
1  2q
 q

1

2
q
q
0
0


A 0
  
0 


0
0
q
1

2
q
q


 q
0
0
q
1  2q 
Ipotesi sulla distribuzione dei sensori
Al fine di semplificare l’implementazione del metodo basato sulla
distribuzione del modello si sono assunte alcune ipotesi:
• Ogni sensore osserva lo stesso numero di componenti dello stato x
• Le componenti dello stato osservate da ogni sensore sono pesate a seconda
della distanza dal sensore stesso
• Ogni componente dello stato è osservata da almeno un sensore ed al
massimo da due
• Per la comunicazione tra i
nodi sensore si è considerato
un grafo non orientato con
pesi di metropolis
Condizioni iniziali ed evoluzione
Ipotesi sulla condizione iniziale e l’evoluzione della temperatura sulla
barretta:
• La distribuzione di temperatura iniziale è di tipo sinusoidale
• La propagazione del calore avviene in evoluzione libera
Confronto tra le diverse implementazioni dei
filtri di Kalman distribuiti con consensus
Nel caso di limitate comunicazioni per intervallo di campionamento:
• Il vettore di informazione non converge
a quello del caso centralizzato
Q C
j( i )
ij
jT
R
j 1
1 N j T j 1 j
y   C R yk
N j 1
j
k
• L’ errore di stima compensato nel
passo di aggiornamento è quindi
riferito ad un’informazione diversa
da quella del caso centralizzato.
Questo comporta una sorta di errore
a regime nella stima.
Confronto tra le diverse implementazioni dei
filtri di Kalman distribuiti con consensus
La convergenza alle prestazioni del filtro centralizzato richiede un elevato
numero di comunicazioni
Nell’ esempio in considerazione, in
cui lo stato di dimensione n=20 è
osservato da N=10 sensori, ciascuno
dei quali osserva 3 stati e comunica
con i vicini secondo un grafo
circolare non orientato, con pesi di
metropolis, si è verificato essere
necessarie ben 60 iterazioni di
consensus per intervallo di
campionamento. L’autovalore λ1,
della matrice di consensus Q vale
infatti λ1 = 0,91.
Confronto tra le diverse implementazioni dei
filtri di Kalman distribuiti con consensus
La convergenza alle prestazioni del filtro centralizzato richiede un elevato
numero di comunicazioni
La varianza dell’errore di stima è
stata valutata per via empirica su 20
esperimenti indipendenti e
confrontata con il valore ottimo
teorico di Pk|k
Filtri di Kalman distribuiti con consensus a
limitate comunicazioni
Nel caso di limitate comunicazioni per intervallo di campionamento:
• Il filtro deve tener conto solo della limitata informazione che riceve rispetto al
filtro centralizzato
• Ovviamente non si otterranno sin dai primi passi prestazioni paragonabili al
caso centralizzato
• Seguendo questa logica, il passo di aggiornamento della stima locale si può
i
i
i
i
i
i
i
esprimere come: xk |k  I  N  K k |k C  xˆk |k 1  N  Pk |k C R yk
T
1
• Come Ki si può utilizzare la colonna i del guadagno di Kalman ottimo del filtro
centralizzato, oppure il guadagno ottimo del filtro che si basa sul solo sensore i.
Mentre N non è più l’intero numero dei sensori, ma solo il numero di quelli che
comunicano in un passo. Si effettua poi una sola iterazione di consensus
ottenendo:
1 i 1 j
1 i 1 j j
i
xˆk |k   xˆk |k 1  N   K k |k yk  C j xˆkj|k 1
N j i 1
N j i 1


Filtri di Kalman distribuiti con consensus a
limitate comunicazioni
Confronto tra le prestazioni delle diverse implementazioni
Considerazioni sulla stima distribuita basata
sulla decomposizione del modello
Note riguardo l’implementazione effettivamente utilizzata:
• Espressione d’ aggiornamento di x(l) secondo un filtro di Kalman che si basa
sulla sola osservazione y(l)

1
T
1
xˆk(l|k)  Pk(|lk)1  C (l ) R (l ) C (l )

1
1

1
T
1
Pk(|lk)1 xˆk(l|k) 1  Pk(|lk)1  C (l ) R (l ) C (l )
C
1
(l )T
1
R (l ) yk(l )
• Si noti che ciascun vettore di informazione locale ik(l)=C(l)T R(l) -1yk(l) è
moltiplicato per un differente fattore P~k(l)
• Tornando in z appare quindi scorretto effettuare la fusione sui vettori
direttamente sui vettori d’informazione ik(l)
• Ciò che è stato effettivamente implementato per il passo di aggiornamento è:
zˆk(l|k)  zˆk(l|k) 1  ik(l )
• Si ricavano quindi le stime xk|k(l)con le quali si effettua poi il consensus con i vicini
• Particolare attenzione va posta nella determinazione delle matrici di varianza
dell’errore di stima da usare nei passi di predizione ed aggiornamento
Considerazioni sulla stima distribuita basata
sulla decomposizione del modello
Confronto tra filtro distribuito e filtri locali di ordine ridotto:
• Come errore di stima per la varianza campionaria si è usato quello relativo alle
sole componenti dello stato viste con maggior peso dai sensori
Conclusioni
• Si è verificato come in particolari casi sia possibile applicare tecniche di stima
distribuita, per la stima anche solo di una porzione dello stato x, ottenendo a
regime prestazioni confrontabili con quelle del filtro centralizzato.
• Un approccio basato su filtri distribuiti in forma di informazione che stimano
l’intero stato può presentare dei forti limiti, legati in un caso alla necessità di
effettuare un elevato numero di comunicazioni, oppure ad una poca prontezza
nel seguire la dinamica nel caso si utilizzi un filtro a ridotte comunicazioni.
• Con i filtri locali basati sul modello ridotto è invece possibile ottenere una
stima accurata sulle variabili locali utilizzando un ridotto numero di
comunicazioni. Si può pensare inoltre, se necessario, che ciascun nodo
comunichi le proprie stime locali agli altri, così da avere a ciascun nodo a
disposizione la stima dell’intero stato x.
Fine presentazione
Grazie per l’attenzione