Decompongono lo spazio in regioni e rappresentano il post cumulativo di ogni regione con un valore di probabilità.
Se applicati ad uno spazio finito sono detti Filtri Discreti: Xt prende valori in un insieme finito (es. in una occupancy grid la cella Xij ha 2 valori).
Se lo spazio è continuo si parla di Filtri ad Istogramma (Xt prende valori in spazio continuo).
Lo spazio è diviso in regioni finite e convesse (bins) che partizionano lo stato: Xt = x1,t v … v xn,t.
Ad ogni regione è associata una probabilità pk,t quindi p(xt) = pk,t / | xk,t|
Statica: partizione statica dello spazio.
Dinamica: partizione dello spazio dipendente dal contesto.
Rappresentazione costante: occupancy grid.
Utile quando lo stato è binario.
Problemi
Density Tree: decomposizione ricorsiva adatta alla risoluzione del post.
Meno è probabile una regione, minore è la risoluzione.
Decomposizione più precisa ed efficiente (ordini di grandezza).
Filtri ad Istogrammi
Alternativa più efficiente
Approssimano il post con un numero finito di parametri, ma tecnica diversa
Rappresenta i belief con campioni random.
Stima di non-Gaussiane, processi nonlineari.
Monte Carlo filter, Survival of the fittest, Condensation, Bootstrap filter, Particle filter.
Adattivi: numero di campioni dipendenti dalle risorse e dalla complessità del task.
1. Lo stato al tempo t è rappresentato da un insieme di campioni (particles):
Xt = xt,1, xt,2, … , xtM
2. Ogni xt,i è una istanza dello stato al tempo t, M e’ il numero delle particles.
3. Ogni particella è una ipotesi sullo stato.
4. Probabilità di “xt,m appartenente ad Xt” approssima bel(xt,m): xt,m ~ p(xt | z1:t,u1:t).
Gli insiemi di particelle Xt approssimano una funzione di distribuzione.
Prob di “xt,m appartenente ad Xt” approssima bel(xt,m): xt,m ~ p(xt | z1:t,u1:t).
Più particelle cadono in un intervallo, più è probabile l’intervallo.
Si assume f(x) < 1 per ogni x.
Campionamento da distribuzione uniforme.
Si campiona c da [0,1].
Se f(x) > c allora si mantiene il campione altrimenti si scarta.
Si vuole campionare dalla target(x) ma si può fare solo da una proposal(x).
Un campione da proposal(x) viene pesato con: w = target(x)/proposal(x).
Condizione: target(x) -> proposal(x).
Distr. di campioni su f:
Distr. di campioni su g:
Pesi w:
Nel caso del filtro particellare:
Target(x) = Bel(xt) → Xt
Proposal(x) = p(xt| ut, xt-1) Bel(xt-1) → X’t
w = p(zt | xt)
Così Xt si aggiorna da Xt-1.
Le ipotesi sono pesate:
dove
è lo State hypotesis e
è l’Importance weight.
I campioni pesati usati per rappresentare il post:
Si parte da Xt-1 che rappresenta Belt-1(x).
Si applica il modello di moto p(xt,i | ut, xt-1,i) e si campiona X’t.
Si pesano i campioni rispetto a P(z|x).
Si effettua il ricampionamento per avere Xt.
Filtri particellari usati per implementare il filtro bayesiano ricorsivo.
Rappresentano il post con un insieme di campioni pesati.
Per la localizzazione le particelle sono propagate secondo il modello di moto.
Le particelle sono pesate secondo il likelihood delle osservazioni.
Nel passo di ricampionamento si estraggono nuove particelle con probabilità proporzionale alla verosomiglianza dell’osservazione.
2. Robotica mobile - parte prima
3. Robotica mobile - parte seconda
4. Robotica Probabilistica - Filtri Bayesiani (parte prima)
5. Robotica Probabilistica - Filtri Bayesiani (parte seconda)
7. Modello Probabilistico dei Sensori
8. Robotica Probabilistica - Filtri Gaussiani
10. SLAM
11. Filtri Discreti
12. FastSLAM
13. SLAM grid-based
14. Esplorazione basata su guadagno di informazione