Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Alberto Finzi » 11.Filtri Discreti


Filtri ad Istogrammi e Discreti

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).

Filtro Discreto: Algoritmo


Filtro ad Istogramma

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|

Filtro ad Istogramma (segue)

La funzione risultante è costante a tratti.

La funzione risultante è costante a tratti.


Implementazione

Statica: partizione statica dello spazio.

Dinamica: partizione dello spazio dipendente dal contesto.

Rappresentazione costante: occupancy grid.


Rappresentazione Statica

Utile quando lo stato è binario.

Problemi

  • Per update e normalizzazione occorre la scansione di tutta la griglia.
  • Se le credenze sono concentrate si vorrebbe evitare.
  • Si può fare l’update di una sottogriglia “attiva”, ma non gestisce la delocalizzazione.

Localizzazione Grid-based

Gridmap risoluzione 15 cm, 15 g, 2LRF, beam model. Posizione dopo 3 scan.

Gridmap risoluzione 15 cm, 15 g, 2LRF, beam model. Posizione dopo 3 scan.


Localizzazione Grid-based (segue)

Sonar and occupancy Grid map.

Sonar and occupancy Grid map.


Decomposizione Dinamica

Density Tree: decomposizione ricorsiva adatta alla risoluzione del post.

Meno è probabile una regione, minore è la risoluzione.

Decomposizione più precisa ed efficiente (ordini di grandezza).

Quadtree o Octree.

Quadtree o Octree.


Filtri Particellari

Filtri ad Istogrammi

  • Discretizzazione dello spazio (statica o dinamica).
  • Problemi di risoluzione ed efficienza.

Alternativa più efficiente

  • Filtri Particellari

Approssimano il post con un numero finito di parametri, ma tecnica diversa

  • Insiemi di ipotesi (particelle) rappresentano il post.
  • Sopravvivono le migliori.

Filtri Particellari (segue)

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.

  • Filtering: [Rubin, 88], [Gordon et al., 93], [Kitagawa 96].
  • Computer vision: [Isard and Blake 96, 98].
  • Dynamic Bayesian Networks: [Kanazawa et al., 95]d.

Filtri Particellari (segue)

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).

Filtri Particellari (segue)

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.

Più particelle cadono in un intervallo, più è probabile l’intervallo.

Più particelle cadono in un intervallo, più è probabile l'intervallo.


Campionamento per Rifiuto

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.


Campionamento per importanza

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).


Campionamento per importanza (segue)


Campionamento per importanza (segue)

Peso dei campioni: w = f / g.

Peso dei campioni: w = f / g.


Campionamento per importanza (segue)

Distr. di campioni su f: p(x|z_1,z_2, ...,z_m)=\frac{\prod_{k} p(z_k|x) p(x)}{p(z_1,z_2, ...,z_n)}

Distr. di campioni su g: p(x|z_t)=\frac{p(z_t|x)p(x)}{p(z_t)}

Pesi w: \frac f g =\frac{p(x|z_1,z_2,...,z_n)}{p(x|Z_t)}=\frac{p(z_t)\prod_{k\neq 1}p(z_k|x)}{p(z_1,z_2,...,z_n)}
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)

Filtro Particellare

Come bel(xt) si aggiorna da bel(xt-1).

Così Xt si aggiorna da Xt-1.

Le ipotesi sono pesate:

S=\{\langle s^{[i]},w^{[i]}\rangle|i=1,...,N\}

dove

s^{[i]} è lo State hypotesis e

w^{[i]} è l’Importance weight.

I campioni pesati usati per rappresentare il post:

p(x)=\sum_{i=1}^w_i\cdot\delta_s[i]}(x)

Filtro Particellare: Algoritmo

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.

Filtro Particellare: Algoritmo (segue)

La posa iniziale sono particelle prese in modo random.

La posa iniziale sono particelle prese in modo random.


Informazione Sensori: Importanza

Bel(x)\leftarrow \alpha p(z|x)Bel^-(x)

w~~~~~~\leftarrow \frac{\alpha p(z|x)Bel^-(x)}{Bel^-(x)}=\alpha p(z|x)


Movimento

Bel^-(x)\leftarrow \int p(x|u,x')Bel(x')dx'


Informazione Sensori: Importanza

Bel(x)\leftarrow \alpha p(z|x)Bel^-(x)

w~~~~~~\leftarrow \frac{\alpha p(z|x)Bel^-(x)}{Bel^-(x)}=\alpha p(z|x)


Movimento

Bel^-(x)\leftarrow \int p(x|u,x')Bel(x')dx'


Filtro Particellare: Algoritmo


Sommario

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.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion