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
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Alberto Finzi » 9.Mapping con pose note


Perché Mapping?

E’ uno dei problemi fondamentali in robotica mobile.

La mappa permette lo svolgimento dei task e la localizzazione.

Robot di successo si basano su mappe per localizzazione, path planning, activity planning etc…

Il problema del mapping

Per i dati di sensing:

d=\{u_1,z_1,u_2,z_2, ..., u_n,z_n\}

occorre calcorare la mappa più probabile

m^*=\arg \max_m P(m|d)

Mapping come problema dell’uovo e della gallina

Abbiamo visto come stimare la posa di un veicolo per dati sensoriali e mappa.

Il mapping, però richiede la stima simultanea di posa e mappa.

Il problema generale è chiamato: simultaneous localization and mapping problem (SLAM).

Si considera prima il mapping assumendo di conoscere la posa del veicolo.

Problemi di Mapping

Interpretazione dei dati sensoriali

  • Come estrarre informazione rilevante dai dati di sensing?
  • Come rappresentare e integrare questa informazione nel tempo?

Stima delle locazioni

  • Come identificare posti visitati precedentemente?
  • Il problema è chiamato: data association problem.

Problemi di Mapping (segue)

Dimensioni. Più grande è l’ambiente più difficilie è il probelma.

Rumore. Maggiore è il rumore di sensori ed attuatori più difficile è il problema.

Abiguità percettiva. Più frequentemente le posizioni sono simili più è difficile stabilire corrispondenze.

Cicli. I cicli sono difficili da mappare, l’errore odometrico accumulato può essere molto grande.

Mappe Occupancy Grid

Introdotte da Moravec e Elfes nel 1985.

Rappresentano l’ambiente come una griglia (solitamente 2D).

Stima della probabilità che una locazione sia occupata da un ostacolo: P(mi=1), P(mi=0).

Assunzione

Occupazione di celle m[x,y] è indipendente

Bel(m_t)=P(m_t|u_1,z_2, ... , u_{t-1}, z_t)

=\prod_{x,t}Bel (m_t^{[xy]})

Le posizioni del robot sono note

Update della Occupancy Grid

Idea: ogni cella viene aggiornata usando un filtro di bayes binario:

Bel(m_t^{[xy]})=\eta p(z_t|m_t^{[xy]})\int p(m_t^{[xy]}|m_{t-1}^{[xy]}, u_{t-1})Bel(m_{t-1}^{[xy]})dm_{t-1}^{[xy]}

Assunzione: mappa statica:

Bel (m_t^{[xy]})=\eta p(z_t|m_t^{[xy]})Bel (m_{t-1}^{[xy]})

Update della Occupancy Grid

Update delle celle usando il modello di sensore inverso:

Bel(m_t^{[xy]})=1-\left(1+\frac{P(m_t^{[xy]}|z_t, u_{t-1})}{1-P(m_t^{[xy]}|z_t, u_{t-1})}\cdot \frac{1-P(m_t^{[xy]})}{P(m_t^{[xy]})}\cdot \frac{Bel(m_{t-1}^{[xy]})}{1-Bel(m_{t-1}^{[xy]}}\right)^{-1}

Oppure la rappresentazione log-odds:

\overline B(m_t^{[xy]})=\log odds\left(m_t^{[xy]}|z_t,u_{t-1}\right)\;\;\;\;\overline B\left(m_t^{[xy]}\right):=\olg odds (m_t^{[xy]})

-\log odds (m_t^{[xy]})\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; odds (x):=\left(\frac{P(x)}{1-P(x)}\right)

+\overline B(m_{t-1}^{[xy]})

Update della Occupancy Grid


Modelli di Sensori tipici per mappe Occupancy Grid

Combinazione di una funzione lineare e una Gaussiana.

Combinazione di una funzione lineare e una Gaussiana.


Parameteri chiave del modello


Valore di Occupazione dipende dalla distanza misurata


Modello di misura inverso


Probabilità occupazione basate su singole osservazioni


Update incrementale delle Occupancy Grid (Esempio)


Occupancy Grid e Mappa Maximum Likelihood

La mappa maximum likelihood ottenuta tagliando la mappa occupancy grid ad una soglia di 0.5.

La mappa maximum likelihood ottenuta tagliando la mappa occupancy grid ad una soglia di 0.5.


Occupancy Grids: dagli scan alla mappa


Problemi con assunzione di indipendenza

Integrazione di più misure quando c’e’ sovrapposizione: le misure sono dipendenti.

Integrazione di più misure quando c'e' sovrapposizione: le misure sono dipendenti.


Mapping con dipendenza: modello diretto

Ricerca locale, aggiorna fino a convergenza.

Ricerca locale, aggiorna fino a convergenza.


Esempio Modello Diretto

Rilevazione di una porta.

Rilevazione di una porta.


Alternativa: Frequenze

Per ogni cella

  • hits(x,y): numero di casi in cui un beam è finito su <x,y>
  • misses(x,y): numero di casi in cui un beam è passato attraverso <x,y>
Bel (m^{[xy]})=\frac{\text{hits}(x,y)}{\text{hits}(x,y)+\text{misses}(x,y)}

Valore di interesse: P(reflects(x,y))

Il modello di Misura

Posa al tempo t: x_t

Beam n di scan tz_{t,n}

Maximum range reading: \zeta_{t,n}=1

Beam riflesso da un oggetto: \zeta_{t,n}=0

p(z_{t,n}|x_t,m)=\left\{\begin{array}{ll}\prod_{k=0}^{z_{t,n}-1}(1-m_{f(x_t,n,k)})\;\;\;\;\;\;\;\;\text{if}\zeta_{t,n}=1\\ \\m_{f(x_t,n,z_{t,n})}\prod_{k=0}^{z_{t,n}-1}(1-m_{f(x_t, n,k)})\;\;\text{if} \zeta_{t,n}=0\end{array}\right


Calcola la mappa più probabile

Calcola i valori di m che massimizzano:

m^*=\arg\max P(m|z_1, ..., z_t, x_1, ...,x_t)

Assumendo un prior uniforme p(m) equivale a massimizzare (applic. della regola di Bayes):

m^*=\arg\max_m P(z_1, ..., z_t|m,x_1, ..., x_t)

=\arg\max_m \prod_{t=1}^{T}P(z_t|m,x_t)

=\arg\max_m\sum_{t=1}^T\ln P(z_t|m,x_t)

Calcolo della mappa più probabile (segue)

m^*=\arg\max_m\left[\sum_{j=1}^J\sum_{t=1}^T\sum_{n=1}^N(I(f(x_t,n, z_{t,n})=j)\cdot(1-\zeta_{t,n})\cdot \ln m_j +\sum_{k=0}^{z_{t,n}-1}I(f(x_t,n,k)=j)\cdot \ln(1-m_j))\right]

dove

\alpha_1=\sum_{t=1}^T\sum_{n=1}^N I(f(x_t,n,z_{t,n})=j)\cdot(1-\zeta_{t,n})

\beta_j=\sum_{t=1}^T\sum_{n=1}^N\left[\sum_{k=0}^{z_{t,n}-1}I(f(x_t,n,k)=j)\right]

Interpretazione di αj e βj

\alpha_1=\sum_{t=1}^{T}\sum_{n=1}^NI(f(x_t,n,z_{t,n})=j)\cdot (1-\zeta_{t,n})

Numero di volte che un beam, non maximum range, finisce nella cella j (hits(j)).

\beta_j=\sum_{t=1}^T\sum_{n=1}^N\left[\sum_{k=0}^{z_{t,n}-1}I(f,(x_t,n,k)=j)\right]

Numero di volte che un beam passa per una cella j senza finirci (misses(j)).

Calcolo della mappa più probabile

Le celle mj si assumono independenti:

m^*=\arg\max_m\left(\sum_{j=1}^J\alpha_1\ln m_j+\beta_j\ln(1-m_j)\right)

Se settiamo:

\frac{\partial m}{\partial m_j}=\frac{\alpha_j}{m_j}-\frac{B_j}{1-m_j}=0

si ottiene:

m_j=\frac{\alpha_i}{\alpha_j+\beta_j}

Il calcolo della mappa più probabile equivale a contare quanto spesso una cella ha riflesso una misura e quanto spesso è stata intercettata.

Differenza tra le Mappe Occupancy Grid e Counting

Il modello counting determina quanto spesso una cella riflette un beam.

Il modello occupancy determina se una cella è occupata da un oggetto.

Anche se una cella è occupata da un oggetto la probabilità di riflessione dell’oggetto può essere molto bassa.

Sommario

Le mappe occupancy grid sono un approccio popolare per la rappresentazione dell’ambiente di un robot mobile.

In questo approccio ogni cella è considerata indipendentemente dalle altre.

Contiene il posterior che l’area corrispondente nell’ambiente sia occupata.

La mappa occupancy grid può essere appresa efficientemente con approccio probabilistico.

Le mappe reflection sono un’alternativa.

Contengono, per ogni cella, la probabilità che un beam sia riflesso da questa cella.

Modello di sensore per calcolare il likelihood di misura, la procedura di conteggio porta alla mappa ottimale.

  • 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