SLAM (robotica)

Nella geometria computazionale e nella robotica, la localizzazione e mappatura simultanea (Simultaneous localization and mapping, SLAM) è il problema computazionale della costruzione o dell'aggiornamento di una mappa di un ambiente sconosciuto, tenendo contemporaneamente traccia della posizione di un agente al suo interno. Sebbene questo inizialmente sembri essere un problema uovo-e-gallina, sono noti diversi algoritmi per risolverlo, almeno approssimativamente, in tempi trattabili per determinati ambienti. I metodi di soluzione approssimativa più diffusi includono il Particle Filter, il filtro Kalman esteso, l'intersezione di covarianza e GraphSLAM. Gli algoritmi SLAM vengono utilizzati nella navigazione, nella mappatura robotica e nell'odometria per la realtà virtuale o la realtà aumentata. Gli algoritmi SLAM sono adattati alle risorse disponibili, quindi non mirati alla perfezione, ma alla conformità operativa. Gli approcci pubblicati sono impiegati in auto a guida autonoma, veicoli aerei senza pilota, veicoli subacquei autonomi, rover planetari, nuovi robot domestici e persino all'interno del corpo umano.

Descrizione matematica del problema

Data una serie di controlli u_t e osservazioni del sensore o_t su fasi temporali discrete t, il problema SLAM è calcolare una stima dello stato dell'agente x_t e una mappa dell'ambiente m_t. Tutte le quantità sono generalmente probabilistiche, quindi l'obiettivo è calcolare: P(m_t+1, x_t+1|o_1:t+1, u_1:t). L'applicazione della regola di Bayes fornisce una struttura per l'aggiornamento sequenziale delle posizioni posteriori, data una mappa e una funzione di transizione P(x_t|x_t-1).

Algoritmi

Le tecniche statistiche utilizzate per approssimare le equazioni di cui sopra includono filtri di Kalman e filtri di particelle (noti anche come metodi Monte Carlo). Forniscono una stima della funzione di probabilità a posteriori per la posa del robot e per i parametri della mappa. I metodi che approssimano in modo conservativo il modello di cui sopra utilizzando l'intersezione di covarianza sono in grado di evitare di fare affidamento su ipotesi di indipendenza statistica per ridurre la complessità algoritmica per applicazioni su larga scala. Altri metodi di approssimazione consentono di ottenere una migliore efficienza computazionale utilizzando semplici rappresentazioni dell'incertezza a regione delimitata. Le tecniche di appartenenza a gruppi si basano principalmente sulla propagazione dei vincoli di intervallo. Forniscono un set che racchiude la posa del robot e un'approssimazione set della mappa. La regolazione del pacchetto, e più in generale la stima a posteriori massima (Maximum a posteriori estimation, MAP), è un'altra tecnica popolare per SLAM che utilizza dati di immagine, che stima congiuntamente le pose e le posizioni dei punti di riferimento, aumentando la fedeltà della mappa, e viene utilizzata nei sistemi SLAM commercializzati come Google ARCore che ha sostituito il precedente progetto di realtà aumentata "Tango". Gli stimatori MAP calcolano la spiegazione più probabile delle pose del robot e della mappa dati i dati del sensore, piuttosto che cercare di stimare l'intera probabilità a posteriori. I nuovi algoritmi SLAM rimangono un'area di ricerca attiva e sono spesso guidati da requisiti e ipotesi diversi sui tipi di mappe, sensori e modelli come descritto di seguito. Molti sistemi SLAM possono essere visti come combinazioni di scelte da ciascuno di questi aspetti.

Mappatura

Le mappe topologiche sono un metodo di rappresentazione dell'ambiente che cattura la connettività (cioè la topologia) dell'ambiente piuttosto che creare una mappa geometricamente accurata. Gli approcci SLAM topologici sono stati utilizzati per rafforzare la coerenza globale negli algoritmi SLAM metrici. Al contrario, le mappe a griglia utilizzano matrici (tipicamente quadrate o esagonali) di celle discretizzate per rappresentare un mondo topologico e fare inferenze su quali celle sono occupate. Tipicamente si presume che le celle siano statisticamente indipendenti per semplificare il calcolo. In tale ipotesi, P(m_t|x_t, m_t-1, o_t) sono impostati a 1 se le celle della nuova mappa sono coerenti con l'osservazione o_t nella posizione x_t e 0 se incoerente. Le moderne auto a guida autonoma semplificano quasi del tutto il problema della mappatura, facendo ampio uso di dati cartografici altamente dettagliati raccolti in anticipo. Ciò può includere annotazioni sulla mappa fino al livello di contrassegno delle posizioni di singoli segmenti di linea bianca e cordoli sulla strada. I dati visivi contrassegnati dalla posizione come StreetView di Google possono anche essere utilizzati come parte delle mappe. Essenzialmente tali sistemi semplificano il problema SLAM in una più semplice attività di sola localizzazione, forse consentendo di spostare oggetti come automobili e persone solo per essere aggiornati nella mappa in fase di esecuzione.

Sensori

SLAM utilizzerà sempre diversi tipi di sensori e le potenze e i limiti di vari tipi di sensori sono stati uno dei principali motori dei nuovi algoritmi. L'indipendenza statistica è il requisito obbligatorio per far fronte alla distorsione metrica e al rumore nelle misurazioni. Diversi tipi di sensori danno origine a diversi algoritmi SLAM le cui ipotesi sono più appropriate per i sensori. Ad un estremo, le scansioni laser o le caratteristiche visive forniscono dettagli di molti punti all'interno di un'area, a volte il rendering dell'inferenza SLAM non è necessario perché le forme in queste nuvole di punti possono essere allineate facilmente e in modo inequivocabile ad ogni passaggio tramite la registrazione dell'immagine. All'estremo opposto, i sensori tattili sono estremamente scarsi in quanto contengono solo informazioni su punti molto vicini all'agente, quindi richiedono modelli precedenti forti per compensare in SLAM puramente tattile. La maggior parte delle attività SLAM pratiche rientrano da qualche parte tra questi estremi visivi e tattili. I modelli di sensori si dividono ampiamente in approcci basati su dati storici e dati grezzi. I punti di riferimento sono oggetti nel mondo identificabili in modo univoco la cui posizione può essere stimata da un sensore, ad esempio punti di accesso Wi-Fi o radiofari. Gli approcci con dati grezzi non presuppongono che i punti di riferimento possano essere identificati, e invece modellano P(o_t|x_t) direttamente in funzione della posizione. I sensori ottici possono essere telemetri laser unidimensionali (raggio singolo) o 2D (sweeping), LiDAR 3D ad alta definizione, LIDAR flash 3D, sensori sonar 2D o 3D e una o più fotocamere 2D. Dal 2005, c'è stata un'intensa ricerca su VSLAM (visual SLAM) utilizzando principalmente sensori visivi (telecamera), a causa della crescente ubiquità delle telecamere come quelle nei dispositivi mobili. I sensori visivi e LIDAR sono sufficientemente informativi da consentire l'estrazione di punti di riferimento in molti casi. Altre forme recenti di SLAM includono SLAM tattile (rilevamento solo tramite tocco locale), SLAM radar, SLAM acustico e SLAM WiFi (rilevamento in base alla forza dei punti di accesso WiFi vicini). Approcci recenti applicano la gamma wireless quasi ottica per multi-laterazione (RTLS) o multi-angolazione in combinazione con SLAM come tributo a misure wireless irregolari. Una sorta di SLAM per i pedoni umani utilizza un'unità di misura inerziale montata su scarpe come sensore principale e si basa sul fatto che i pedoni sono in grado di evitare i muri per costruire automaticamente le planimetrie degli edifici da un sistema di posizionamento interno. Per alcune applicazioni all'aperto, la necessità di SLAM è stata quasi completamente rimossa a causa di sensori GPS differenziali ad alta precisione. Da una prospettiva SLAM, questi possono essere visti come sensori di posizione le cui probabilità sono così nitide da dominare completamente l'inferenza. Tuttavia, i sensori GPS possono diminuire del tutto o in alcune occasioni le prestazioni, specialmente durante i periodi di conflitto militare che sono di particolare interesse per alcune applicazioni robotiche.

