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 » 14.Esplorazione basata su guadagno di informazione


Task dei Robot Mobili


Esplorazione e SLAM

SLAM è tipicamente passivo.

L’esplorazione guida attivamente il robot per percorrere l’intero ambiente da osservare.

L’esplorazione combinata con lo SLAM pone il problema di agire con incertzza di mappa e di posa.

L’incertezza deve essere considerata nella scelta di un’azione.

Esplorazione

Gli approcci visti fino ad ora sono passivi.

Il processo di mapping può diventare più efficace tenendo in considerazione anche il controllo.

La domanda è: dove muovere i prossimi passi?

Esplorazione


Esplorazione vs SLAM

La strategia di esplorazione determina la qualità della mappa.

La strategia di esplorazione determina la qualità della mappa.


Approccio Decision-Teoretico

Costruisci la mappa usando un Filtro Particellare.

Considera un insieme di azioni potenziali.

Definisci una strategia di esplorazione che minimizza l’incertezza totale dove:

utilità = riduzione di incertezza – costo

Incertezza del Post

L’entropia è una misura di incertezza del post

H(p(x))=-\int_x p(x)\log p(x)dx

=E_x[-\log(p(x))]

Guadagno di informazione = riduzione dell’incertezza

I(t+1 | t) = H(p(x_t))-H(p(x_t+1))

Calcolo Entropia

H(p(x,y))

=E_{x,y}[-\log p(x,y)]

=E_{x,y}[-\log (p(x)p(y|x))]

=E_{x,y}[-\log p(x)]+E_{x,y}[-\log p(y|x)]

=H(p(x))+\int_{x,y}-p(x,y)\log p(y|x)dx dy

=H(p(x))+\int_{x,y}-p(y|x)p(x)\log p(y|x) dx dy

=H(p(x))+\int_x p(x)\int_y -p(y|x)\log p(y|x)dy dx

=H(p(x))+\int_x p(x)H(p(y|x))dx

Calcolo incertezza di Mappa e Posa

H(p(x_{1:t},m|d_t))=H(p(x_{1:t}|d_t))+\int_{x_{1:t}}p(x_{1:t}|d_t)H(p(m|x_{1:t},d_t))dx_{1:t}

Data la rappresentazione approssimata

H(p(m,x_{1:t}|d_t))\approx H(p(x_{1:t}|d_t))+\sum_{i=1}^{\#~particles}\omega_t^{[i]}H(p(m^{[i]}|x_{1:t}^{[i]}, d_t))

Incertezza percorso + incertezza mappa.

Incertezza del post nelle Grid Map

Ogni cella è una variabile aleatoria binaria.

La mappa m è una occupancy grid

H(p(m))=-\sum_{c\in m}p(c)\log p(c)+(1-p(c))\log (1-p(c))

dove:

H: incertezza sulla mappa;

c: celle della grid map;

p: probabilità che la cella sia occupata.

Entropia della Mappa

L’entropia totale è la somma delle entropie individuali.

L'entropia totale è la somma delle entropie individuali.


Incertezza sulla traiettoria

Ogni posa dipende dalle pose precedenti 0:t-1.

Approssimazione con incertezza media sul percorso: H(p(x1:t|dt)).

Post su traiettoria rappresentato come gaussiana.

Incertezza sulla traiettoria (segue)

Gaussiana n-dimensionale:

H(G(\mu,\Sigma))=\log((2\pi e)^{(n/2)}|\Sigma|)

Rank ridotto per un insieme di campioni sparso.

Approssimazione per grid map:

H(p(x|d))\leadsto const.

per un insieme di campioni sparso.

Incertezza sulla traiettoria (segue)

Entropia della posa media nel tempo.

Entropia della posa media nel tempo.


Guadagno di informazione con azioni

Riduzione di entropia nel modello:

I(\hat z,a)=H(p(m,x|d))-H(p(m,x,\hat x|d,a,\hat z))

dove:

\hat z: osservazioni da ottenere;

a (al primo membro): azione;

x: entropia prima dell’azione;

a (al secondo membro): entropia dopo l’azione;

\hat x: nova posa dopo l’azione.

Guadagno di informazione atteso

Per il calcolo del guadagno atteso occorrono le osservazioni che si ottengono eseguendo le azioni.

Questo dato non è noto. Si usano quindi delle misure potenziali:

E[I(a)]=\int_{\hat z}p(\hat z|a,d)\cdot I(\hat z, a)d\hat z

Sequenze di Misure

Il filtro rappresenta il post sulle possibili mappe.

Si usano queste mappe per definire le possibili osservazioni.

Simulazione di misure laser sulle mappe delle particelle:

E[I(a)]=\int_{\hat z}p(\hat z|a,d)\cdot I(\hat z, a)d\hat z

dove:

\hat z: sequenze di misure simulate nella mappa;
p: peso della particella (likelihood).

Sequenze di Misure

Mappa della i-esima particella.

Mappa della i-esima particella.


Utilità

Si definisce una utilità associata all’azione:

U(a)=I(a)-\alpha \cdot cost. (a)

Si selezione l’azione che massimizza l’utilità attesa:

a^*=argmax_a \{E[U(a)]\}

Azioni specifiche

Si definiscono le seguenti classi di azioni:

  • azioni esplorative (1-3);
  • azioni di chiusura di ciclo (4);
  • azioni di visita (5).

Rilevazione di cicli

Il grafo della traiettoria è il cammino percorso dal robot.

La mappa di occupazione rappresenta lo spazio coperto dai sensori.

I cicli corrispondono a percorsi lunghi sul grafo delle traiettorie e brevi tratti sulla grid map.


Esempio


Possibili Target


Valutazione Target e Movimento


Valutazione Target e Movimento


  • 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