Localisació i modelació simultàneus

Archiu:Stanley2.JPG

STANLEY, guanyador del 2005 DARPA Grand Challenge, incorpora SLAM com a part del seu sistema de conducció autònoma

La localisació i mapage simultàneus, mapage i localisació simultàneus o SLAM (de l'anglés simultaneous localization and mapping ), és una tècnica usada per robots i vehículs autònoms per a construir un mapa d'un entorn desconegut en el que es troba, al mateix temps que estima la seua trayectòria en desplaçar-se dins d'este entorn.

Introducció

Archiu:RoboCup Rescue arena map generated by robot Hector from Darmstadt at 2010 German open.jpg

Mapa generat per un SLAM Robot

La localisació i modelació simultàneus investiga els problemes que planteja la construcció de models matemàtics, geomètrics o llògics d'entorns físics, amprant com a ferramenta un robot mòvil —en ocasions varis d'ells— i el conjunt de sensorés i actuadorés que ho conformen. Dit d'una atra manera, el SLAM busca resoldre els problemes que planteja el colocar un robot mòvil en un entorn i posició desconeguts, i que ell mateixa siga capaç de construir incrementalmente un mapa consistent de l'entorn al temps que utilisa dit mapa per a determinar la seua pròpia localisació.

La solució de dit problema, objectiu insoslayable si es desija dispondre de robots mòvils verdaderament autònoms, ha segut objecte d'estudi per part de la comunitat científica durant els últims 20 anys.

El soroll present en els sistemes sensorials, els inevitables errors i aproximacions comesos en els models empleats, i la dificultat representativa dels entorns a mida que estos aumenten en complexitat, fan que la tasca de resoldre el mencionat problema siga àrdua. Tal complexitat té un doble alvertent:

• Des d'un punt de vista conceptual s'impon la necessitat de raonar en un món a voltes confús, en ocasions dinàmic i canviant, aprehendido per mig de sensors que disten molt de ser perfectes. En estes condicions es busca la manera d'obtindre i manipular senyes sobre l'entorn, extraure aquell coneiximent que siga substancial per a la tasca de la seua representació, i integrar l'informació aixina obtinguda del modo més convenient. Moltes preguntes sorgixen en este nivell de complexitat: ¿qué és l'entorn?, ¿quines geometria cal esperar trobar en ell?, ¿existixen objectes mòvils?, ¿en quina precisió és necessari representar-ho?, ¿quin nivell de coneiximent permetrà obtindre el mapa generat?
• L'atre alvertent de la complexitat del problema té que vore en l'aspecte computacional de les solucions plantejades al problema de el SLAM, i està indisolublemente lligada a l'anterior. El modo en que el robot perceba el seu entorn, la cantitat d'informació disponible aixina com les tècniques empleades en el seu processament, interpretació i combinació, determinaran els recursos computacionals necessaris per a la construcció del mapa. Estos recursos no són illimitats; menys encara si l'objectiu és cenyir-se als disponibles a bordo de la màquina. Ací els interrogants tenen que vore en l'idoneïtat dels algoritmes utilisats i la possibilitat d'obtindre solucions l'implementació de les quals siga possible en temps real.

Aixina que, en la base de qualsevol solució al problema de el SLAM es troba sempre en la necessitat de treballar en cantitats progressivament creixents d'informació —contaminada en major o menor mida per soroll—, i manipulada per mig de models que, la majoria de les voltes, no són sino meres aproximacions a la realitat. No és d'estranyar, per lo tant, que les solucions més exitoses fins al moment hagen estat basades en l'utilisació de tècniques provabilístiques.

SLAM en tècniques provabilístiques

Les solucions que millors resultats han obtingut a l'hora d'abordar el problema de el SLAM són aquelles basades en tècniques provabilístiques. Conseguixen aixina fer front a totes les fonts d'incertitut involucrades en el procés, ya comentades anteriorment. Este tipo d'algoritmes tenen la seua base en la teorema de Bayes, que relaciona entre sí les provabilitats marginal i condicional de dos variables aleatòries.

La formulació bayesiana de el SLAM

El principal obstàcul a l'hora de modelar un entorn desconegut, utilisant un robot mòvil per a la seua exploració és l'inevitable incertitut que es deriva de l'imperfecció dels sensors i models amprats. Si els sensors anaren perfectes, proporcionarien mides absolutament precises dels objectes detectats, que podrien ser insertats en un mapa en la seua posició exacta respecte a un sistema de referència lligat al robot. De la mateixa manera, en desplaçar-se la màquina, una mida exacta del gir de les seues rodes —o de l'alvanç de les seues pates—, combinada en un model exacte del seu moviment, permetrien determinar exactament la posició del robot quan este realisara una nova mida. Podríem aixina construir incrementalmente un model perfecte de l'entorn.

Desafortunadament tanta perfecció no existix en este món; o a lo manco no en el món que oferix l'actual desenroll tecnològic. S'impon per tant la necessitat d'acomodar estes incertituts en les solucions obtingudes.

La manera evident de fer-ho és considerar que tant la posició del robot com els elements que modelen el seu entorn són variables aleatòries. Aixina, els algoritmes existents modelen abdós de manera provabilística, i utilisen métodos d'inferència per a determinar aquella configuració que és més provable tenint en conte les mides que es van obtenint.

El principi bàsic que subyacer en qualsevol solució exitosa de el SLAM és la regla de Bayes. Per a dos variables aleatòries, $x$ i $d$, esta regla establix de manera molt compacta lo següent:

$p(x|d)=\frac{p(d|x)p(x)}{p(d)}$

L'anterior equació constituïx un mecanisme bàsic d'inferència, la simplicitat de la qual no resta un àpiç a la potència del seu significat. Supongam que volem obtindre informació sobre la variable $x$ —per eixemple, l'estat d'un sistema compost per un mapa i un robot— basant-se en l'informació continguda en una atra variable $d$ —que be podria ser un conjunt de mides adquirides per un sensor—. L'anterior regla indica que este problema es pot resoldre simplement multiplicant dos térmens:

1. El model generativo $p(d|x)$, que expressa la provabilitat d'obtindre la mida $d$ baix l'hipòtesis expressada per l'estat $x$
2. El grau de confiança que es dona a que $x$ siga precisament el cas abans de rebre les senyes, $p(x)$

És important el fet de que el denominador de l'equació anterior no depén de la variable que es pretén estimar, $x$. Per esta raó $p(d)$ se sol escriure com un factor de normalisació.

Principals algoritmes

El filtre estés de Kalman

L'utilisació d'un Filtre Estés de Kalman és una de les solucions més esteses al problema de la localisació i modelació simultàneus, i també és una de les que millors resultats ha proporcionat en la pràctica. A esta categoria de solucions, el fonament de les quals enraíza en els treballs introductoris realisats per Randall Smith, Matthew Self i Peter Cheeseman a finals de la década de 1980, li la coneix generalment com SLAM-EKF.

Per la seua pròpia naturalea, el SLAM-EKF requerix dispondre d'un mapa en el qual les entitats que ho componen siguen fàcilment parametrisables. Açò és, els elements que componen el mapa deuen poder ser descrits utilisant un conjunt de paràmetros que encaixen de forma senzilla en el vector d'estat del sistema.

A la vista de les hipòtesis realisades, cal enumerar les següents desventages d'esta classe d'algoritmes:

1. La premissa de partida de l'algoritme, que supon una distribució gaussiana per a l'estat del sistema, pugues no correspondre's en la realitat. En el millor dels casos, les linealizaciones introduïdes en els models faran que les estimacions dels moments d'esta distribució degeneren a lo llarc del temps no corresponent-se en els seus autèntics valors.
2. El punt anterior indica ademés un greu problema de consistència de l'algoritme, que fa que el nivell de confiança de l'estimació obtinguda no es corresponga en l'autèntic error comés. Açò origina que l'exactitut dels resultats obtinguts pel filtre siguen a sovint impredictibles, observant-se bots bruscs en l'estimació sense causa aparent alguna.
3. El cost computacional creix al quadrat en el número d'objectes continguts en el mapa. Este fet llimita la seua aplicació en temps real a mapes formats per uns pocs centenars d'objectes.
4. No sempre és senzill o immediat extraure característiques de l'entorn assimilables a una classe particular d'objecte. En ocasions ni tan sols cal extraure informació que puga descriure's amprant primitives geomètriques simples com a punts, segments, arcs de circumferència o plans (per eixemple, en l'interior d'una mina).
5. Cal dispondre d'un método d'associació de senyes robust que permeta emparellar les observacions realisades en els elements continguts en el mapa. Una associació de senyes errònea provocarà casi en total seguritat la divergència irrecuperable de l'estimació del filtre.

A pesar dels inconvenients que sorgixen en amprar esta solució, es tracta de la més estesa en la lliteratura i presenta interessants propietats que resulten molt atractives:

1. El fet de descriure l'entorn a partir d'entitats geomètriques descriptibles de manera compacta, es corresponen més en una visió antropomórfica del món, que representa este últim a través del concepte de l'objecte i les seues relacions.
2. Estes solucions conten en una llarga tradició, la qual cosa fa que la seua estructura, ventages i inconvenients siguen ben coneguts. Històricament s'han plantejat múltiples solucions que intenten paliar alguns dels problemes anteriorment mencionats.
3. En mantindre's la matriu d'covarianza del sistema completa, és capaç de tancar bucles exitosamente.

Mapes d'ocupació de celdillas

Els mapes d'ocupació de celdillas varen ser introduïts per Hans Moravec i Alberto Elfes a mitan de la década de 1980. El método es basa en discretizar l'espai, dividint-ho en unitats de tamany predefinit, que es classifiquen com ocupades o buides en un determinat nivell de confiança o provabilitat.

Estes solucions partixen de l'hipòtesis de que la posició del robot és coneguda. En la pràctica, es necessita d'algun método de localisació que estime la posició del robot en cada instant que, en este cas, no és considerada una variable estocàstica. La precisió que alcancen estos mapes en la descripció de l'entorn (tant major quant més fina és la divisió de l'espai), permet que l'algoritme de localisació amprat acumule errors reduïts a lo llarc d'intervals prolongats de temps. Aixina que, la major desventaja d'estos métodos és la pèrdua de potència que es deriva de no tindre en conte l'incertitut associada a la posició del robot, la qual cosa origina que la seua capacitat per a tancar bucles correctament es veja mermada.

