Il Pirata pdf free

Filtri con Discretizzazione dello Spazio di Stato
Discretizzazione dello Spazio di Stato
Fin ora si è sempre proceduto nella discretizzazione dell’asse temporale. Discretizzando lo spazio di stato ha un
significato analogo, ossia che lo stato x può assumere solo alcuni valori in Rn .
Si hanno tre tipi di discretizzazione del dominio a cui corrispondono altrettanti filtri :
Il campionamento avviene attraverso una trasformazione di tipo deterministico, detta trasformazione
uscented, che corrisponde al filtro di Kalman Uscented .
Il campionamento dello spazio di stato avviene in modo uniforme. Si hanno i grill based filter .
Il campionamento dello spazio di stato avviene in modo probabilistico, a cui corrispondo i particle filter .
Trasformazione Unscented
I metodi di linearizzazione tipo il filtro di Kalman esteso assumono che i contributi dei termini di secondo ordine e di
ordine superiore siano trascurabili. Tuttavia, se questi risultano essere significativi, la trasformazione corrispondente ,
può essere polarizzata e inconsistente.
In questo caso si deve ricorrere ad un metodo di approssimazione migliore della linearizzazione.
La trasformazione Unscented si basa sull’idea che è più facile approssimare una distribuzione di probabilità piuttosto
che approssimare una funzione non lineare. In pratica:
vengono generati dei campioni (punti sigma) xi nello spazio degli stati in modo da catturare certe proprietà
della distribuzione di x.
Si associano ai campioni dei pesi wi
i campioni vengono poi propagati attraverso la funzione non lineare f (·), ottenendo in tal modo dei campioni
trasformati
dei campioni trasformati si calcolano le statistiche per ottenere y e Py.
I passi della trasformazione Unscented sono quindi:
1.
Generazione dei punti sigma 
2.
Propagazione dei punti sigma attraverso la funzione non lineare yi = f (xi)
3.
Calcolo delle statistiche dei campioni trasformati:
Identificazione e Fusione Sensoriale – Appunti di DM
in cui l è il numero dei punti
Pagina 1
Filtri con Discretizzazione dello Spazio di Stato
Il numero dei punti sigma, la loro locazione nello spazio degli stati nonché i pesi associati sono scelti
deterministicamente in modo da catturare le proprietà statistiche più importanti della variabile aleatoria x. Si osserva
che non è facile catturare i momenti di x per distribuzioni generiche.
Tuttavia, se si assume per x una distribuzione Gaussiana, è possibile determinare i punti sigma garantendo
un’accuratezza fino ad almeno il secondo ordine. La distribuzione Gaussiana soddisfa le seguenti due proprietà:
1.
simmetria ⇒i punti xi devono essere simmetrici (rispetto al valor medio);
2.
una variabile aleatoria x con media x e covarianza Px, può essere sempre scritta nella forma x = x + Cz
dove z è una variabile aleatoria Gaussiana standard (con media nulla e covarianza unitaria) e CCT = Px.
La matrice C può essere ottenuta ad esempio tramite una decomposizione di Cholesky di Px.
I punti sigma sono quindi
.
Ora si vogliono generare i campioni zi della variabile aleatoria z in modo da catturarne i primi due momenti, cioè
imporre
Si può verificare che la trasformazione Unscented, utilizzando 2n + 1 punti di cui uno collocato sull’origine degli assi e
gli altri 2n disposti simmetricamente lungo gli assi coordinati, riesce ad approssimare i momenti di una variabile
aleatoria Gaussiana in forma standard sino al secondo ordine.
Dalla relazione x = x + Cz si ottengono i punti sigma associati alla variabile aleatoria x :
per i = 1, 2, . . . , n, dove Ci indica la i-esima colonna della matrice C.
La scelta del parametro k è un grado di libertà della trasformazione Unscented. Di solito si sceglie K + n = 3 .
La trasformazione Unscented riesce a catturare correttamente i momenti di x fino al secondo ordine, senza dover
calcolare né lo Jacobiano né l’Hessiano della funzione f (·). L’approssimazione è quindi migliore di quella ottenibile
tramite linearizzazione.
Identificazione e Fusione Sensoriale – Appunti di DM
Pagina 2
Filtri con Discretizzazione dello Spazio di Stato
Filtro di Kalman Unscented
Il filtro di Kalman Unscented è la diretta applicazione della trasformazione unscented al problema della stima ricorsiva.
I passi di cui è composto il procedimento di filtraggio sono i seguenti :
Fase 1 – Predizione
Contiene una trasformazione di tipo non-lineare, infatti
conoscere
.
Si ricercano i punti
con i rispettivi pesi
, in cui si suppone di
.
Per calcolare
e
si applica la trasformazione unscented ad ogni punto
seguenti equazioni di predizione :
Fase 2 – Correzione
Si considera l’errore definito come
ad ogni istante k .
Ricordando che
da cui
ottenendo le
, ossia misure attuali – misure attese , ricalcolando gli
Si hanno le seguenti equazioni di correzione :
Per non usare la matrice jacobiana si pensa di esprimere la matrice della covarianza
da cui derivano le altre equazioni di predizione :
Ad ogni iterazione è quindi necessario invertire la matrice S e scegliere i punti
matrice C si può ottenere utilizzando la decomposizione di Cholesky
in un modo diverso
. Per quanto riguarda la
Riassumendo, le principali caratteristiche del filtro di Kalman Unscented sono :
o
o
o
Per implementare il filtro non è necessario calcolare la matrice jacobiana o l’essiana delle funzioni f ed h .
Il numero dei punti sigma dipende linearmente dalla dimensione dello stato
Questo filtro risulta più efficiente rispetto al filtro di Kalman lineare, ma anche computazionalmente più
complesso.
Identificazione e Fusione Sensoriale – Appunti di DM
Pagina 3
Filtri con Discretizzazione dello Spazio di Stato
NOTA : Esistono altri tipi di filtri in cui i rumori vengono considerati non additivi, in cui le equazioni sono
Per risolverli considero un vettore aumentato per la matrice di covarianza
E 2(2n+m)+1 punti sigma .
Rappresentazione a griglia
E’la rappresentazione dello spazio di stato di un sistema, in cui l’insieme dei punti che si vanno a considerare ricadono
all’interno di una griglia equispaziale (in cui le celle hanno la stessa grandezza).
Si ha una mappa a livelli di grigio che da un’idea immediata della distribuzione di probabilità delle variabili aleatorie. E’
quindi detta mappa di tipo probabilistico. Si associa quindi alle zone chiare un’alta probabilità di accadimento e ,
viceversa, alle zone scure una bassa probabilità.
Nota : Nel caso in cui si abbia a che fare con una distribuzione multimodale solitamente si sceglie la zona con ampiezza
maggiore, a parità di valore probabilistico.
Filtro a Griglia
Con questo tipo di filtro si lavora con un campionamento temporale ed anche con un campionamento dello spazio di
stato. Il filtro a griglia ha il seguente procedimento :
Si utilizza una prima griglia costruita ad hoc in modo tale che, da un istante all’altro, sia evidente in essa lo
spostamento del sistema da uno stato all’altro, decidendo quindi il grado ed il tipo di discretizzazione dei
valori.
Una volta creata la prima griglia, all’arrivo di un nuovo controllo avviene una transizione di stato, che si
traduce in un aggiornamento della griglia mediante la trasformazione f .
Per ottenere la griglia aggiornata si applica la trasformazione (rototraslazione) f solo nei punti ammissibili,
ossia solo nei punti corrispondenti ai centri cella.
La trasformazione comporta una traslazione delle celle, e quindi dei colori corrispondenti.
Dopo aver applicato la trasformazione può capitare che alcune celle si traslino all’esterno dello spazio di stato
riducendo la probabilità totale (che deve essere sempre = 1 ). Per ristabilire tale valore si assegna alle nuove
celle entranti nello spazio di stato la probabilità corrispondente.
Al termine della fase di trasformazione si ha a disposizione la griglia di predizione che mostra la probabilità di
trovarsi in un determinato stato.
Si costruisce la griglia di correzione in base alle misurazioni ottenute per evidenziare la probabilità di trovarsi
effettivamente in quello stato date le misurazioni effettive.
Si costruisce quindi la griglia considerando per ogni centro cella la probabilità condizionata
, ossia la
probabilità di ottenere le misure che fornisce il sensore noto che la posizione è il centro cella.
Si compone una griglia finale considerando per ogni centro cella :
o La probabilità di avere quello stato data la predizione
Identificazione e Fusione Sensoriale – Appunti di DM
Pagina 4
Filtri con Discretizzazione dello Spazio di Stato
o
La probabilità di avere quello stato date le misurazioni
Combinando i due valori tramite un AND si ottiene la griglia finale.
Gli aspetti salienti del filtro a griglia sono :
Ad ogni nuovo campione si devono effettuare n*m aggiornamenti
Informazione a disposizione limitata
La complessità postrebbe crescere a dismisura al crescere delle dimensioni del sistema
Metodo di campionamento per filtri a griglia : il metodo di campionamento usato è quello di Riemann secondo cui
Percui la probabilità è data dalla somma di tutte le aree dei rettangoli, corrispondenti alla probabilità di ogni
centrocella.
Utilizzando il metodo Riemann si ha un valore certo, con errore di convergenza pari a
.
Metodo di campionamento per filtri particle : il metodo usato è quello di Montecarlo in cui
p(x) viene utilizzata per il campionamento. In questo caso i rettangoli corrispondenti alle probabilità dei centri cella
non sono equispaziati.
Utilizzando il metodo Montecarlo si ha un valore probabile, con errore di convergenza pari a
.
Metodo di campionamento per funzione di importanza : il metodo viene utilizzato nel caso in cui non si conosca la
funzione densità di probabilità p(x) ma si conosce il suo valore solo in determinati punti. Questa tecnica prevede di
scegliere una funzione di importanza q(x) con una distribuzione di probabilità che sia comoda per l’analisi, ad
esempio con tutti gli stati equiprobabili.
Si considera quindi l’integrale
In cui
da cui la discretizzazione
e risulta nota in quanto q(x) è stata scelta e p(x) si ottiene dai particle filter .
Questo tipo di campionamento viene usato per esprimere la stima a massima verosimiglianza , infatti :
o
sia la stima
istante per istante
con
Identificazione e Fusione Sensoriale – Appunti di DM
la funzione di probabilità di cui non si conosce la forma chiusa
Pagina 5
Filtri con Discretizzazione dello Spazio di Stato
o
si considera
o
La stima diventa
o
Noti
è possibile calcolare il valore della densità di probabilità a posteriori .
Nel caso in cui il valore ottenuto sia uguale al valor medio si ritrovano le formule del filtro unscented .
. Si campiona in base alla funzione d’importanza q(x) considerando i pesi
Particle Filter
Un filtro di questo tipo ha diversi gradi di liberta, di scelta, e considera il seguente procedimento :
In base all’accuratezza che si desidera si sceglie il numero M di campioni da considerare
Si scelgono i campioni da considerare, individuando una funzione di utilità adeguata. L’operazione può essere
fatta in due modi :

