Localització i mapatge simultani

Stanley, guanyador del Grand Challenge DARPA de 2005, va realitzar SLAM com a part del seu sistema de conducció autònoma.

La localització i mapatge simultani (SLAM) és el problema computacional de construir o actualitzar un mapa d'un entorn desconegut alhora que es fa un seguiment de la ubicació d'un agent intel·ligent dins d'aquest mapa. Tot i que inicialment sembla ser un problema de l'ou o la gallina, hi ha diversos algorismes coneguts per resoldre'l en, almenys aproximadament, un temps tractable per a determinats entorns. Els mètodes de solució aproximats populars inclouen el filtre de partícules, el filtre de Kalman estès, la intersecció de covariància i GraphSLAM. Els algorismes SLAM es basen en conceptes de geometria computacional i visió per ordinador, i s'utilitzen en la navegació de robots, mapes robòtics i odometria per a realitat virtual o realitat augmentada.

Un mapa generat per un robot SLAM

Els algorismes SLAM s'adapten als recursos disponibles i no estan dirigits a la perfecció sinó al compliment operatiu. Els enfocaments publicats s'utilitzen en cotxes autònoms, vehicles aeris no tripulats, vehicles submarins autònoms, rovers planetaris, robots domèstics més moderns, i fins i tot dins del cos humà.

Descripció matemàtica del problema

Donat una sèrie de controls $u_t$ i observacions de sensors $o_t$ en passos de temps discrets $t$, el problema SLAM és calcular una estimació de l'estat de l'agent $x_t$ i un mapa de l'entorn $m_t$. Totes les quantitats solen ser probabilistes, de manera que l'objectiu és calcular

$P(m_{t+1},x_{t+1}|o_{1:t+1},u_{1:t})$

L'aplicació de la regla de Bayes proporciona un marc per actualitzar seqüencialment els posteriors de la ubicació, donat un mapa i una funció de transició $P(x_t|x_{t-1}$)

$P(x_t|o_{1:t},u_{1:t},m_t)=\sum _{m_{t-1}}P(o_t|x_t,m_t,u_{1:t})\sum _{x_{t-1}}P(x_t|x_{t-1})P(x_{t-1}|m_t,o_{1:t-1},u_{1:t})/Z$

De la mateixa manera, el mapa es pot actualitzar seqüencialment per

$P(m_t|x_t,o_{1:t},u_{1:t})=\sum _{x_t}\sum _{m_t}P(m_t|x_t,m_{t-1},o_t,u_{1:t})P(m_{t-1},x_t|o_{1:t-1},m_{t-1},u_{1:t})$

Com molts problemes d'inferència, les solucions per inferir les dues variables juntes es poden trobar, a una solució òptima local, alternant actualitzacions de les dues creences en una forma d'algorisme d'expectativa-maximització.

Algorismes

