Localización y modelado simultáneos

STANLEY, ganador del 2005 DARPA Grand Challenge, incorpora SLAM como parte de su sistema de conducción autónoma

La localización y mapeo simultáneos,​ mapeo y localización simultáneos​ o SLAM (del inglés simultaneous localization and mapping ), es una técnica usada por robots y vehículos autónomos para construir un mapa de un entorno desconocido en el que se encuentra, a la vez que estima su trayectoria al desplazarse dentro de este entorno.

Introducción

Mapa generado por un SLAM Robot

La localización y modelado simultáneos investiga los problemas que plantea la construcción de modelos matemáticos, geométricos o lógicos de entornos físicos, empleando como herramienta un robot móvil —en ocasiones varios de ellos— y el conjunto de sensores y actuadores que lo conforman. Dicho de otra manera, el SLAM busca resolver los problemas que plantea el colocar un robot móvil en un entorno y posición desconocidos, y que él mismo sea capaz de construir incrementalmente un mapa consistente del en torno al tiempo que utiliza dicho mapa para determinar su propia localización.

La solución de dicho problema, objetivo insoslayable si se desea disponer de robots móviles verdaderamente autónomos, ha sido objeto de estudio por parte de la comunidad científica durante los últimos 20 años.

El ruido presente en los sistemas sensoriales, los inevitables errores y aproximaciones cometidos en los modelos empleados, y la dificultad representativa de los entornos a medida que estos aumentan en complejidad, hacen que la tarea de resolver el mencionado problema sea ardua. Tal complejidad tiene una doble vertiente:

• Desde un punto de vista conceptual se impone la necesidad de razonar en un mundo a veces confuso, en ocasiones dinámico y cambiante, aprehendido mediante sensores que distan mucho de ser perfectos. En estas condiciones se busca la manera de obtener y manipular datos acerca del entorno, extraer aquel conocimiento que sea sustancial para la tarea de su representación, e integrar la información así obtenida del modo más conveniente. Muchas preguntas surgen en este nivel de complejidad: ¿qué es el entorno?, ¿qué geometrías cabe esperar encontrar en él?, ¿existen objetos móviles?, ¿con qué precisión es necesario representarlo?, ¿qué nivel de conocimiento permitirá obtener el mapa generado?
• La otra vertiente de la complejidad del problema tiene que ver con el aspecto computacional de las soluciones planteadas al problema del SLAM, y está indisolublemente ligada a la anterior. El modo en que el robot perciba su entorno, la cantidad de información disponible así como las técnicas empleadas en su procesamiento, interpretación y combinación, determinarán los recursos computacionales necesarios para la construcción del mapa. Estos recursos no son ilimitados; menos aún si el objetivo es ceñirse a los disponibles a bordo de la máquina. Aquí los interrogantes tienen que ver con la idoneidad de los algoritmos utilizados y la posibilidad de obtener soluciones cuya implementación sea posible en tiempo real.

Así pues, en la base de cualquier solución al problema del SLAM se encuentra siempre con la necesidad de trabajar con cantidades progresivamente crecientes de información —contaminada en mayor o menor medida por ruido—, y manipulada mediante modelos que, la mayoría de las veces, no son sino meras aproximaciones a la realidad. No es de extrañar, por lo tanto, que las soluciones más exitosas hasta el momento hayan estado basadas en la utilización de técnicas probabilísticas.

SLAM con técnicas probabilísticas

Las soluciones que mejores resultados han obtenido a la hora de abordar el problema del SLAM son aquellas basadas en técnicas probabilísticas. Consiguen así hacer frente a todas las fuentes de incertidumbre involucradas en el proceso, ya comentadas anteriormente. Este tipo de algoritmos tienen su base en el teorema de Bayes, que relaciona entre sí las probabilidades marginal y condicional de dos variables aleatorias.

La formulación bayesiana del SLAM

El principal obstáculo a la hora de modelar un entorno desconocido, utilizando un robot móvil para su exploración es la inevitable incertidumbre que se deriva de la imperfección de los sensores y modelos empleados. Si los sensores fueran perfectos, proporcionarían medidas absolutamente precisas de los objetos detectados, que podrían ser insertados en un mapa en su posición exacta respecto a un sistema de referencia ligado al robot. Del mismo modo, al desplazarse la máquina, una medida exacta del giro de sus ruedas —o del avance de sus patas—, combinada con un modelo exacto de su movimiento, permitirían determinar exactamente la posición del robot cuando este realizase una nueva medida. Podríamos así construir incrementalmente un modelo perfecto del entorno.

Desafortunadamente tanta perfección no existe en este mundo; o al menos no en el mundo que ofrece el actual desarrollo tecnológico. Se impone por tanto la necesidad de acomodar estas incertidumbres en las soluciones obtenidas.

La manera evidente de hacerlo es considerar que tanto la posición del robot como los elementos que modelan su entorno son variables aleatorias. Así, los algoritmos existentes modelan ambos de manera probabilística, y utilizan métodos de inferencia para determinar aquella configuración que es más probable teniendo en cuenta las medidas que se van obteniendo.

El principio básico que subyace en cualquier solución exitosa del SLAM es la regla de Bayes. Para dos variables aleatorias, $x$ y $d$, esta regla establece de manera muy compacta lo siguiente:

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

La anterior ecuación constituye un mecanismo básico de inferencia, cuya simplicidad no resta un ápice a la potencia de su significado. Supongamos que queremos obtener información acerca de la variable $x$ —por ejemplo, el estado de un sistema compuesto por un mapa y un robot— basándose en la información contenida en otra variable $d$ —que bien podría ser un conjunto de medidas adquiridas por un sensor—. La anterior regla indica que este problema se puede resolver simplemente multiplicando dos términos:

1. El modelo generativo $p(d|x)$, que expresa la probabilidad de obtener la medida $d$ bajo la hipótesis expresada por el estado $x$
2. El grado de confianza que se da a que $x$ sea precisamente el caso antes de recibir los datos, $p(x)$

Es importante el hecho de que el denominador de la ecuación anterior no depende de la variable que se pretende estimar, $x$. Por esta razón $p(d)$ se suele escribir como un factor de normalización.

Principales algoritmos

El filtro extendido de Kalman

La utilización de un Filtro Extendido de Kalman es una de las soluciones más extendidas al problema de la localización y modelado simultáneos, y también es una de las que mejores resultados ha proporcionado en la práctica. A esta categoría de soluciones, cuyo fundamento enraíza en los trabajos introductorios realizados por Randall Smith, Matthew Self y Peter Cheeseman a finales de la década de 1980, se la conoce generalmente como SLAM-EKF.

Por su propia naturaleza, el SLAM-EKF requiere disponer de un mapa en el cual las entidades que lo componen sean fácilmente parametrizables. Esto es, los elementos que componen el mapa deben poder ser descritos utilizando un conjunto de parámetros que encajen de forma sencilla en el vector de estado del sistema.

A la vista de las hipótesis realizadas, cabe enumerar las siguientes desventajas de esta clase de algoritmos:

1. La premisa de partida del algoritmo, que supone una distribución gaussiana para el estado del sistema, puede no corresponderse con la realidad. En el mejor de los casos, las linealizaciones introducidas en los modelos harán que las estimaciones de los momentos de esta distribución degeneren a lo largo del tiempo no correspondiéndose con sus auténticos valores.
2. El punto anterior indica además un grave problema de consistencia del algoritmo, que hace que el nivel de confianza de la estimación obtenida no se corresponda con el auténtico error cometido. Esto origina que la exactitud de los resultados obtenidos por el filtro sean a menudo impredecibles, observándose saltos bruscos en la estimación sin causa aparente alguna.
3. El coste computacional crece al cuadrado con el número de objetos contenidos en el mapa. Este hecho limita su aplicación en tiempo real a mapas formados por unos pocos cientos de objetos.
4. No siempre es sencillo o inmediato extraer características del entorno asimilables a una clase particular de objeto. En ocasiones ni siquiera es preciso extraer información que pueda describirse empleando primitivas geométricas simples como puntos, segmentos, arcos de circunferencia o planos (por ejemplo, en el interior de una mina).
5. Es preciso disponer de un método de asociación de datos robusto que permita emparejar las observaciones realizadas con los elementos contenidos en el mapa. Una asociación de datos errónea provocará casi con total seguridad la divergencia irrecuperable de la estimación del filtro.

A pesar de los inconvenientes que surgen al emplear esta solución, se trata de la más extendida en la literatura y presenta interesantes propiedades que resultan muy atractivas:

1. El hecho de describir el entorno a partir de entidades geométricas descriptibles de manera compacta, se corresponden más con una visión antropomórfica del mundo, que representa este último a través del concepto del objeto y sus relaciones.
2. Estas soluciones cuentan con una larga tradición, lo cual hace que su estructura, ventajas e inconvenientes sean bien conocidos. Históricamente se han planteado múltiples soluciones que intentan paliar algunos de los problemas anteriormente mencionados.
3. Al mantenerse la matriz de covarianzas del sistema completa, es capaz de cerrar bucles exitosamente.