Si osserva lo stato del sistema e si assegna un’incertezza di tipo gaussiano. In questo modo però si
limita la potenzialità del filtro che può lavorare con funzioni moltimodali.

Ci si basa sull’equazione di misura
non può essere usato.
. Nel caso in cui l’equazione non sia biettiva il metodo
Si sceglie la q(x) in modo tale che estraendo campioni a caso si hanno più probabilità che questi
ricadano nell’intorno dei punti modali .
Si effettua la propagazione della stima , applicando l’equazione di transizione di stato
Si effettua una fase di correzione in cui si considera una nuova funzione di importanza q(x) e si ricalcolano i
pesi dei punti particle.
In alcuni casi è possibile variare il numero dei punti particle durante l’esecuzione del filtro stesso. Si utilizzano solo
quei punti che dopo il ricalcolo dei pesi risultano efficienti, ossia siano in grado di esprimere la densità di probabilità.
Questi tipi di filtri funzionano in modo ottimo nel caso in cui siano sovradimensionati, ossia se il numero di campioni
risulta efficiente per fare una stima accurata.
Metodi di approssimazione dell’integrale
Applicando i primi due metodi di approssimazione presentati insieme ai filtri particle si nota che si ottengono
grossomodo i medesimi risultati, con la differenza che il campionamento di Montecarlo prevede di
posizionare i campioni dove ha maggiore importanza descrivere la funzione.
Identificazione e Fusione Sensoriale – Appunti di DM
Pagina 6
Filtri con Discretizzazione dello Spazio di Stato
Utilizzando la modalità tramite funzione di importanza q(x) si cerca di rendere questa funzione simile alla
densità di probabilità a priori
.
Il problema che si presenta è che ad ogni passo è necessario ricalcolare la q(x) è la p(x) .
L’obiettivo quindi è di identificare una formula ricorsiva per determinare la q(x) in modo tale da poter
ottenere ricorsivamente anche l’espressione dei pesi w .
Il procedimento è il seguente :