Les tècniques estadístiques utilitzades per aproximar les equacions anteriors inclouen filtres de Kalman i filtres de partícules (l'algorisme que hi ha darrere de la localització de Monte Carlo). Proporcionen una estimació de la distribució de probabilitat posterior per a la postura del robot i per als paràmetres del mapa. Els mètodes que aproximen de manera conservadora el model anterior mitjançant la intersecció de covariància són capaços d'evitar la dependència dels supòsits d'independència estadística per reduir la complexitat algorítmica per a aplicacions a gran escala. Altres mètodes d'aproximació aconsegueixen una eficiència computacional millorada mitjançant l'ús de representacions simples de regions limitades de la incertesa.

Les tècniques de pertinença de conjunt es basen principalment en la propagació de restriccions d'interval. Proporcionen un conjunt que inclou la postura del robot i una aproximació conjunta del mapa. L'ajust de paquets i, en general, l'estimació de màxima probabilitat a posteriori (MAP), és una altra tècnica popular per SLAM que utilitza dades d'imatge, que estima conjuntament posicions i posicions de referència, augmentant la fidelitat del mapa, i s'utilitza en sistemes SLAM comercialitzats com l'ARCore de Google, que substitueix la seva plataforma informàtica de realitat augmentada anterior anomenada Tango, abans Project Tango. Els estimadors MAP calculen l'explicació més probable de les posicions del robot i el mapa donades les dades del sensor, en lloc d'intentar estimar tota la probabilitat posterior.

Els nous algorismes SLAM segueixen sent una àrea de recerca activa i sovint es deuen a diferents requisits i supòsits sobre els tipus de mapes, sensors i models tal com es detalla a continuació. Molts sistemes SLAM es poden veure com una combinació d'opcions de cadascun d'aquests aspectes.

Cartografia

Els mapes topològics són un mètode de representació de l'entorn que capturen la connectivitat (és a dir, la topologia) de l'entorn en lloc de crear un mapa geomètricament precís. Els enfocaments SLAM topològics s'han utilitzat per reforçar la coherència global en algorismes SLAM mètrics.

En canvi, els mapes de quadrícula utilitzen matrius (normalment quadrades o hexagonals) de cel·les discretitzades per representar un món topològic i fer inferències sobre quines cel·les estan ocupades. Normalment se suposa que les cel·les són estadísticament independents per simplificar el càlcul. Sota aquest supòsit, $P(m_t|x_t,m_{t-1},o_t)$ s'estableixen a 1 si les cel·les del mapa nou són coherents amb l'observació $o_t$ a la ubicació $x_t$ i 0 si és inconsistent.

Els cotxes moderns de conducció autònoma en la seva majoria simplifiquen el problema de la cartografia a gairebé res, fent un ús extensiu de dades de mapes molt detallades recopilades per endavant. Això pot incloure anotacions de mapes al nivell de les ubicacions de marcatge de segments de línia blanca individuals i vorals de la carretera. Les dades visuals etiquetades amb la ubicació, com ara StreetView de Google, també es poden utilitzar com a part dels mapes. Essencialment, aquests sistemes simplifiquen el problema SLAM a una tasca més senzilla només de localització, potser permetent que objectes en moviment com ara cotxes i persones només s'actualitzin al mapa en temps d'execució.

Sensat

SLAM sempre utilitzarà diversos tipus de sensors diferents, i les potències i els límits de diversos tipus de sensors han estat un dels principals impulsors dels nous algorismes. La independència estadística és el requisit obligatori per fer front al biaix mètric i al soroll en les mesures. Els diferents tipus de sensors donen lloc a diferents algorismes SLAM, quins supòsits són els més apropiats per als sensors. En un extrem, les exploracions làser o les característiques visuals proporcionen detalls de molts punts dins d'una àrea, de vegades fent innecessària la inferència SLAM perquè les formes d'aquests núvols de punts es poden alinear fàcilment i sense ambigüitats a cada pas mitjançant el registre d'imatge. A l'extrem oposat, els sensors tàctils són extremadament escassos, ja que només contenen informació sobre punts molt propers a l'agent, de manera que requereixen models previs forts per compensar en SLAM purament tàctil. La majoria de les tasques pràctiques SLAM es troben entre aquests extrems visuals i tàctils.

Mètodes d'implementació

S'implementen diversos algorismes SLAM a les biblioteques del sistema operatiu per a robots (ROS) de programari de codi obert, que s'utilitzen sovint juntament amb la biblioteca de núvols de punts per a mapes 3D o funcions visuals d'OpenCV.

EKF SLAM

En robòtica, EKF SLAM és una classe d'algorismes que utilitza el filtre de Kalman estès (EKF) per SLAM. Normalment, els algorismes EKF SLAM es basen en funcions i utilitzen l'algoritme de màxima probabilitat per a l'associació de dades. A les dècades de 1990 i 2000, EKF SLAM havia estat el mètode de facto per SLAM, fins a la introducció de FastSLAM.

Associada a l'EKF hi ha la hipòtesi del soroll gaussià, que perjudica significativament la capacitat d'EKF SLAM per fer front a la incertesa. Amb una major quantitat d'incertesa a la part posterior, la linealització de l'EKF falla.

GraphSLAM

En robòtica, GraphSLAM és un algorisme SLAM que utilitza matrius d'informació escassa produïdes generant un gràfic de factors d'interdependències d'observació (dues observacions estan relacionades si contenen dades sobre la mateixa fita). Es basa en algorismes d'optimització.