Entre les seues ventages cal destacar les següents:

1. L'algoritme és robust i la seua implementació senzilla.
2. No fa suposicions sobre la naturalea geomètrica dels elements presents en l'entorn.

1. Distinguix entre zones ocupades i buides, conseguint una partició i descripció completa de l'espai explorat. Per este motiu és popular en tasques de navegació, en facilitar la planificació i generació de trayectòries amprant métodos convencionals.
2. Permet descripcions arbitrariamente denses o precises del món, simplement aumentant la resolució de la reixeta que ho dividix (p. eix. disminuint el tamany de les celdillas individuals). Com és llògic, açò va en detriment del rendiment computacional de l'algoritme.
3. Permet una extensió conceptualment simple a l'espai tridimensional.

Recentment han aparegut variants d'este método que milloren substancialment alguns aspectes. Per eixemple, els mapes de cobertura que mantenen una provabilitat d'ocupació per a cada celdilla que s'ajusta més correctament a casos en els que esta es troba només parcialment ocupada, o el DP-SLAM, que manté vàries hipòtesis sobre el mapa construït i utilisa un filtre de partícules per a estimar la que més s'ajusta a la realitat.

Solució factorizada del filtre de Bayes

En la tesis de Michael Montemerlo es realisa un detallat anàlisis de la formulació Bayesiana del problema SLAM, i s'aplega a una conclusió que resulta molt intuïtiva i casi evident. Si el camí verdader que recorre el robot fora perfectament conegut, l'estimació del mapa seria un problema de solució casi immediata. Ademés supondria una ventaja computacional, ya que l'estimació dels objectes que componen el mapa seria independent, ya que no estarien relacionats per l'incertitut comuna associada a la posició del sensor del robot. Per tant, les correlació entre els objectes serien nules. És alguna cosa semblat a lo que succeïx en els mapes d'ocupació de celdillas, que també suponen coneguda la localisació del robot en tot moment.

Vore també

• Planta (arquitectura)
• Robot autònom
• Sistema de posicionament en interiors