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.
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
Integrazioni fatte una alla volta
Online SLAM
Full SLAM
Tecniche per la generazione di mappe consistenti
- EKF SLAM
- Fast-SLAM
- Graph-SLAM
- Etc.
Algoritmo del Filtro di Kalman
- Algoritmo Kalman_filter( μt-1, Σt-1, ut, zt):
- Predizione:
- Correzione:
- 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.
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.
(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.