Il peso ad ogni singola iterazione è stato definito come
E per normalizzarli è stato introdotto

Si considera tutta la storia delle variabili al tempo t ,
rispettivamente
. Si può scrivere

Separando la storia delle misure con l’ultimo campione si ha

Ricordando la definizione densità di probabilità a priori
, mentre le ultime misure sono
l’equazione diventa

Utilizzando l’ipotesi Markoviana per cui xt contiene tutto lo stato fino all’istante t e tutte le misure
fino all’istante t-1 , si può scrivere la probabilità di ottenere certe misure y dato lo stato x

I pesi sono calcolati di conseguenza
Indicazioni :
Il tipo di filtro da utilizzare dipende dal sistema :
o
Se il sistema presenta brusche discontinuità è consigliabile non avere troppa memoria della storia passata
o
Se il sistema non ha brusche discontinuità è consigliabile mantenere memoria della storia passata
Identificazione e Fusione Sensoriale – Appunti di DM
Pagina 7
Filtri con Discretizzazione dello Spazio di Stato
Alla lunga comunque il contenuto informativo non è più efficiente quindi si tende a generare una nuova popolazione,
questa operazione è detta passo di ricampionamento .
Per individuare le posizioni dei punti particle si considerano quelli di peso maggiore ed intorno ad essi si vanno a
posizionare gli altri.
Aumentare il numero di particol provoca un aumento della velocità di convergenza, ma ovviamente anche della
complessità computazionale.
Vengono utilizzati alcuni algoritmi di tipo evolutivo in cui si ha che i punti particle non sono indipendenti tra di loro, ma
sono legati attraverso una rete, ad esempio di comunicazione. L’avvicinamento o meno dei particol dipende dalla
bontà del particle stesso che tende ad attirare a se gli altri.
Identificazione e Fusione Sensoriale – Appunti di DM
Pagina 8

Download Report