Localizzazione Monte Carlo

Le variabili del filtro di Kalman sono ipotizzate affette da rumori con distribuzione di probabilità Gaussiana. Nei casi in cui questa ipotesi non sia plausibile e si voglia introdurre una distribuzione qualsiasi, verrebbe persa la caratteristica di ottimalità. Una delle idee alternative sviluppate negli anni è quella di campionare la distribuzio- ne, in modo che i vari contributi dei campioni vadano ad interpolare la funzione di partenza non nota a priori.

Questa risulta l’idea alla base del metodo di localizzazione Monte Carlo, una tecnica basata su un filtro a particelle. Esso stima la posa di un oggetto su cui sono montati i sensori andando a ricercare le similitudini tra ciò che viene percepito ed una mappa di partenza.

Un filtro a particelle è un metodo che va a stimare lo stato di un sistema dinamico, avendone una parziale conoscenza attraverso i sensori. Rappresenta un filtro baye- siano2_{in cui iterativamente viene calcolata la distribuzione di probabilità tramite un}

metodo Monte Carlo. Concettualmente quel che si propone di fare è di descrivere la funzione densità di probabilità a posteriori attraverso dei campioni, chiamati appunto particelle, ad ognuno dei quali viene associato un peso. Attraverso le particelle ed i pesi stessi si effettua la stima. Naturalmente questa risulta un’approssimazione, ma all’aumentare del numero dei campioni la rappresentazione sarà sempre più veritiera.

2_{Un filtro bayesiano è un filtro che fa uso di un classificatore bayesiano per la valutazione di}

Alla base di questi filtri, si pone il concetto dell’importance sampling (IS). Essa è una tecnica utilizzata per la determinazioni delle proprietà di una distribuzione target a partire da campioni su una densità differente. Si fonda sul dar maggior importanza, tra le variabili casuali ricevute in ingresso, a quelle che hanno maggior influenza sulle grandezze da stimare. Viene, quindi scelta una distribuzione q(x), chiamata propo- sal distribution, e ne viene ridotta la varianza iterativamente andando a privilegiare i campioni che condizionano maggiormente la stima. Per valutare ciò ad ogni campio- ne è associato un peso w(xi), detto anche fattore d’importanza. Questi vengono poi

normalizzati, generando i pesi ˜w(xi). Si può dimostrare che così facendo la varianza

della stima può essere ridotta per una buona scelta di q(x). La stima sarà comunque affetta da errore, ma sarà consistente, cioè

P ( lim

n→∞ Xn = X) = 1.

Per il buon esito dell’algoritmo risulta chiave avere una buona conoscenza iniziale del- la q(x). Purtroppo, conoscere a priori la proposal distribution che faccia a caso del pro- blema in esame è spesso difficoltoso. Per ovviare a ciò, una possibilità è quella di ricor- rere al cosiddetto sequential importance sampling (SIS). In particolare la distribuzione può essere riscritta come:

q(x0:k|z1:k) = q(x0) k

Y

t=1

q(xt|x0:k−1, z1:k) (3.22)

dove z1:k rappresentano le k misure date dai sensori. In questo modo l’IS può essere

riformulato ricorsivamente.

In ogni caso i pesi potrebbero essere affetti da una varianza grande e portare ad un’i- naccurata stima. Inoltre, essi potrebbero diminuire nel tempo andando ad avere solo poche particelle con un peso associato diverso da zero. Dovendo trovare una solu- zione a questa degradazione, viene introdotto un nuovo passaggio che è quello del ricampionamento. Nel caso in cui questo step venga integrato la tecnica si trasfor- ma in sequential importance resampling (SIR), in cui il ricampionamento si occupa di eliminare i campioni con un peso trascurabile. Così facendo, la propagazione avver-

rà solo attraverso le particelle che stanno influenzando maggiormente la stima. Ciò può risultare positivo sia in termini di accuratezza, che di efficienza computazionale. Infatti, continuare a propagare termini non utili consumerebbe solo risorse. La distri- buzione viene di conseguenza aggiornata, ma questo può essere fatto o in maniera deterministica o dinamica. Nel primo caso ogni m passi si effettua un resampling dei campioni, con m scelto a priori. Nel secondo caso, invece, è possibile stabilire una soglia, fissa o variabile nel tempo, e l’operazione verrà effettuata solo al superamento della stessa. I metodi di ricampionamento sono molti, ma non vengono qui affrontati. Per un approfondimento si rimanda a [23, 35].

Per cui, si ha a che fare con un set di particelle ed ad ognuna di esse è associata una coppia (xi, w(xi)), formata dal vettore di stato (xi) del campione i − esimo e da un

peso (w(xi)) che ne definisce l’importanza ai fini della stima. Verrà rappresentata la

funzione densità di probabilità a posteriori p(x0:k|z1:k)attraverso le coppie appena de-

scritte.

I filtri basati sul metodo Monte Carlo rappresentano in realtà una famiglia di algoritmi rinomata per la flessibilità e l’applicabilità a svariati problemi. Essi sono accomunati dal campionamento Monte Carlo e dal trattare le particelle derivanti secondo le pro- cedure elencate, al fine di risolvere un problema di stima. Tra questi, di particolare interesse per il lavoro svolto risulta il filtro particellare adattivo o KLD-Sampling. Il se- condo nome deriva dal fatto che viene usata la distanza di Kullback-Leibler (KL), cioè date due distribuzioni di probabilità, p1e p2, la loro distanza, intesa come un valore di

similitudine tra le due, è definita come: KL(p1, p2) = X x p(x) log₂ p1(x) p2(x)  con KL(p1, p1) = 0; KL(p1, p2) ≥ 0

ed, in generale, non rappresenta una funzione simmetrica.

nare ad ogni iterazione il numero di campioni in analisi, col fine di aver un errore tra le distribuzioni minore di un certo , con una certa probabilità (1 − δ). Assumendo la funzione densità di probabilità costante a tratti, viene determinato il numero di cam- pioni che servono affinché la distanza tra la stima della probabilità a peso maggiore e la distribuzione reale, risulti inferiore alla soglia . Per il calcolo, viene appunto utiliz- zata la distanza KL.

È possibile andare a definire il numero minimo di campioni (Np) necessari affinché la

distanza tra la distribuzione calcolata e quella reale sia inferiore alla soglia prefissa- ta (). Così verrà adattato iterativamente il numero di campioni necessari per avere un’approssimazione della funzione densità di probabilità sufficientemente accurata.