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 » 10.SLAM


Landmark-based SLAM


Il problema dello SLAM

Un robot esplora un ambiente sconosciuto e statico.

Dato

  • Il controllo del robot.
  • Osservazione di features vicine.

Stima

  • Mappa delle features.
  • Percorso del robot.

Perché SLAM è difficile?

SLAM: posizione e mappa del robot sconosciuti. Errori di percorso sono correlati agli errori nella mappa.

SLAM: posizione e mappa del robot sconosciuti. Errori di percorso sono correlati agli errori nella mappa.


Perché SLAM è difficile? (segue)

Nel mondo reale, il mapping tra osservazioni e landmarks è sconosciuto.

Associazioni sbagliate possono avere conseguenze catastrofiche.

Errori di posa correlati ad associazioni di dati.


SLAM: Simultaneous Localization and Mapping

Full SLAM → Stima di percorso e mappa

Online SLAM → Stima della posa e mappa più recente

p(x_t, m |z_{1:t}, u_{1:t})=\int\int...\int p (x_{1:t}, m|z_{1:t}, u_{1:t})dx_1dx_2...dx_{t-1}

Integrazioni fatte una alla volta

Online SLAM

p(x_t, m |z_{1:t}, u_{1:t})=\int\int...\int p (x_{1:t}, m|z_{1:t}, u_{1:t})dx_1dx_2...dx_{t-1}


Full SLAM

p(x_{1:t},m|z_{1:t},u_{1:t})


Tecniche per la generazione di mappe consistenti

  • EKF SLAM
  • Fast-SLAM
  • Graph-SLAM
  • Etc.

Algoritmo del Filtro di Kalman

  1. Algoritmo Kalman_filter( μt-1, Σt-1, ut, zt):
  2. Predizione:
  3. \bar \mu_t=A_t\mu_{t-1}+B_tu_t
  4. \bar \Sigma_t=A_t\Sigma_{t-1}A_t^T+R_t
  5. Correzione:
  6. K_t=\bar \Sigma_tC_t^T(C_t\bar\Sigma C_t^T+Q_t)^{-1}
  7. \mu_t=\bar\mu_t+K_t(z_t-C_t\bar\mu_t)
  8. \Sigma_t=(I-K_tC_t)\bar\Sigma_t
  9. Return μt, Σt

(E)KF-SLAM

  • Primo algoritmo di SLAM.
  • Mappe Feature-based: pochi landmark (< 1000) e non troppo ambigui.
  • Rumore Gaussiano: non eccessivo.
  • Solo con misure di landmark.

(E)KF-SLAM (corrispondenze note)

  • Stima la posizione del robot e quella dei landmark.
  • Si assumono corrispondenze note.
  • Si aggiungono le coordinate dei landmark nel vettore di stato.

(E)KF-SLAM

Mappa con N landmark:(3+2N)-Gaussiana. Può gestire centinaia dimensioni.

Mappa con N landmark:(3+2N)-Gaussiana. Può gestire centinaia dimensioni.


Soluzione Classica – EKF

Approssima il post di SLAM con una Gaussiana ad alta dimensione [Smith & Cheesman, 1986].

Associazione di dati con singola ipotesi.

Blue path = true path   Red path = estimated path   Black path = odometry.

Blue path = true path Red path = estimated path Black path = odometry.


EKF-SLAM


EKF-SLAM (segue)


(E)KF-SLAM

  • Incertezza aumenta (a-c) su posa e landmark.
  • Appena rivede un landmark già visto (d), riduce l’incertezza.
  • Riduce l’incertezza ditutte le posizioni.
  • Matrice di covarianza lega la posizione del robot e le altre posizioni.

Propertà del KF-SLAM (Caso Lineare)

Il determinanta di ogni sottomatrice della matrice di covarianza della mappa decresce monotonicamente per successive osservazioni.

Al limite la stima dei landmark diventa totalmente correlata.

(E)KF-SLAM (corrispondenze non note)

Con corrispondenze non note occorre uno stimatore incrementale ML (maximum likelihood) per stabilire tali corrispondenze.

L’algoritmo per corrispondenze note può essere adattato.

Numero di landmark corrente Nt dimensione la mappa.

(E)KF-SLAM (corrispondenze non note)

Update di moto è lo stesso
Update di misura è diverso:

  • si ipotizza nuovo landmark e si inizializza;
  • si effettuano gli update su tutti i landmark;
  • si verifica la creazione di un nuovo landmark se la misura Mahalanobis da tutti i landmark dista più di una soglia;
  • in caso di nuovo landmark la mappa viene estesa e si calcola il nuovo valor medio e la covarianza.

SLAM su larga scala

Problema

Molte applicazioni richiedono molta autonomia in ambienti estesi

Difficoltà
Caso del filtro gaussiano lineare:

  • Complessità computazionale nel mantenere la cross-correlazione
  • La soluzione del Full covariance SLAM in O(n^2)

Nel caso generale del non-lineare e non-gaussiano:

  • “curse of dimensionality” (Bellman, 1960s)

SLAM e Covarianza

La matrice di covarianza nel caso di SLAM lineare gaussiano
Pro

  • Permette di trasferire informazione da una parte all’altra dell’ambiente
  • Limita confidenza eccessiva e divergenza

Con

  • Aumenta la complessità computazionale

Approssimazioni per SLAM

  • Local submaps [Leonard et al.99, Bosse et al. 02, Newman et al. 03]
  • Sparse links (correlations) [Lu & Milios 97, Guivant & Nebot 01]
  • Sparse extended information filters [Frese et al. 01, Thrun et al. 02]
  • Thin junction tree filters [Paskin 03]
  • Rao-Blackwellisation (FastSLAM) [Murphy 99, Montemerlo et al. 02, Eliazar et al. 03, Haehnel et al. 03]

EKF-SLAM: Complessità

Costo per passo: quadratica nel numero di landmarks: O(n^2)
Costo totale per costruire una mappa con n landmarks: O(n3)
Memoria: O(n2)

Approcci permettono EKF-SLAM
O(n1.5) / O(n2.5) / O(n)

EKF-SLAM Sommario

Quadratica nel numero dei landmarks: O(n2)

  • Rsultato di convergenza nel caso lineare.
  • Può divergere per grosse nonlinearità!
  • Applicata con successo in ambienti di grandi dimensioni.
  • Approssimazione riduce la complessità computazionale.
  • 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