Modellazione cinematica

Il termine P(x_t|x_t-1) rappresenta la cinematica del modello, che solitamente include informazioni sui comandi di azione dati un robot. Come parte del modello, è inclusa la cinematica del robot, per migliorare le stime di rilevamento in condizioni di rumore intrinseco e ambientale. Il modello dinamico bilancia i contributi di vari sensori, vari modelli di errore parziale e infine comprende una nitida rappresentazione virtuale come una mappa con la posizione e la direzione del robot come una nuvola di probabilità. La mappatura è la rappresentazione finale di tale modello, la mappa è o tale rappresentazione o il termine astratto per il modello. Per i robot 2D, la cinematica è solitamente data da un mix di comandi di rotazione e "sposta in avanti", che sono implementati con motore aggiuntivo e rumore. Purtroppo, la distribuzione formata dal rumore indipendente in direzioni angolari e lineari non è gaussiana, ma è spesso approssimata da una gaussiana. Un approccio alternativo consiste nell'ignorare il termine cinematico e leggere i dati dell'odometria dalle ruote del robot dopo ogni comando: tali dati possono quindi essere trattati come uno dei sensori piuttosto che come cinematica.

SLAM acustico

Un'estensione del comune problema SLAM è stata applicata al dominio acustico, dove gli ambienti sono rappresentati dalla posizione tridimensionale (3D) delle sorgenti sonore determinate. Le prime implementazioni di questa tecnica hanno utilizzato stime della direzione di arrivo (DoA) della posizione della sorgente sonora e si basano sulle principali tecniche di localizzazione del suono per determinare le posizioni della sorgente. Un osservatore o un robot deve essere dotato di un array di microfoni per consentire l'uso di Acoustic SLAM, in modo che le caratteristiche della DoA siano adeguatamente stimate. Acoustic SLAM ha gettato le basi per ulteriori studi sulla mappatura di scene acustiche e può svolgere un ruolo importante nell'interazione uomo-robot attraverso la parola. Al fine di mappare sorgenti sonore multiple e occasionalmente intermittenti, un sistema Acoustic SLAM utilizza i fondamenti della teoria Random Finite Set per gestire la presenza variabile di punti di riferimento acustici. Tuttavia, la natura delle caratteristiche di derivazione acustica rende Acoustic SLAM suscettibile a problemi di riverbero, inattività e rumore all'interno di un ambiente.

SLAM audiovisivo

Progettato originariamente per l'interazione uomo-robot, Audio-Visual SLAM è un framework che fornisce la fusione di caratteristiche distintive ottenute dalle modalità sia acustiche che visive all'interno di un ambiente. L'interazione umana è caratterizzata da caratteristiche percepite non solo nella modalità visiva, ma anche in quella acustica; in quanto tali, gli algoritmi SLAM per robot e macchine incentrati sull'uomo devono tenere conto di entrambi i set di funzionalità. Un framework audiovisivo stima e mappa le posizioni dei punti di riferimento umani attraverso l'uso di caratteristiche visive come la posa umana e caratteristiche audio come il linguaggio umano e fonde le convinzioni per una mappa più solida dell'ambiente. Per le applicazioni nella robotica mobile (es. Droni, robot di servizio), è utile utilizzare apparecchiature leggere e a bassa potenza come telecamere monoculari o array di microfoni microelettronici. Lo SLAM audiovisivo può anche consentire il funzionamento complementare di tali sensori, compensando il campo visivo ristretto, le occlusioni delle caratteristiche e le degradazioni ottiche comuni ai sensori visivi leggeri con l'intero campo visivo e rappresentazioni delle caratteristiche senza ostacoli inerenti a sensori audio. La suscettibilità dei sensori audio al riverbero, all'inattività della sorgente sonora e al rumore può anche essere compensata di conseguenza attraverso la fusione delle convinzioni fondamentali della modalità visiva. La funzione complementare tra le modalità audio e visiva in un ambiente può rivelarsi preziosa per la creazione di robotica e macchine che interagiscono completamente con la parola e il movimento umano.