Mapas de ocupación de celdillas

Los mapas de ocupación de celdillas fueron introducidos por Hans Moravec y Alberto Elfes a mediados de la década de 1980. El método se basa en discretizar el espacio, dividiéndolo en unidades de tamaño predefinido, que se clasifican como ocupadas o vacías con un determinado nivel de confianza o probabilidad.

Estas soluciones parten de la hipótesis de que la posición del robot es conocida. En la práctica, se necesita de algún método de localización que estime la posición del robot en cada instante que, en este caso, no es considerada una variable estocástica. La precisión que alcanzan estos mapas en la descripción del entorno (tanto mayor cuanto más fina es la división del espacio), permite que el algoritmo de localización empleado acumule errores reducidos a lo largo de intervalos prolongados de tiempo. Así pues, la mayor desventaja de estos métodos es la pérdida de potencia que se deriva de no tener en cuenta la incertidumbre asociada a la posición del robot, lo cual origina que su capacidad para cerrar bucles correctamente se vea mermada.

Entre sus ventajas cabe destacar las siguientes:

1. El algoritmo es robusto y su implementación sencilla.
2. No hace suposiciones acerca de la naturaleza geométrica de los elementos presentes en el entorno.
3. Distingue entre zonas ocupadas y vacías, consiguiendo una partición y descripción completa del espacio explorado. Por este motivo es popular en tareas de navegación, al facilitar la planificación y generación de trayectorias empleando métodos convencionales.
4. Permite descripciones arbitrariamente densas o precisas del mundo, simplemente aumentando la resolución de la rejilla que lo divide (p. ej. disminuyendo el tamaño de las celdillas individuales). Como es lógico, esto va en detrimento del rendimiento computacional del algoritmo.
5. Permite una extensión conceptualmente simple al espacio tridimensional.

Recientemente han aparecido variantes de este método que mejoran sustancialmente algunos aspectos. Por ejemplo, los mapas de cobertura que mantienen una probabilidad de ocupación para cada celdilla que se ajusta más correctamente a casos en los que esta se encuentra sólo parcialmente ocupada, o el DP-SLAM, que mantiene varias hipótesis sobre el mapa construido y utiliza un filtro de partículas para estimar la que más se ajusta a la realidad.

Solución factorizada del filtro de Bayes

En la tesis de Michael Montemerlo se realiza un detallado análisis de la formulación Bayesiana del problema SLAM, y se llega a una conclusión que resulta muy intuitiva y casi evidente. Si el camino verdadero que recorre el robot fuera perfectamente conocido, la estimación del mapa sería un problema de solución casi inmediata. Además supondría una ventaja computacional, puesto que la estimación de los objetos que componen el mapa sería independiente, ya que no estarían relacionados por la incertidumbre común asociada a la posición del sensor del robot. Por tanto, las correlaciones entre los objetos serían nulas. Es algo parecido a lo que sucede con los mapas de ocupación de celdillas, que también suponen conocida la localización del robot en todo momento.

SLAM visual

El SLAM visual consiste en el empleo de una cámara para desarrollar un mapeado y localización simultáneos. Este tipo de algoritmos, o técnicas, están compuestos fundamentalmente por 5 módulos diferenciados.Estos son la inicialización, la localización, el mapeado, la re-localización y por último la optimización del mapeado. Cada una de los diferentes algoritmos desarrollados hasta la fecha emplea diferentes técnicas para cada uno de estos 5 puntos. Algunos de los algoritmos más conocidos son PTAM, LSD SLAM y ORB SLAM entre otros.

Véase también

• Planta (arquitectura)
• Robot autónomo
• Sistema de posicionamiento en interiores

Enlaces externos

• Smith, Randall; Self, Matthew; Cheeseman, Peter (1987). «Estimating uncertain spatial relationships in robotics». 1987 IEEE International Conference on In Robotics and Automation. Proceedings. 4. 

• Montemerlo, Michael (2003). «FastSLAM: A Factored Solution to the Simultaneous Localization and Mapping Problem with Unknown Data Association». doctoral dissertation, tech. report CMU-RI-TR-03-28, Robotics Institute, Carnegie Mellon University. 

• «OpenSLAM» (en inglés). 

• Datos: Q1203659