SLAM collaborativo

SLAM collaborativo combina immagini da più robot o utenti per generare mappe 3D.

Oggetti in movimento

Gli ambienti non statici, come quelli che contengono altri veicoli o pedoni, continuano a presentare sfide per la ricerca. SLAM con DATMO è un modello che traccia gli oggetti in movimento in modo simile all'agente stesso.

Loop closure

La chiusura del ciclo (Loop closure) è il problema di riconoscere un luogo visitato in precedenza e aggiornare le convinzioni di conseguenza. Questo può essere un problema perché errori di modello o algoritmo possono assegnare priorità basse alla posizione. I metodi tipici di chiusura del loop applicano un secondo algoritmo per calcolare un certo tipo di somiglianza di misura del sensore e reimpostare i priori della posizione quando viene rilevata una corrispondenza. Ad esempio, ciò può essere fatto memorizzando e confrontando i vettori di sacchi di parole delle caratteristiche SIFT da ciascuna posizione visitata in precedenza.

Esplorazione

"Active SLAM" studia il problema combinato dello SLAM con la decisione di dove muoversi per costruire la mappa nel modo più efficiente possibile. La necessità di esplorazione attiva è particolarmente pronunciata nei regimi di rilevamento sparsi come lo SLAM tattile. Lo SLAM attivo viene generalmente eseguito approssimando l'entropia della mappa sotto azioni ipotetiche. "Multi agent SLAM" estende questo problema al caso di più robot che si coordinano per esplorare in modo ottimale.

Ispirazione biologica

Nelle neuroscienze, l'ippocampo sembra essere coinvolto in calcoli simili a SLAM, dando origine a cellule di posizionamento, e costituisce la base per sistemi SLAM bio-ispirati come RatSLAM.

Implementazioni

Vari algoritmi SLAM sono implementati nelle librerie di sistemi operativi robot (ROS) open source, spesso utilizzati insieme alla libreria di nuvole di punti per mappe 3D o funzionalità visive di OpenCV.

Storia

Un lavoro fondamentale in SLAM è la ricerca di R.C. Smith e P. Cheeseman sulla rappresentazione e stima dell'incertezza spaziale nel 1986. Altro lavoro pionieristico in questo campo è stato condotto dal gruppo di ricerca di Hugh F. Durrant-Whyte all'inizio degli anni '90: ha mostrato che le soluzioni per SLAM esistono nel limite di dati infinito. Questa scoperta motiva la ricerca di algoritmi che siano trattabili computazionalmente e approssimino la soluzione. Le auto a guida autonoma STANLEY e JUNIOR, guidate da Sebastian Thrun, hanno vinto la DARPA Grand Challenge e sono arrivate seconde nella DARPA Urban Challenge negli anni 2000, e hanno incluso i sistemi SLAM, portando SLAM all'attenzione mondiale. Le implementazioni SLAM per il mercato di massa possono ora essere trovate negli aspirapolvere robot di consumo.

Voci correlate

• Robotica
• Filtro di Kalman

Collegamenti esterni

• (EN) SLAM For Dummies (A Tutorial Approach to Simultaneous Localization and Mapping) (PDF), su ocw.mit.edu. URL consultato il 18 ottobre 2011 (archiviato dall'url originale il 15 dicembre 2011).