Proyecto Fin de Carrera Implementación del FKE para SLAM
5
2. El problema de la localización y el mapeo simultáneo
2.1. Introducción
El problema de localización y mapeo simultáneo (SLAM), propone si es posible para un
robot móvil situarse en una posición desconocida dentro de un sistema también desconocido y
construir de forma incremental un mapa del entorno mientras simultáneamente determina su
posición utilizando el mapa.
La solución al problema del SLAM ha sido uno de los grandes éxitos de la comunidad
científica de la última década. Este problema ha sido formulado y resuelto como un problema
numérico utilizando diferentes métodos. También ha sido implementado en diferentes campos
desde robots en entornos cerrados hasta robots al aire libre, bajo el agua y en sistemas aéreos.
Desde los puntos de vista teóricos y numéricos el problema del SLAM se puede considerar
resuelto.
Proyecto Fin de Carrera Implementación del FKE para SLAM
6
2.2. Tipos de mapas
2.2.1. Introducción
El tipo de mapa que se va a generar mediante la resolución del problema del SLAM es una
parte tan importante como el método que se llevará a cabo para su resolución.
Existen diferentes tipos de navegación en un entorno en función de la utilización o no de un
mapa para llevar acabo el movimiento del robot por dicho entorno. La siguiente clasificación
muestra los tres tipos posibles:
1. Navegación basada en mapas. Estos sistemas dependen de modelos geométricos
creados por el usuario o mapas topológicos del ambiente.
2. Navegación basada en la construcción de mapas. Estos son sistemas que utilizan un
sistema sensorial para construir sus propios modelos geométricos o topológicos del
ambiente, utilizando el mapa creado para su navegación.
3. Navegación sin mapas. Estos son sistemas que no usan la representación explícita de
todo lo que hay en el espacio de navegación sino que tratan de reconocer o reorganizar
los objetos que allí se encuentran.
Es obvio que el problema del SLAM es un sistema de navegación incluido en la segunda
categoría. Ahora habrá que indicar cómo es el mapa que se construirá con las sucesivas
implementaciones del algoritmo de resolución del SLAM.
Una buena representación debe ser lo suficientemente rica para que el robot pueda
localizarse en el mismo y navegar por él de forma autónoma, mientras tiene una baja
complejidad espacial.
2.2.2. Mapas métricos
Estos mapas son útiles para localizar el robot con gran exactitud y trazar un camino en
presencia de obstáculos, sin embargo requieren mucho espacio de memoria. Se pueden
dividir en dos categorías:
2.2.2.1 Mapas creados a partir de hitos
Esta clase de mapas describen el entorno como un conjunto de rasgos o marcas
localizados espacialmente. Una de las ventajas de este tipo de representación es su
compacidad, que lo hace muy útil para sistemas de dos dimensiones de gran extensión
y para entornos en tres dimensiones. Además un mapa está representado como un
Proyecto Fin de Carrera Implementación del FKE para SLAM
7
punto en nlℜ donde n es la dimensión de la función de espacio y l es el número de
características del entorno. El posterior trabajo sobre los mapas puede ser fácilmente
modelado como una gaussiana multivariable, lo que permite el análisis matemático del
problema.
A pesar de las ventajas previas, los mapas basados en hitos tienen también
importantes inconvenientes:
- Una gran cantidad de información está almacenada en un pequeño conjunto de
puntos u otras características simples, así que desaprovecha la mayoría de información
proporcionada por la exactitud de los modernos sistemas de sensores.
- Las características deben ser únicas para que puedan ser identificadas. Este
problema se conoce como aliasing o asociación de la información, y debe ser abordado
explícitamente ya que una asociación indebida provoca la divergencia en las
estimaciones.
- Dado que se van a trabajar con puntos de referencia sobre el mapa, habrá que
emplear algoritmos de extracción de características asumiendo que ciertas estructuras
deben estar presente en el entorno. Estos algoritmos varían dependiendo del sensor
utilizado. De un lado, usando sonar o sensor láser, hay dos tipos de rasgos: los rincones
y las líneas. La extracción es llevada a cabo utilizando diferentes algoritmos: Split and
merge [1], Transformada de Hough [2] y/o RANSAC [3]. Por otro lado está la utilización
de cámaras, donde se extraen los rasgos a partir de la apariencia de la información
(forma, textura, color, etc). Los rasgos se representan como puntos y son obtenidos
usando diferentes algoritmos: Harris [4]. Por otra parte una sola cámara sólo
proporciona información de la orientación, así que es necesario un cuidadoso
procedimiento de inicialización en este caso.
2.2.2.2 Mapas de densidad o de malla
Cuando se necesita mucha resolución, típica para planificar una ruta con exactitud,
o el entorno tiene una estructura libre. Los hitos no aportan suficiente información y,
entonces se usan los mapas de densidad. Estos pueden desarrollarse para celdas de dos
o tres dimensiones, donde se almacena la probabilidad de estar ocupadas o libres. Los
algoritmos para construir mapas de este tipo se basan en la estructura de la rejilla de
ocupación desarrollada por H. Moravec y A. Elfes [5]. Una de las principales
características de esta forma de organizar la información es la capacidad de representar
entornos desestructurados, y se puede aumentar la exactitud cambiando la resolución
de la celda. Además no hay necesidad de utilizar algoritmos para extraer las
características del entorno, reduciendo los problemas de aliasing y convirtiendo el
Proyecto Fin de Carrera Implementación del FKE para SLAM
8
algoritmo en un proceso más robusto. Sin embargo, las celdas son independientes así
que no se puede expresar una relación entre las mismas. Esta limitación implica que
cuando se trabaja con entornos dinámicos, un grupo de celdas tengan que moverse
siempre juntas.
Este tipo de mapas se construye normalmente utilizando sensores láser y sensores
sonar, debido a la necesidad de obtener medida del rango y de la orientación. Sin
embargo, en los últimos tiempos se ha vivido un gran desarrollo utilizando cámaras
estéreo.
2.2.3. Mapas topológicos
Un mapa topológico representa el entorno a través de un gráfico. Los nodos
representan lugares del entorno, mientras que las líneas representan relaciones entre los
lugares. A diferencia de un mapa métrico, en un mapa topológico puro el sentido espacial
de los nodos y las relaciones se pierde. Esto hace a este tipo de representación menos
sensible a los problemas de escala: si el tamaño del entorno crece, el mapa métrico que lo
describe también crece, mientras que el tamaño del mapa topológico correspondiente se
mantiene igual.
La definición precisa de un mapa topológico depende de la ontología, es decir, del
significado de “lugar” y “relación” que se especifique. Diferentes ontologías dan lugar a
diferentes definiciones.
A pesar de sus atractivos, es difícil usar estas representaciones que no disponen de
ningún tipo de información métrica. Recientemente, se han realizado algunos avances en el
campo del mapeo topológico. El primero se refiere al uso de la teoría de probabilidad.
Hasta ahora, los mapas topológicos se habían construido usando algoritmos para tal fin
basados en lógica o inferencia. Ahora se presenta el concepto de mapa topológico, con la
introducción del concepto de distribución sobre topologías. El segundo aspecto se basa en
la interpretación semántica de un lugar. Los lugares eran clasificados de acuerdo sólo a las
propiedades de conectividad, actualmente utilizando un clasificador AdaBoost [6] se
construye una topología del entorno, sobre la base de la comprensión humana.
2.2.4. Mapas jerárquicos
Las relaciones entre diferentes partes del entorno son normalmente locales: elementos
del entorno que se encuentran cercanos entre sí están altamente correlacionados, mientras
que elementos que están lejos están débilmente correlacionados. Los mapas jerárquicos
tratan de captar esta característica. El entorno es descrito como un conjunto de pequeños
Proyecto Fin de Carrera Implementación del FKE para SLAM
9
mapas globales, mientras que las limitaciones globales entre ellos se mantienen en un mapa
global común. En principio, esta jerarquía se puede repetir para varios niveles, pero la
mayoría de los enfoques en la literatura suelen utilizar sólo dos capas.
Dentro de la jerarquía de dos capas el mapa global utiliza un mapa gráfico para
mantener la estructura topológica de las posiciones de los mapas locales, y para construir
una visión local del entorno alrededor del robot. Este gráfico es sustancialmente a una
representación topológica, ya que expresa de una manera compacta las relaciones métricas
entre las entidades, mientras que en un mapa topológico, el significado de la métrica se
pierde.
Proyecto Fin de Carrera Implementación del FKE para SLAM
10
2.3. Historia del problema del SLAM
El problema probabilístico del SLAM se presentó por primera vez en la Conferencia de
IEEE de Robótica y Automatización de 1986 que tuvo lugar en San Francisco (California). Los
métodos probabilísticos acababan de ser introducidos en campos como la robótica y la
inteligencia artificial (IA). Un número de investigadores habían estado buscando y aplicando
métodos de estimación de la teoría para los problemas de mapeo y localización; algunas de
estas personas fueron Meter Cheeseman, Jim Crowley, y Hugh Durrant-Whyte. Durante el
transcurso de la conferencia se escribieron numerosas discusiones sobre la consistencia del
mapeo. Pero también se hicieron grandes aportaciones gracias a Raja Chatila, Oliver Faugeras,
Randal Smith y otros.
El resultado de estas conversaciones fue el reconocimiento de la consistencia del problema
probabilístico y que éste era un problema fundamental en robótica con una gran carga
conceptual y computacional que necesitaba ser resuelto. Durante los siguientes años una serie
de documentos fueron desarrollados, como los trabajos de Smith y Cheesman [7], y de Durrant-
Whyte [8], proporcionando una base estadística para describir las relaciones entre los hitos
(puntos de referencia geográficos) y la manipulación de la geometría desconocida. Una clave de
estos trabajos fue demostrar que había un gran grado de correlación entre las estimaciones de
las localizaciones de los diferentes hitos en el mapa y que ésta crecía conforme se aumentaban el
número de observaciones sucesivas.
Al mismo tiempo N. Ayache y O. Faugeras [9] trabajaban con sistemas de navegación
basados en visión, J. Crowley [10], y R. Chatila y J. L. Laumond [11] estaban trabajando en la
navegación basada en sonar con robots móviles usando los algoritmos propuestos por el filtro
de Kalman. Los resultados de estos dos trabajos tenían mucho en común y tuvieron clara
influencia en el trabajo de Smith y otros [12]. En el documento desarrollado por éste último se
mostraba un robot móvil moverse a través de un entorno desconocido realizando observaciones
de unos ciertos hitos, las estimaciones de estos hitos tenían que estar necesariamente
correlacionas debido al error en la localización del vehículo. La implicación de esto fue: una
solución completa y consistente de la combinación de los problemas de mapeo y localización
requiere el conjunto de estados de la posición del vehículo y las posiciones de cada unos de los
hitos para que la posición del vehículo pueda ser establecida mediante la observación
continuada de los hitos. Esto implicaba utilizar un estimador para trabajar con un gran vector
de estados del orden del cuadrado del número de hitos que haya definidos en el mapa.
Este trabajo, sin embargo, no mostraba una convergencia en las propiedades del mapa o un
comportamiento estable. Así que finalmente fue ampliamente asumido que los errores del mapa
estimado no convergerían, ni las trayectorias aleatorias con un crecimiento de los errores no
acotado. Así que dada la complejidad computacional del problema del mapeo y sin el
Proyecto Fin de Carrera Implementación del FKE para SLAM
11
conocimiento de la convergencia en las características del mapa, los investigadores se centraron
en una serie de aproximaciones para la consistencia del problema del mapeo, tal que asumieron
o incluso forzaron las relaciones entre los hitos para minimizarlos o eliminarlos, para reducir el
filtro completo a una serie de hitos desacoplados para el filtro del vehículo. También por estas
razones, el trabajo teórico de combinar el problema de localización y mapeo llevaba a parar
temporalmente el desarrollo para centrarse en uno u otro de los problemas de forma
independiente.
El cambio conceptual vino con la observación de que la combinación de los problemas de
mapeo y simulación, una vez estimados como problemas independientes, convergían. Lo más
importante fue reconocer que la correlación entre los hitos, que la mayoría de los investigadores
habían tratado de minimizar, eran parte crucial del problema y cuanto más crecían las
correlaciones mejor era la solución.
La estructura del problema del SLAM, la convergencia en el resultado y la acuñación del
acrónimo SLAM fueron por primera vez presentadas en un panfleto sobre robots móviles en el
Simposio Internacional de Investigación Robótica de 1995 [13]. La base del desarrollo teórico de
la convergencia y la mayoría de los resultados iniciales fueron desarrolladas por M. Csorba.
Varios grupos que estaban trabajando en la localización y mapeo, principalmente en el Instituto
de Tecnología de Massachussets, Zaragoza, el ACFR (Australian Centre for Field Robotics) de
Sydney y otros, empezaron a trabajar en los comienzos del SLAM (también llamado en esta
época CML, Concurrent mapping and localization) en espacios cerrados, abiertos y bajo el agua.
Por este tiempo el trabajo se centraba en probar la eficiencia computacional y
direccionamiento de cuestiones en la asociación de la información, o los bucles sin fin. En el
Simposio Internacional de Robótica de 1999 [14] se produjo la primera sesión sobre SLAM donde
se alcanzó un acercamiento entre el SLAM basado en el filtro de Kalman y los métodos
probabilísticos para la localización y el mapeo introducidos por S. Thurn [15]. En la Conferencia
Internacional de Robótica y Automatización (ICRA) del Institute of Electrical and Electronics
Engineers (IEEE) de 2000 el trabajo con SLAM atrajo a 15 investigadores que buscaban
soluciones para la complejidad, la asociación de la información y retos de implementación. El
siguiente taller de SLAM organizado por la Internet Content Rating Association (ICRA) en 2002
atrajo a 150 investigadores con toda una variedad de aportaciones y aplicaciones. La escuela de
verano de SLAM cuyo anfitrión fue Henrik Christiensen en la KTH de Estocolmo convocó a
investigadores junto con estudiantes del doctorado en investigación de todo el mundo y tuvo
un gran éxito en el desarrollo del campo. Los interesados por el SLAM han crecido
exponencialmente en los últimos años, y los talleres han seguido organizándose por ICRA e
IROS (Intelligent Robots and Systems). La escuela de verano se ha seguido celebrando en
Toulouse (Francia) en el 2004 y en Oxford (Inglaterra) en 2006.
Proyecto Fin de Carrera Implementación del FKE para SLAM
12
2.4. Formulación y estructura del problema del SLAM
El SLAM es un proceso en el que un robot móvil puede construir un mapa de su entorno y
al mismo tiempo usar ese mapa para saber su localización. En SLAM, la trayectoria del robot y
las posiciones de los puntos de referencia o hitos están estimadas en línea sin la necesidad de un
conocimiento previo de la localización.
El esquema general del problema del SLAM consta de cuatro pasos:
1. Adquirir la información sensorial.
2. Detectar los puntos de referencia marcados para identificar los puntos de interés del entorno.
3. Establecer correspondencias entre lo observado y lo esperado. Esto asume analizar lo
observado con respecto a una base de datos o unos criterios bien definidos de comparación para
poder discernir que es lo que está percibiendo el robot.
4. Cálculo de la posición. Gracias a la comparación realizada se puede hacer el cálculo de la
posición del robot.
2.4.1 Introducción
Se considera un robot moviéndose a través de
un entorno realizando observaciones de un
número de hitos desconocidos mediante un
sensor. Para el instante k las siguientes variables
están definidas:
Figura 1
kx Vector de estado describiendo la posición y la orientación del vehículo.
ku Vector de control aplicado en el instante 1−k para llevar al vehículo desde su posición anterior hasta la actual kx en el instante k .
im Vector que describe la localización del hito ésimoi − , cuya localización se asume a través del tiempo invariante.
ikz
Observación tomada desde el robot de la localización del ésimoi − hito en el instante k . Cuando haya múltiples observaciones de diferentes hitos en el mismo instante o cuando un hito específico no sea relevante la observación se escribirá para simplificar como kz .
},{},,,{ 1:010:0 kkkk xXxxxX −== L Todas las anteriores posiciones del robot.
},{},,,{ 1:010:0 kkkk uUuuuU −== L Todos los vectores de control dados al robot.
},,,{ 21 nmmmm L= Todas las posiciones de todos los hitos.
},{},,,{ 1:010:0 kkkk zZzzzZ −== L Todas las observaciones de los diferentes hitos.
Proyecto Fin de Carrera Implementación del FKE para SLAM
13
2.4.2 SLAM probabilístico
Para trabajar desde el punto de vista de la probabilidad en el problema del mapeo y la
localización simultánea es necesario que la probabilidad de la distribución
),,|,( 0:0:0 xUZmxP kkk (1)
sea calculada para todos los instantes k . Esta distribución de probabilidad describe el
conjunto de las posibles posiciones del robot y de los hitos para un instante posterior a
k dado el conocimiento de las anteriores observaciones, las señales de control efectuadas
incluyendo la del instante k y conociendo la posición original del robot. En general, es
deseable una solución recursiva para el problema del SLAM. Comenzando con una
estimación de la distribución ),,|,( 01:01:01 xUZmxP kkk −−− en el instante 1−k el conjunto
posterior, siguiendo un control ku y una observación kz , se computaría utilizando el
teorema de Bayes. Este cálculo requiere la definición de un modelo de estado de transición
y un modelo de observación que describan el efecto del control y de la observación
respectivamente.
El modelo de observación describe la probabilidad de hacer una observación kz cuando
la posición del robot y las de los hitos son conocidas y se pueden describir como
),|( mxzP kk (2)
Es razonable asumir que una vez que la localización del robot y el mapa están
definidos, las observaciones son condicionalmente independientes dado el mapa y la
posición del robot.
El modelo de movimiento para el robot puede describirse en términos de una
distribución de probabilidad de la transición de estados como
),|( 1 kkk uxxP − (3)
Esto es, el estado de transición es asumido que debe ser un proceso de Harkov en el que
el siguiente estado kx depende únicamente del estado inmediatamente precedente 1−kx y el
control aplicado ku y es independiente de las observaciones y del mapa.
El algoritmo del SLAM se implementa en dos pasos iterativos de predicción y
corrección:
Tiempo de actualización (predicción)
101:01:0110:01:0 ),,|,(),|(),,|,( −−−−−− ×= ∫ kkkkkkkkkk dxxUZmxPuxxPxUZmxP
(4)
Proyecto Fin de Carrera Implementación del FKE para SLAM
14
Medidas de actualización (corrección)
),|(),,|,(),|(),,|,(
:01:0
0:01:00:01:0
kkk
kkkkkkkk UZzP
xUZmxPmxzPxUZmxP−
−− =
(5)
Las ecuaciones (4) y (5) proporcionan un método recursivo para calcular el conjunto
posterior ),,|,( 0:01:0 xUZmxP kkk − para el robot del estado kx y el mapa m en el instante
k , basado en todas las observaciones kZ :0 y todas las salidas de control kU :0 incluyendo el
instante k . La recursión es una función de un modelo de robot ),|( 1 kkk uxxP − y un
modelo de observación ),|( mxzP kk .
Merece la pena observar que el problema de construir el mapa puede ser formulado
como el cómputo de la densidad condicional ),,|( :0:0:0 kkk uZxmP . Esto asume que la
localización del robot kx es conocida (o al menos determinada) en cada instante, sujeto al
conocimiento de la posición inicial. Un mapa m es entonces construido por la fusión de las
observaciones desde diferentes localizaciones. En cambio, el problema de la localización
puede ser formulado como el cómputo de la distribución de probabilidad
),,|( :0:0 mUZxP kkk . Esto asume que las localizaciones de los hitos son conocidos con
certeza, y el objetivo es calcular una estimación de la posición del robot con respecto a estos
hitos.
2.4.3 Estructura del SLAM probabilístico
Para simplificar el desarrollo se quitarán los límites en las variables históricas de la
ecuación (1) y se escribirá el conjunto requerido posterior en el mapa y en la localización del
robot como )|,( kk zmxP e incluso ),( mxP k cuando el contexto lo permita.
El modelo de observación ),|( mxzP kk indica de forma explícita la dependencia entre
las observaciones del robot y las posiciones de los hitos. Por tanto no se podrá dividir el
conjunto posterior como
)|()|()|,( kkkkk zmPzxPzmxP ≠ ya que es conocido desde los primeros documentos en el mapeo consecuente que una
partición como esta conduce a estimaciones incoherentes [16]. De cualquier forma, el
problema del SLAM tiene más estructuras que son inmediatamente obvias desde estas
ecuaciones.
Refiriéndonos otra vez a la figura 1, se puede observar que gran parte del error entre la
estimación y la posición real de los hitos es común entre todos ellos y es en cambio debida a
una única fuente; es el error en el conocimiento de dónde se encuentra el robot cuando las
Proyecto Fin de Carrera Implementación del FKE para SLAM
15
observaciones de los hitos se han hecho. Sucesivamente, esto implica que los errores en la
estimación de las posiciones de los hitos están fuertemente relacionados. Prácticamente,
esto significa que la posición relativa entre dos hitos cualesquiera, ji mm − , puede ser
conocida con precisión, incluso cuando la posición absoluta del hito im es bastante incierta.
Desde el punto de vista de la probabilidad esto significa que el conjunto de la densidad de
probabilidad para el par de hitos ),( ji mmP está muy concentrada incluso cuando la
densidad marginal )( imP puede estar bastante dispersa.
El descubrimiento más importante en SLAM fue observar que las correlaciones entre
los hitos estimados crece monótonamente cuanto mayor es el número de observaciones
realizadas. (Estos resultados sólo han sido probados para el caso de una Gaussiana lineal [17]. La raíz formal para el caso de un problema probabilística general es un problema
abierto). Prácticamente, esto significa que el conocimiento de la posición relativa de los
hitos siempre mejora y nunca diverge, a pesar del movimiento del robot. En términos
probabilísticos, esto significa que el conjunto de la densidad de probabilidad de todos los
hitos )(mP llega a ser monótonamente más centrada conforme se realizan más
observaciones.
Esta convergencia sucede porque las observaciones hechas por el robot pueden ser
consideradas como medidas casi independientes de la posición relativa de los hitos.
Teniendo en cuenta la figura 1, se considera el robot situado en kx observando los dos hitos
im y jm . La posición relativa de los hitos observados es claramente independiente del
rango de coordenadas del robot, y sucesivas observaciones desde esta posición fija darán
lugar a mayor independencia en la relación de las medidas relativas entre hitos. Ahora, el
robot se mueve a la situación 1+kx , observa otra vez el hito jm . Esto permite que la
localización estimada del robot y del punto de referencia sea actualizada respecto de la
localización previa kx . Sucesivamente, esta propagación hacia atrás establece el hito im ,
incluso si éste no es visto desde una nueva localización. Esto ocurre porque dos hitos están
altamente correlacionados (su localización relativa está bien definida) por mediciones
anteriores. Adicionalmente, el hecho de que la misma información de la medida sea usada
para establecer estos dos hitos los hace más correlacionados. El término “casi medidas
independientes” es apropiado porque los errores observados estarán correlacionados a
través de los sucesivos movimientos del robot. También observar en la figura 1, en la
localización 1+kx , el robot observa nuevos hitos relativos a jm . Estos nuevos hitos estarán
así inmediatamente vinculados y correlacionados al resto del mapa. Establecimientos
posteriores de estos hitos determinarán también el hito jm y a través de éste el hito im y
Proyecto Fin de Carrera Implementación del FKE para SLAM
16
así consecutivamente. Esto es, todos los hitos al final forman una red vinculada por las
posiciones relativas o las correlaciones cuya precisión o cuyo valor incrementa en cuanto
una nueva observación es realizada.
Este proceso puede visualizarse en la figura 2 como una red de líneas elásticas
conectando todos los hitos juntos. Una observación en la vecindad actúa como un cambio
de posición en el sistema de rebotes de manera que su efecto es mayor en la vecindad y,
dependiendo de las propiedades de dureza (correlación), disminuye con la distancia a los
otros puntos de referencia. Conforme el robot se mueve en este entorno y toma
observaciones de los diferentes puntos de referencia, los rebotes se van volviendo más
rígidos (o monótonos). Al final se obtiene un mapa rígido de puntos de referencia o un
mapa relativo fiel al entorno. A medida que se va construyendo el mapa, la precisión de la
posición medida por el robot relativa al mapa es delimitada sólo por la calidad del mapa y
la medida relativa del sensor. En el límite teórico, la precisión de la localización relativa del
robot se va haciendo igual a la precisión de la posición alcanzable a partir del mapa dado.
Figura 2
Proyecto Fin de Carrera Implementación del FKE para SLAM
17
2.5. Soluciones al problema del SLAM
2.5.1 Introducción
Las soluciones al problema del SLAM implican encontrar una representación
aproximada para el modelo de observación y el modelo de movimiento que permita un
eficiente y consistente cálculo de la primera y posteriores distribuciones en las ecuaciones
(4) y (5). Con diferencia, la representación más común es mediante el modelo estado-
espacio con un ruido gaussiano añadido, destacando el uso del filtro de Kalman extendido
(FKE) para resolverlo. Una representación alternativa importante es describir el
movimiento del robot (3) como un conjunto de ejemplos de distribuciones de probabilidad
más generales no gaussianas. Esto lleva a usar el filtro de partículas Rao-Blackwellized, o el
algoritmo FastSLAM, para resolver el problema del SLAM. Mientras que el FKE y el
método de FastSLAM son dos de los más importantes métodos para obtener una solución,
nuevas alternativas que ofrecen un mayor potencial han sido propuestas incluyendo el uso
de la formulación de la información-estado o forma canónica.
2.5.2 Filtro de Kalman extendido para el problema del SLAM
El filtro de Kalman es un algoritmo desarrollado por Rudolf. E. Kalman utilizado para
estimar el estado no medible de un sistema dinámico lineal cuando éste esta sometido a un
ruido blanco.
El estado de un sistema dinámico es el conjunto más pequeño de variables tal que el
conocimiento de los valores de estas variables en un instante 0t junto con el conocimiento
de los valores de la señal de entrada para todos los instantes posteriores a éste 0t permite
determinar el comportamiento y evolución del sistema para cualquier instante posterior.
Un ruido blanco es un proceso aleatorio que se puede considerar como una secuencia
cuyos elementos son variables aleatorias independientes entre sí y con idéntica distribución.
σ~)]()([
0)]()([
=
=
ji
ji
txtxE
txtxE
jiji
=≠
0)]([ =txE La idea que desarrolla el filtro de Kalman para estimar un sistema dinámico estable es
generar un sistema idéntico al original al cual sí se le puede medir el estado interno
directamente. Si el sistema original y su “copia” son sometidos a los mismos estímulos, se
puede esperar que conforme transcurra el tiempo ambos sistemas se empiecen a comportar
de la misma manera dado que sus estados internos tienden a parecerse cada vez más. Así se
Proyecto Fin de Carrera Implementación del FKE para SLAM
18
podrá disponer del estado interno de la “copia” como una aproximación del estado interno
del sistema original.
Para acelerar la convergencia entre sistemas se realimenta a la “copia” con una entrada
corregida que consiste en la misma entrada que el sistema original más la diferencia de la
salida de los dos sistemas multiplicada por un factor calculado a partir de las varianzas de
los ruidos que los afectan.
Definición de un filtro de Kalman en tiempo discreto:
kkkk
kkkkkk
vxCzwuBxAx
+=++= −−−−− 11111
donde kw es un ruido blanco de valor promedio igual a cero y con varianza kQ en el
instante k , y kv es también un ruido blanco de valor promedio igual a cero y con varianza
kR en el instante k .
El filtro de Kalman permite estimar el estado kx a partir de las mediciones anteriores de
kkkk RQzu ,,, y las estimaciones anteriores de ).(tx
Definición del Filtro de Kalman en tiempo continuo:
)()()()(
)()()()()()(
tvtxtCtz
twtutBtxtAtxdtd
+=
++=
donde )(tw es un ruido blanco de valor promedio igual a cero y con varianza )(tQ en
el instante t , y )(tv es también un ruido blanco de valor promedio igual a cero y con
varianza )(tR en el instante t .
El filtro de Kalman permite estimar el estado )( dttx + a partir de las anteriores
mediciones de )(),(),(),( tRtQtztu y las estimaciones de ).(tx
Utilizando esta última definición vamos a crear el sistema “copia” del original el cual
estará regido por las siguientes ecuaciones:
)()(ˆ)()(ˆ
)()(ˆ)()(ˆ)()(ˆ
tvtxtCtz
twtutBtxtAtxdtd
+=
++=
El error en la estimación del estado estará dado por:
)()(ˆ)( txtxtd −=
El error en la salida del observador estará dado por:
)()()()(ˆ)( tdtCtztzte =−=
Se puede alimentar el sistema “copia” con la siguiente entrada modificada
)()()()()()(ˆ tdtKCtutKetutu −=−=
Proyecto Fin de Carrera Implementación del FKE para SLAM
19
Quedando su ecuación de transición como
)()]()()()[()(ˆ)()(ˆ twtdtKCtutBtxtAtxdtd
+−+=
Restando esta ecuación menos la ecuación de transición del sistema original se obtiene
[ ] [ ])()()()()()()]()()()[()(ˆ)()()(ˆ twtutBtxtAtwtdtKCtutBtxtAtxdtdtx
dtd
++−+−+=−
[ ] [ ] )()()()()()()()()(ˆ)()( tdtKCtBtAtdtKCtBtxtxtAtddtd
−=−−=
Esta última ecuación demuestra que la dinámica del error puede ser modificada
mediante el conocimiento de K , que puede ser calculado a partir de la varianza de los
ruidos que afectan a la salida y a la entrada.
En el caso de que el sistema dinámico no sea lineal, es posible usar una modificación del
algoritmo denominada “filtro de Kalman Extendido” (FKE), el cual linealiza el sistema en
torno al )(ˆ tx estimado actualmente para calcular la ganancia y la dirección ocupada. En este
caso, en vez de haber matrices )(tA , )(tB y )(tC , hay dos funciones ),,( wuxf y
),( vxh que representan la transición de estado y la observación respectivamente.
Aplicando esto al problema del SLAM, se tiene que el FKE describe el movimiento del
robot como
( ) kkkkkkk wuxfxuxxP +=⇔ −− ,),|( 11
donde ( )f es el modelo cinemático del robot y donde kw es un ruido aditivo, cero
significa que no hay correlación entre las alteraciones del movimiento gaussiano con la
covarianza kQ . El modelo de observación está descrito como
( ) kkkkkk vuxhzmxzP +=⇔ − ,),|( 1
donde ( )h describe la geometría de la observación y donde kv es un ruido aditivo, cero
significa que no hay relación entre los errores de observación gaussiana con la covarianza
kR
Con estas definiciones, el método estándar FKE puede ser aplicado para calcular la
media
⎥⎦
⎤⎢⎣
⎡=⎥
⎦
⎤⎢⎣
⎡k
k
k
kk Zmx
Emx
:0| |)
)
y la covarianza
⎥⎥⎦
⎤
⎢⎢⎣
⎡⎟⎟⎠
⎞⎜⎜⎝
⎛−−
⎟⎟⎠
⎞⎜⎜⎝
⎛−−
=⎥⎦
⎤⎢⎣
⎡= k
T
k
kk
k
kk
mmxmT
xmxxkk Z
mmxx
mmxx
EPPPP
P :0| |)
)
)
)
Proyecto Fin de Carrera Implementación del FKE para SLAM
20
De la posterior distribución ),,|,( 0:01:0 xUZmxP kkk − de la unión de:
Tiempo de establecimiento
( )kkkkk uxfx ,1|11| −−− = )) (8)
kT
kkxxkkxx QffPP +∇∇= −−− 1|1,1|, (9)
donde f∇ es el jacobiano de f evaluada en la estimación 1|1 −− kkx) . No hay generalmente
necesidad de marcar un tiempo de establecimiento para hitos estacionarios (un tiempo de
establecimiento, sin embargo, sí es necesario para hitos que pueden moverse)
Medidas de actualización
[ ] ( )[ ]11|11|| , −−−− −+=⎥⎦
⎤⎢⎣
⎡kkkkkkkk
k
kk mxhzWmxmx )))))
)
(10)
Tkkkkkkk WSWPP −= −1|| (11)
donde
kT
kkk RhhPS +∇∇= −1|
11|
−− ∇= s
Tkkk ShPW
Y donde h∇ es el jacobiano de h evaluado en 1| −kkx) y en 1−km) .
Esta solución del FKE-SLAM es muy bien conocida y hereda muchos de los mismos
beneficios y problemas que la solución estándar del filtro de Kalman extendido para
navegación o seguimiento de problemas. Cuatro de las cuestiones claves son:
Convergencia
En el problema del FKE-SLAM, la convergencia del mapa se manifiesta en la
convergencia monótona del determinante de la matriz kmmP , del mapa de covarianzas y
todas las submatrices de pares de hitos, tienden a cero. La varianza de un hito individual
converge hacia el menor valor determinado por la incertidumbre inicial en la posición del
robot y de las observaciones.
Esfuerzo computacional
El paso de la actualización requiere que todos los hitos y el conjunto de la matriz de
covarianza sean establecidos con cada observación realizada. Esto significa que el cálculo
computacional crece cuadráticamente con el número de hitos. Ha habido un gran esfuerzo
de trabajo subyacente para desarrollar variantes eficientes de la solución FKE-SLAM y se
han demostrado mejoras en tiempo real con varios miles de puntos de referencia.
Asociación de la información
La formulación estándar de la solución del FKE-SLAM es especialmente frágil con la
incorrecta asociación de observaciones a los hitos. El problema del bucle sin fin, se produce
cuando el robot vuelve a reobservar los hitos después de un largo recorrido, este problema
Proyecto Fin de Carrera Implementación del FKE para SLAM
21
es especialmente difícil. El problema de asociación se agrava en entornos donde los hitos no
son puntos simples y, es más, parecen diferentes desde distintos puntos de vista.
(Actualmente se está trabajando para resolver este problema)
No linealidad
El KKE-SLAM utiliza modelos linealizados a partir de los modelos de movimiento y
observación no lineales y así hereda algunas salvedades. La no linealidad puede ser un
problema importante en el FKE-SLAM y llevará a inevitable, y a veces dramática,
inconsistencia en las soluciones. Convergencia y consistencia sólo pueden ser garantizadas
en casos lineales.
2.5.3 Filtro Rao-Blackwellized
El algoritmo del FastSLAM, introducido por M. Montemerlo y otros [18], marca un
cambio conceptual fundamental en el diseño en el cálculo del SLAM con métodos
probabilísticos recursivos. Esfuerzos previos se centraban en mejorar la implementación del
FKE-SLAM, mientras mantenían la presunción inicial de la gaussiana lineal. FastSLAM, que
está basada en el muestreo recursivo de Montecarmelo, o filtro de partículas, fue el primero
en representar directamente el modelo de proceso no lineal y distribución no gaussiana de
la posición (FastSLAM linealiza el modelo de observación, pero esto es una aplicación
razonable para la relación del rango de medidas cuando la posición del robot es conocida).
Esta aproximación fue influenciada por los primeros experimentos de mapeado
probabilístico de K. Murphy [19] y S. Thrun [20].
La gran dimensión del problema estado-espacio del SLAM hace inviable el cálculo de la
aplicación directa del filtro de partículas. Sin embargo, es posible reducir el muestreo del
espacio mediante la aplicación del filtro de Rao-Blackwellization (R-B), a través del cual un
conjunto de estados es dividido de acuerdo a la regla del producto
)()|(),( 11221 xPxxPxxP = y si )|( 12 xxP puede ser representada analíticamente, sólo
)( 1xP necesitaría muestrearse )( 1)(
1 xPx i ≈ . El conjunto de distribución, no obstante, es
representado por un conjunto Ni
ii xxPx )}|(,{ )(12
)(1 y las estadísticas como la
marginal ∑≈N
i
íxxPN
P )|(1)x( )(122 puede ser obtenida con mayor exactitud de la que es
posible muestreando todo el conjunto de estados.
El conjunto de espacios del SLAM puede ser factorizado en una componente del robot y
otra condicional del mapa:
).,|(),|(),,|,( 0:0:0:0:0:00:0:0:0 xUZXPZXmPxUZmXP kkkkkkkk = (12)
Proyecto Fin de Carrera Implementación del FKE para SLAM
22
Aquí la distribución de probabilidad es sobre la trayectoria kX :0 más que sobre una
única posición kx porque, cuando se imponen las condiciones sobre la trayectoria, el mapa
de hitos comienza a ser independiente (Figura 4). Esto es una propiedad clave del
FastSLAM y una razón de su rapidez. El mapa está representado como un conjunto de
gaussianas independientes, con complejidad lineal, en vez de un mapa de covarianzas
conjuntas con complejidad cuadrática.
Figura 3
La estructura esencial del fastSLAM, entonces, es un estado Rao-Blackwellized donde la
trayectoria es representada por muestras ponderadas y el mapa esta calculado
analíticamente. De esta manera, el conjunto de la distribución, en el instante k , es
representado por el conjunto Nik
ik
ik
ik ZXmPXw )},|(,,{ :0
)(:0
)(:0
)( , donde el mapa asociado a
cada partícula esta compuesto de distribuciones gaussianas independientes
),|(),|( :0)(
:0:0)(
:0 kikj
M
jk
ik ZXmPZXmP ∏=
La estimación recursiva es llevada a cabo por el filtro de partículas para los estados de
la posición y el FKE para los estados del mapa.
Actualizar el mapa para la trayectoria de una partícula dada )(:0ikX es trivial. Cada hito
observado es procesado individualmente como una actualización de las medidas del FKE
respecto a una posición conocida. Hitos no observados no se modifican. Por otro lado la
propagación de las partículas de la posición es más complejo.
Tenemos que renunciar a un segundo plano en los filtros de partículas, salvo para decir
que la teoría se deriva de una forma recursiva de muestreo conocido como muestreo
secuencial importante (Sequential Important Sampling SIS), que muestrea desde un conjunto
de estados históricos pero "pliega'' el conjunto en una recursión a través de la regla del
producto.
),|(),|()|()|,,,( :01:0:001:00:010 TTTTTTT ZXxPZxxPZxPZxxxP −= LL
En cada instante k , las partículas son extraídas de la distribución propuesta
),|( :01:0 kkk ZXx −π , que aproxima la distribución ),|( :01:0 kkk ZXxP − , y los muestreos se
Proyecto Fin de Carrera Implementación del FKE para SLAM
23
ponderan con pesos para compensar cualquier discrepancia. El error de aproximación crece
con el tiempo (y el conjunto inherente del espacio de estados), incrementando la variación
de los pesos de los muestreos, degradando la aproximación estadística. Un paso de
“remuestreo” restablece la ponderación, pero causa la pérdida de la información histórica
de las partículas. Esto lleva a una propiedad fundamental: el SIS con “remuestreo” puede
producir una estadística razonable sólo para sistemas que olvidan su pasado
exponencialmente, es decir, sistemas cuyos procesos sean ruidosos de tal forma que el
estado en el instante k sea cada vez más independiente de los estados precedentes.
La forma general de un filtro de partícula R-B para el problema del SLAM es el
siguiente. Se asume que, en el instante 1−k el conjunto de estados es representado por Nik
ik
ik
ik ZXmPXw )},|(,,{ 1:0
)(1:0
)(1:0
)(1 −−−− .
• Para cada partícula, calcular una propuesta de distribución, en función de la
historia específica de partícula, y realizar un muestreo para la misma
),,|( :0)(
1:0)(
kkikk
ik uZXxx −≈ π
(13)
Este nuevo muestreo está (implícitamente) unido a la historia de la partícula
},{ )()(1:0
)(:0
ik
ik
ik xXX −
Δ
= • Ponderar las muestreos de acuerdo a la importancia de la función
),,|(),|(),|(
:0)(
1:0)(
)(1
)(1:0
)(:0)(
1)(
kkik
ik
ki
ki
kkikki
ki
k uZXxuXxPZXzPww
−
−−−=
π
(14)
El término del numerador está formado por dos términos que son el modelo de
observación y el modelo del movimiento, respectivamente. El primero es diferente
de la definición dada en la ecuación (2) porque R-B requiere calcular de forma
independiente el mapa.
dmZXmPmxzPZXzP kkkkkkk ),|(),|(),|( 1:01:01:0:0 −−− ∫= (15)
• Si es necesario, realizar “remuestreo”. Cuándo es el mejor momento para un
segundo muestreo, es un problema abierto. Algunas implementaciones
“remuestrean” en cada paso, otras después de un número fijo de pasos, y otras
cuando la variación del peso excede un umbral. El “remuestreo” se consigue por la
selección de partículas, con sustitución, desde el conjunto Ni
ikX }{ )(:0 , incluyendo sus
mapas asociados, con la probabilidad de selección proporcional a )(ikw . Las
partículas tienen dado un peso uniforme Nw ik /1)( = .
• Para cada partícula, realizar una actualización mediante el filtro de Kalman en los
hitos observados como una operación simple de mapeo con la posición del vehículo
conocida.
Proyecto Fin de Carrera Implementación del FKE para SLAM
24
Las dos versiones del FastSLAM (1.0 [21] y 2.0 [22]) en la literatura se diferencian sólo en
términos de cómo formular la distribución propuesta (Primer punto de la descripción del
modelo del FastSLAM), y en consecuencia, en la importancia de los pesos (Segundo punto).
Pero FastSLAM 2.0 es con diferencia la más eficiente solución.
Para FastSLAM 1.0, la distribución propuesta es el modelo de movimiento
),|( )(1
)(k
ikk
ik uxxPx −≈
(16)
Por tanto, de (14), los muestreos son ponderados de acuerdo el modelo de observación
marginal.
),|( 1:0)(
:0)(1
)(−−= k
ikk
ik
ik ZXzPww
(17)
Para FastSLAM 2.0, la distribución propuesta incluye la observación actual
),,|( :0)(
1:0)(
kkikk
ik uZXxPx −≈
(18)
donde
),|(),,|(1),,|( 11:0)(
1:0:0)(
1:0 kkkkk
ikkkkk
ikk uxxPZXxzP
CuZXxP −−−− =
y C es una constante normalizada. La importancia de los pesos de acuerdo a la
ecuación (14) es Cww ik
ik
)(1
)(−= . La ventaja de esta forma respecto a la primera es que la
distribución propuesta es óptima localmente. Esto significa, para cada partícula,
proporciona la menor diferencia posible en la importancia de los pesos )(ikw condicionado a
la información disponible )(1:0
ikX − , kZ :0 y kU :0 .
Estadísticamente, FastSLAM (tanto la versión 1.0 y como la 2.0) sufre degeneración
debido a su inestabilidad para olvidar el pasado. Descartando el mapa en la ecuación (15) se
introduce dependencia en la historia de la posición y la medida, y así, cuando se
“remuestrea” se reduce la historia, y la exactitud estadística se pierde. Sin embargo, los
resultados empíricos de fastSLAM 2.0 en entornos reales al aire libre muestran que el
algoritmo es capaz de generar un mapa exacto en la práctica.
Proyecto Fin de Carrera Implementación del FKE para SLAM
25
2.6. Implementación del SLAM
Los desarrollos prácticos del SLAM probabilístico se han incrementado en los últimos años,
cubriendo grandes áreas en entornos que cada vez requieren más desafíos. En el apartado
anterior se han dado los desarrollos teóricos de las dos implementaciones más importantes. A
continuación se menciona otra con notables aplicaciones.
El método “Explorar y regresar” desarrollado por P. M. Newman y otros [23], fue una
moderable implementación que confirmo la no divergencia de las propiedades del FKE-SLAM
para regresar al punto preciso marcado de salida. El experimento es notable porque su viaje de
regreso fue totalmente autónomo. El robot fue manualmente guiado durante la fase de
exploración, aunque sin el contacto visual del operador, quien se basó únicamente en el mapa
generado por el robot en tiempo real. Para el viaje de regreso, el robot trazó un camino y volvió
sin intervención humana.
J. E. Guivant y E. M. Nebot [24] fueron pioneros en desarrollar el SLAM en grandes espacios
al aire libre. Ellos abordan temas computacionales en tiempo real de operación, mientras tratan
con la alta velocidad de movimiento del robot, terreno irregular y una dinámica variable. Sus
resultados eran particularmente interesantes porque iban acompañados por un sistema RTK-
GPS (Real Time Kinematic), mostrando la veracidad práctica del algoritmo, que involucraba
varios bucles. La información obtenida del viaje a través del parque Victoria está disponible en
Internet y ha llegado a ser un punto de referencia para la comunidad de investigación sobre
SLAM.
Las aplicaciones del SLAM existen actualmente en una gran variedad de dominios. Entre
ellos los desarrollos en lugares cerrados, en espacios abiertos, en el aire y bajo el mar.
Varios investigadores en el campo del SLAM han escrito programas demostrando su
funcionamiento, implementados en MATLAB, C++ y Java, y están disponibles en Internet.
Proyecto Fin de Carrera Implementación del FKE para SLAM
26
2.7. Investigaciones actuales en el desarrollo del SLAM
En el desarrollo del SLAM, la gran mayoría del trabajo se ha centrado en mejorar la
eficiencia computacional mientras se aseguraba la consistencia y la exactitud de la estimación
para el mapa y la posición del robot. Sin embargo, ha habido también muchos investigadores en
cuestiones como la no linealidad, la asociación de la información, y la caracterización de los
puntos de referencia. Todos estos son importantes para el éxito de una implementación práctica
y robusta del SLAM.
En este apartado se muestra el estado actual del arte en las investigaciones en SLAM
centrándose en tres áreas claves: complejidad computacional, asociación de la información, y
representación del entorno.
2.7.1 Complejidad computacional
En su forma más simple el problema del SLAM aumenta cuadráticamente con el
número de puntos de referencia del mapa. Para la implementación en tiempo real, este
crecimiento es potencialmente una limitación substancial en el uso de métodos para SLAM.
Esta es la idea de la que se parte para desarrollar métodos que reduzcan la complejidad
computacional.
La formulación basada en el estado del problema del SLAM involucra la estimación de
un conjunto de estados, compuestos por la posición del robot y las localizaciones de los
hitos observados estacionariamente. La formulación de este problema tiene una estructura
particular, el modelo del proceso sólo afecta a los estados de la posición del vehículo y el
modelo de observación sólo hace referencia a un único par robot-hito. Una gran variedad
de técnicas han sido desarrolladas para explotar esta estructura especial en busca de la
limitación de la complejidad computacional del algoritmo del SLAM.
Las técnicas dirigidas a mejorar la eficiencia computacional pueden ser caracterizadas
como óptimas o conservadoras: los algoritmos óptimos se encaminan a reducir los cálculos
requeridos mientras siguen dando como resultado estimaciones y covarianzas iguales a las
de la formulación completa del algoritmo del SLAM. Los algoritmos conservadores dan
como resultado estimaciones que tienen mayores incertidumbres o covarianzas que el
resultado óptimo. Normalmente, en algoritmos conservadores se cumple que cuanto menor
es la exactitud más eficiente desde el punto de vista computacional es el algoritmo, y por
tanto, de gran valor en implementaciones reales. Algoritmos con incertidumbres o
covarianzas menores que aquellas de la solución óptima son calificadas de incoherentes y
son consideradas como soluciones inválidas para el problema del SLAM y cualquiera de
sus aproximaciones.
Proyecto Fin de Carrera Implementación del FKE para SLAM
27
La aproximación directa para reducir la complejidad computacional involucra sacar
provecho de la estructura del problema SLAM, reformulando las ecuaciones de
actualización de las observaciones y en el tiempo en el que se producen para limitar los
cálculos requeridos. El cálculo del tiempo de actualización puede ser limitado usando
métodos como el incremento de estados. El cálculo de la actualización de la observación
puede ser limitado usando una forma de partición de las ecuaciones de actualización.
Ambos pasos dan lugar a una estimación óptima en SLAM que reduce los cálculos. La
reformulación de la representación estándar del espacio de estados del SLAM en su forma
canónica permite emplear el método sparsification, es decir, permite la simplificación de la
matriz de información mediante la acción de hacer ceros para ser utilizada en cálculos más
reducidos. Los algoritmos resultantes son normalmente conservativos pero todavía podrían
producirse mejores aproximaciones con mucho menor esfuerzo computacional. Los
métodos de submapeo se basan en la idea de que un mapa puede ser “roto” en regiones con
sistemas de coordenadas locales y organizar dichas regiones de forma jerárquica. Las
actualizaciones pueden hacerse en un marco local con tiempos de actualización periódicos.
Las técnicas de submapeo generalmente proporcionan una estimación conservativa en el
marco global.
2.7.1.1 Estado incrementado
En el instante k , el conjunto del vector de estados del problema del SLAM TTT
kvk mxx ],[= comprende dos partes: la posición del robot vkx y el establecimiento
de las localizaciones de los puntos de referencia en el mapa m . El modelo del vehículo
propaga sólo los estados de las posiciones de acuerdo al conjunto de las entradas de
control ku mientras deja los estados del mapa inalterados
( ) ( )⎥⎦
⎤⎢⎣
⎡== −
− muxf
uxfx kvkvkkk
,, 1
1
(19)
En una implementación simplificada del filtro de Kalman extendido para SLAM, la
predicción de la covarianza es calculada de la forma: T
ukuTxkkxkk fUffPfP ∇∇+∇∇= −−− 1|11|
(20)
donde 1−∂
∂=∇
kx x
ff , k
u uff
∂∂
=∇ y kU es una covarianza que caracteriza la
incertidumbre en el vector de control. Esta operación tiene complejidad cúbica con el
número de hitos debido a la multiplicación de las matrices del Jacobiano xf∇ y la
matriz de covarianza 1|1 −− kkP . A pesar de esto, como sólo los estados de la posición están
Proyecto Fin de Carrera Implementación del FKE para SLAM
28
afectados por el modelo del robot, la predicción de la covarianza puede ser rescrita de
una forma que tenga complejidad lineal en el número de hitos:
⎥⎥⎦
⎤
⎢⎢⎣
⎡
∇∇∇∇+∇∇
=−mm
Tv
Tvm
vmvT
vkvT
vvvvkkk PfP
PffUffPfP
x
xuux1|
(21)
donde 1−
∂∂
=∇k
xv
vv x
ff , k
vv u
ffu ∂
∂=∇ y donde ⎥
⎦
⎤⎢⎣
⎡=−−
mmT
vm
vmvvkk PP
PPP 1|1
El proceso de añadir un nuevo punto de referencia al vector de estados tiene una
formulación similar. Un nuevo mapa de un hito es iniciado como función de la posición
del robot y una observación kz
( )kvknew zxgm ,= (22)
Los estados incrementados son entonces una función de solo un número reducido
de estados existentes
( )⎥⎥⎥
⎦
⎤
⎢⎢⎢
⎣
⎡=+
kvk
vk
k
zxgmx
x,
(23)
La idea general de incrementar el estado puede ser aplicada siempre que los nuevos
estados sean una función de un subconjunto de estados existentes
( )⎥⎥⎥
⎦
⎤
⎢⎢⎢
⎣
⎡
qxfxx
,2
2
1
(24)
⎥⎥⎥
⎦
⎤
⎢⎢⎢
⎣
⎡
∇∇+∇∇∇∇∇∇
Tqq
Txxx
Tx
Tx
T
Tx
fQffPfPfPffPPPfPPP
2222
2
2
222212
222212
121211
(25)
Comparando (19) y (21) con (24) y (25) se observa que el paso de predicción del
SLAM es un caso especial del estado incrementado con una nueva posición vkx y
donde la posición previa 1−vkx se deja de tener en cuenta por discriminación. De esta
forma, el paso de predicción del FKE y el proceso de adicción de nuevos hitos pueden
ser reducidos a cálculos que son lineales con el número de puntos de referencia. Las
predicciones realizadas son claramente óptimas.
2.7.1.2 Actualizaciones por partes
Una implementación simplificada del paso de actualización de la observación del
problema del SLAM, actualiza todos los estados del robot y del mapa cada vez que se
Proyecto Fin de Carrera Implementación del FKE para SLAM
29
realiza una medida. Para una actualización con el FKE, el esfuerzo computacional
aumenta cuadráticamente con el número de hitos situados en el mapa. Una serie de
métodos de actualizaciones por partes se han desarrollado para intentar reducir el
esfuerzo computacional. Las actualizaciones se limitan a una pequeña región local y
actualizan el mapa global a una menor frecuencia. Estos métodos de partición producen
estimaciones óptimas.
Hay dos tipos básicos de actualizaciones por partes:
- La primera trabaja en una zona local del mapa global y mantiene coordenadas de
referencias globales. Esta aproximación esta basada en el FKE comprimido y el
algoritmo de aplazamiento.
- El segundo genera una pequeña parte del mapa con sus propias coordenadas
locales. Esta es la aproximación del filtro del submapa local limitado (CLSF, Constrained
local submap filter) y del algoritmo de secuencia del mapa local.
Centrándose en esta última aproximación por su simplicidad y utilizando una alta
frecuencia de operaciones en un rango de coordenadas locales, permite grandes
covarianzas globales, y por tanto, es numéricamente más estable y menos influenciable
para linealizar errores.
El algoritmo del submapeo mantiene todo el tiempo dos estimaciones
independientes del SLAM
⎥⎦
⎤⎢⎣
⎡=
⎥⎦
⎤⎢⎣
⎡=
R
Rv
R
G
GF
G
mx
x
mx
x
(26)
donde Gx es un mapa compuesto por un conjunto de hitos referenciados en el
sistema global Gm , junto con la referencia global de la posición un sistema de
coordenadas de un submapa GFx , y donde Rx es el submapa local con la posición del
robot referenciado localmente Rvx y los hitos referenciados localmente Rm como se
muestran en las siguientes figuras.
Figura 4
Proyecto Fin de Carrera Implementación del FKE para SLAM
30
Debido a como están realizadas las observaciones, las actualizaciones del SLAM
convencional se realizan enteramente en el submapa y con sólo aquellos hitos incluidos
en el submapa local. Es posible obtener la posición estimada global del robot en
cualquier instante mediante la simple suma del vector de referencia de la posición local
y la estimación global del centro de coordenadas del submapa. Una estimación óptima
global se obtiene periódicamente registrando el submapa con el mapa global y
aplicando actualizaciones a las restricciones sobre cualquier rango común entre ambos
mapas. En este momento se crea un nuevo submapa y se continúa el proceso.
El método de los submapas tiene una serie de ventajas:
- El número de puntos de referencia que se debe actualizar cada vez está limitado a
sólo aquellos que están descritos en el rango de coordenadas del submapa. Así la tasa
de actualización completa, y la propagación de las estimaciones locales puede llevarse a
cabo como tarea de fondo en una menor tasa de actualización al mismo tiempo que
permite la observación de tipos de localización global.
- Hay menor incertidumbre en el rango de referencia local, así aproximaciones
debidas a la linealización son reducidas.
- El registro del mapa puede utilizar sistemas de puertas de validación por lotes,
mejorando la robustez de la asociación.
2.7.1.3 Sparsification
El FKE-SLAM convencional produce una estimación del estado kx) y una matriz de
covarianza kP , que describe implícitamente los dos primeros momentos centrales de
una densidad de probabilidad de una gaussiana en el verdadero estado kx . Una
representación alternativa para esta misma gaussiana es en forma canónica usando el
vector de información ky) y la matriz de información kY . Éstas están relacionadas con
los momentos a partir de los parámetros como: 1−= kk PY (27)
kkk xYy )) = (28)
La ventaja de la forma canónica para el SLAM es que para grandes mapas muchos
de los elementos fuera de la diagonal de la matriz de información normalizada están
muy próximos a cero. S. Thrun [25] [26] y otros, han desarrollado esta observación para
proponer un procedimiento de sparsification que permita a los elementos cercanos a cero
de la matriz de información aproximarlos a cero. Con la matriz de información ahora
hecha cero donde corresponda, muchos de los métodos de actualización eficiente para
Proyecto Fin de Carrera Implementación del FKE para SLAM
31
las estimaciones de las observaciones pueden obtenerse con sólo una pequeña pérdida
de exactitud en los mapas producidos. Aunque esta solución inicial fue posteriormente
mostrada como no consistente por R. Eustice [27], la idea de hacer ceros ha suscitado un
considerable interés en el problema del SLAM en su forma canónica, presentándose
numerosas soluciones consistentes basadas en este método.
La clave para hacer ceros en la forma canónica del problema del SLAM es observar
que el incremento del estado, es una operación para hacer ceros. Considerando el
término del incremento respecto a la forma y el momento en (24) y (25). Estos tienen un
término equivalente en la forma canónica
[ ][ ] ⎥
⎥⎥
⎦
⎤
⎢⎢⎢
⎣
⎡
∇−∇−∇−
−
−
2221
2221
2
1
)()(
2
xfxfQxfxfQfy
yTx
(29)
⎥⎥⎥
⎦
⎤
⎢⎢⎢
⎣
⎡
∇−∇−∇∇+
−−
−−
11
112212
1211
2
222
0
0
QfQQffQfPY
YY
x
Txx
Tx
T
(30)
donde por simplicidad se ha asumido que el ruido es aditivo de media cero
( ) ( ) qxfqxf += 22 , . Asumiendo que el subconjunto de estados 1x comprende la
mayoría de los estados del mapa entonces en (30) se hacen ceros y se tiene una
complejidad constante en el tiempo comparada con (25), que tiene complejidad lineal
con la dimensión de 1x .
Por tanto, en la forma canónica del problema del SLAM, una solución exacta
mediante la acción de hacer ceros puede obtenerse incrementando el estado con la
nueva posición estimada del robot a cada paso y conservando las posiciones pasadas
del robot
[ ]TTTv
Tvk
Tvkk mxxxx ,,,, 11 L−=
(31)
De esta forma, los elementos fuera de la diagonal de la matriz de información son
diferentes de cero sólo para las posiciones de los puntos de referencia que están
directamente relacionados a través de la información de las medidas (Figura 5.a). Las
actualizaciones de la observación son también sometidas a la acción de hacer ceros,
produciendo relaciones sólo entre los estados medidos.
Sin embargo, la marginalización, que es necesaria para eliminar los estados de
posiciones pasadas, introduce relaciones entre todos los elementos de estados
conectados a los estados eliminados. Descartar todos los estados pasados provoca una
concentración de la matriz de la información como se muestra en la Figura 5.c. Sin
embargo, es posible conservar una estimación mediante una razonable acción de hacer
ceros sin mantener la historia completa de la posición. Mediante una elección juiciosa
Proyecto Fin de Carrera Implementación del FKE para SLAM
32
de las posiciones fijadas para desacoplar las diferentes regiones del mapa, una gran
parte de las posiciones puede ser descartada sin introducir demasiada densidad como
se muestra en la Figura 5.b.
Figura 5
A pesar del atractivo de esta representación de la acción de hacer ceros, hay serias
advertencias a tener en cuenta sobre las implementaciones prácticas de la forma
canónica del SLAM. Para usos reales es necesario recuperar la media y la covarianza del
estado en cada paso. Esto es potencialmente muy caro. La estimación de la media se
necesita para llevar a cabo la linealización del proceso y los modelos de observación.
Esto puede recuperarse eficientemente utilizando el método del gradiente conjugado
(Es un gran método para matrices simétricas y definidas positivas. Ya que aprovecha
muy bien la estructura de la matriz y tiene muy buenas propiedades de estabilidad
numérica. El método del gradiente conjugado es un método iterativo que a partir de un
iterante inicial va calculando sucesivos iterantes que se van acercando a la solución
exacta del sistema lineal. El iterante 1+k será la solución, si el diferencia entre él y el
iterante k es menor que un cierto número prefijado.). La media y la covarianza son
necesarias para calcular las condiciones en la asociación de la información. Mientras
soluciones eficientes han sido creadas a través de condiciones simples, los métodos
robustos de validación de condiciones por lotes descritos en la parte de asociación de la
información, involucran la recuperación de toda la matriz de covarianza, cuya
complejidad es cúbica con el número de puntos de referencia.
2.7.1.4 Submapas globales
Los métodos basados en submapas son otra forma de redirigir los problemas del
crecimiento cuadrático de los cálculos con respecto al número de hitos durante la
actualización de las medidas. Los métodos basados en submapas se engloban en dos
variedades fundamentales: con referencia global y con referencia local, como se muestra
en la siguiente figura.
Proyecto Fin de Carrera Implementación del FKE para SLAM
33
Figura 6
La línea común de ambos tipos es que un submapa define un sistema local de
coordenadas y los hitos cercanos son estimados en dichas coordenadas. Las
estimaciones del submapa local son usando el algoritmo óptimo del SLAM utilizando
sólo las referencias locales de los hitos. Las estructuras de los submapas resultantes son
entonces ordenadas de forma jerárquica según la eficiencia computacional pero también
por la falta de optimación.
Los métodos de submapas globales estiman las posiciones globales de los sistemas
de coordenadas relativas de los submapas en un sistema de coordenadas base común.
Ésta es la aproximación adoptada en la representación relativa de los hitos (RLR,
Relative Landmark Representation) [28], SLAM jerárquico [29] y métodos de SLAM en
tiempo constante (CTS, Constant Time SLAM) [30]. Estas aproximaciones reducen los
cálculos desde una dependencia cuadrática con el número de hitos a una dependencia
lineal o constante en el tiempo, manteniendo una estimación conservativa del mapa
global. Sin embargo como los rangos de los submapas están referidos localmente a un
sistema de coordenadas general, los submapas globales no alivian las cuestiones de
linealización derivadas de las grandes incertidumbres que plantean.
2.7.1.5 Submapas relativos
Los métodos basados en submapas relativos difieren de los submapas globales en
que no hay un sistema de coordenadas común. La localización de cualquier submapa es
recordado únicamente por sus submapas vecinos, y estos están conectados en una red
gráfica como se muestra en la siguiente figura.
Proyecto Fin de Carrera Implementación del FKE para SLAM
34
Figura 7
Las estimaciones pueden obtenerse sumando vectores a lo largo del camino trazado
en la red. Absteniéndose cualquier forma a nivel global de información conjunta, los
submapas relativos abordan tanto cuestiones de linealidad como computacionales.
La idea original de los submapas relativos fue introducida por K. S. Chong y L.
Kleeman [31]. Pero fueron ampliamente desarrollados por S. B. Williams [32] en la forma
del filtro del submapa relativo limitado (CRSF, Constrined Realtive Submap Filter). Sin
embargo, este último método no exponía un nivel global de convergencia sin
penalización del desacople en la estructura del submapa. La estructura Atlas y la red
conjunta de caracterización de mapas corregían estos problemas considerando que la
conservación de la convergencia global puede obtenerse usando algoritmos de
covarianza cruzados para la estimación de las conexiones. Estos algoritmos dan lugar a
una red de submapas del SLAM óptimo conectados mediante enlaces conservativos.
La estructura de un submapa relativo tiene una serie de ventajas. En particular,
produce mapas óptimos localmente con complejidad computacional independiente del
tamaño del mapa completo. Además considerando actualizaciones locales, es
sumamente estable, permitiendo asociaciones entre diferentes sistemas, y minimizando
problemas que pueden presentarse de la linealización en un sistema global.
2.7.2 Asociación de la información
2.7.2.1 Validación por lotes
Casi todas las implementaciones involucran la asociación de la información usando
sólo métodos estadísticos de validación a través de condiciones, método heredado de la
literatura objetivo de seguimiento para eliminar las asociaciones no deseadas. Pronto
las implementaciones del SLAM consideraron las asociaciones de las mediciones con
los puntos de referencia de forma individual probando si un hito observado estaba
Proyecto Fin de Carrera Implementación del FKE para SLAM
35
cerca de una posición estimada. Los sistemas de validación a través de condiciones de
forma individual son irrealizables si la posición del robot es incierta y falla en la
mayoría, incluso en entornos poco poblados y bien estructurados.
Un avance importante fue el concepto de validación por lotes utilizando
condiciones, donde múltiples asociaciones son consideradas simultáneamente. La
compatibilidad de asociaciones mutuas explota la relación geométrica entre los hitos.
Las dos formas desarrolladas para llevar a cabo este sistema de asociación son el
método del conjunto de compatibilidad camino y destino, es una búsqueda en forma de
árbol (JCBB, Joint Compatibility branch and bound) [33], y la combinación limitada de la
asociación de información, que es un gráfico de búsqueda como puede verse en la
Figura 8 (CCDA, Combined constraint data association) [34]. El último método, y una
variante aleatoria del primero, es capaz de llevar a cabo una asociación fiable sin
ningún conocimiento alguno de la posición del robot.
La validación por lotes por si misma es suficiente para conseguir una asociación de
la información fiable: si la condición es suficientemente restrictiva, los errores de
asociación tienen un efecto insignificante, y si una asociación errónea se realiza con un
hito incorrecto éste está físicamente muy cerca del correcto, entonces la inconsistencia
es menor. Esto no siempre es válido, especialmente en grandes y complejos entornos,
entonces son necesarios mecanismos más exhaustivos de asociación de la información,
como por ejemplo sistemas multihipótesis de seguimiento.
Figura 8
2.7.2.2 Apariencia de los puntos de referencia
La imposición de condiciones en modelos geométricos no es solo la única salida
para una asociación de la información fiable. Muchas modalidades de sensores como la
Proyecto Fin de Carrera Implementación del FKE para SLAM
36
visión, proporcionan una amplia información sobre la forma, el color, y la textura que
pueden ser usadas para encontrar una correspondencia entre dos informaciones dadas.
Para el SLAM las características de apariencia son muy útiles para predecir una
posible asociación, así como un bucle sin fin, o para mejorar un sistema de condiciones
convencional proporcionando información adicional para poder discriminar.
Históricamente, las características de apariencia y similitud métrica de las imágenes
se utilizaban para catalogar bases de datos de imágenes y para reconocer lugares en
mapas topológicos. Más recientemente, la apariencia de las medidas se ha aplicado para
detectar bucles en SLAM. El trabajo en el campo visual de la apariencia de los hitos
para la detección de bucles desarrollado por P. Newman [35] introduce dos innovaciones
importantes. Se trabaja más con una secuencia de imágenes que sobre una única
imagen, y un valor técnico propio es utilizado para quitar similitudes de las formas
comunes. Esta aproximación reduce considerablemente la producción de falsos
positivos considerando únicamente las coincidencias que son interesantes o no
comunes.
2.7.2.3 Multihipótesis de asociación de la información
Este método es esencial para conseguir un objetivo a través de seguimiento en
entorno abarrotados. Resuelve las ambigüedades de asociación generando un camino
separado estimado por cada hipótesis de asociación, creando cada vez una rama dentro
de un árbol de decisión. El número de caminos está normalmente limitado por los
recursos computacionales disponibles y los caminos con menor probabilidad son
reducidos por las hipótesis del árbol.
Las multihipótesis de rastreo son también importantes para una implementación
robusta del SLAM, particularmente en extensos y complejos entornos. Por ejemplo en el
caso de un bucle cerrado, un robot debería mantener hipótesis separadas en el caso de
sospechar un bucle y también una hipótesis sin bucle para casos donde el entorno
percibido tenga una estructura similar. Mientras los métodos multihipótesis de rastreo
han sido aplicados a problemas de mapeo, estos acaban de utilizarse en el contexto del
SLAM. Un obstáculo mayor es el elevado nivel computacional de mantener diferentes
mapas estimados para cada una de las hipótesis. Se pueden conseguir soluciones
factibles usando sparsification o métodos de submapeo. El algoritmo del FastSLAM está
intrínsecamente unido a la solución de multihipótesis, ya que cada partícula da su
propio mapa estimado. Un atributo importante del algoritmo del FastSLAM es su
habilidad para establecer para cada partícula la asociación de la información.
Proyecto Fin de Carrera Implementación del FKE para SLAM
37
2.7.3 Representación del entorno
Los primeros trabajos en SLAM asumieron que el entorno podía ser modelado
razonablemente como un conjunto discreto de puntos de referencia descritos mediante
primitivas geométricas simples como puntos, líneas o círculos. En entornos más complejos y
desestructurados está hipótesis no es válida.
2.7.3.1 Observabilidad parcial y mapeo retardado
Modelar el entorno depende de la complejidad del mismo y de las limitaciones del
modelo sensorial para percibirlo. Dos ejemplos comunes son el sonar y la visión. Los
sensores sonar producen un rango de medidas con gran exactitud pero debido a los
problemas para captar las respuestas producen una medida de la orientación inválida.
En cambio las medidas realizadas por una sola cámara, proporcionan información de la
orientación sin buena exactitud en las medidas.
Desarrollar el SLAM sólo con sensores de medida y sólo con sensores de
orientación demuestra que una única medida es insuficiente para conseguir la
localización de un punto de referencia, o mejor dicho, debe ser observada desde
distintos puntos de vista como se observa en la Figura 9.
Figura 9
Más precisamente, una única medida genera una distribución no gaussiana de la
localización del hito, y se necesitan múltiples medidas para obtener una estimación.
Distribuciones generalizadas, como una combinación de modelos, permiten de forma
inmediata no retrasar el mapeo del punto de referencia. Una forma de obtener una
estimación gaussiana del hito es demorar la inialización y, en cambio, acumular
información de las mediciones en bruto. Para permitir posteriormente una unión
consistente, es necesario guardar la posición del robot para cada medida. Así el estado
del SLAM es incrementado con las estimaciones de las posiciones almacenadas
[ ]TTTnvk
Tvk
Tvkk mxxxx ,,,, 1 −−= L (32)
Proyecto Fin de Carrera Implementación del FKE para SLAM
38
y las medidas correspondientes son almacenadas en una lista auxiliar },,{ nkk zz −L .
Cuando se ha conseguido información suficiente sobre un período n , se inicializa un
punto de referencia mediante una actualización por lotes. Las posiciones almacenadas
que no tienen ninguna otra medida asociada se eliminan del estado.
La unión retardada va más allá una observabilidad parcial. Es un concepto general
para incrementar la robustez acumulando información y permitiendo demorar la toma
de decisión, dando un conjunto de información acumulada, se puede obtener una
estimación mejorada mediante una actualización por lotes, así como un bloque de
adaptación o una iteración de pulido, que reduce dramáticamente la linealización de
errores. También facilita la validación por lotes utilizando condiciones y, por tanto,
ayuda a conseguir una asociación de la información fiable.
2.7.3.2 Hitos no geométricos
Mientras el método del FKE para SLAM se aplica normalmente a hitos geométricos,
la simple asociación de un objeto arbitrario a un sistema de coordenadas permite a los
mismos métodos ser aplicados a descripciones más generales de los hitos. Una
contribución reciente de J. Nieto [36] muestra los hitos como formas arbitrarias que
pueden ser tratadas usando el FKE para reconocer la posición del mismo
separadamente de la estimación de los parámetros de la forma.
Un hito está descrito por un modelo de la forma, que tiene asociado un sistema de
coordenadas definiendo el origen del hito. Este modelo es auxiliar al proceso del SLAM
y puede tener cualquier representación que permita la alineación de la información (por
ejemplo una cuadrícula). Cuando el robot observa el hito, el modelo de la forma está
alineado con los datos de medición. Asumiendo que esta alineación es
aproximadamente gaussiana, el centro estimado del sistema de coordenadas del robot
es una observación fiable para la actualización del FKE-SLAM, donde el mapa está
compuesto por las posiciones de los sistemas de coordenadas de los hitos.
2.7.3.3 SLAM en 3D
Implementar SLAM en tres dimensiones, es en principio, una extensión directa del
caso para dos dimensiones. Sin embargo, involucra una importante cantidad de
complejidad añadida debido a un modelo de movimiento del robot más general y
también un incremento de información sensorial y características de modelaje más
complejas.
Proyecto Fin de Carrera Implementación del FKE para SLAM
39
Hay tres formas de implementar SLAM en 3D. La primera es una implementación
en 2D con habilidades adicionales para construir el mapa en una tercera dimensión, por
ejemplo un láser horizontal con otro secundario ortogonal al primero captando
secciones verticales. Esta aproximación es apropiada cuando el movimiento del robot es
en un único plano. La segunda forma es una extensión directa del SLAM en 2D para
tres dimensiones, con la extracción de hitos discretos y un conjunto de estimación del
mapa y de la posición del vehículo. Esta forma ha sido desarrollada por A. J. Davison [37] utilizando visión monocular como sistema sensorial, y permite el movimiento del
robot en sus seis grados de libertad. La tercera forma involucra una formulación
completamente diferente de la formulación del SLAM, donde el conjunto de estados
está formado por todas las posiciones pasadas del robot. En cada posición el robot
obtiene un escaneo del entorno en tres dimensiones, y las posiciones estimadas se
alinean mediante la correlación de los escaneo.
2.7.3.4 SLAM orientado a trayectoria
La formulación estándar para SLAM define el estado estimado de la posición como
la posición del robot y una lista de hitos observados
[ ]TTTvkk mxx ,= (33)
Una formulación alternativa del problema del SLAM que ha ganado popularidad
últimamente es estimar la trayectoria del robot como
[ ]Tv
Tv
Tvk xxxx
kk 11,,, L
−= (34)
Esta formulación es particularmente válida para entornos donde no es fácil
discernir un número discreto de hitos y la alineación directa de la información dada por
el sistema sensorial es más simple o más fiable. El mapa ya no forma parte del estado
que debe ser estimado sino que forma un conjunto de datos auxiliares. Por tanto, esta
formulación no tiene un mapa explícito, sin embargo cada posición estimada tiene
asociado un escaneo, de tal forma que alineando todos éstos se forme un mapa global.
El algoritmo del FastSLAM puede ser considerado un ejemplo de estimación de la
trayectoria, cada partícula define su particular hipótesis de la trayectoria. Varias
modificaciones recientes del método del FastSLAM usan un híbrido basado en las
posiciones y la alineación de los escaneo en vez de un mapa basado en hitos. Otra
variación del SLAM basado en la trayectoria ha desarrollado mapas topológicos, donde
las posiciones están conectadas en una red gráfica en vez de como un conjunto en un
vector de estado. Esta red se conoce como estimación de la posición consistente (CPE,
Consistent pose estimation), es una propuesta alternativa al SLAM estado-espacio y es
Proyecto Fin de Carrera Implementación del FKE para SLAM
40
capaz de reproducir mapas a gran escala. La ventaja de reducir la información en la
formulación del SLAM utilizando sparsification ha provocado un tercer tipo de SLAM
basado en trayectoria, con una estimación que ha sido sometida a sparsification de (34).
Mientras el SLAM basado en la trayectoria tiene muchas características positivas,
también tiene algunos inconvenientes. El más importante es que en ocasiones es
necesario guardar la información de la misma forma que el mapa tradicional del SLAM
para limitar los costes de almacenamiento.
2.7.3.5 Información auxiliar indirecta
Los métodos basados en trayectoria permiten presentar información espacial
localizada. Cada escaneo del mapa puede tener asociado cierta información auxiliar
como la iluminación, la humedad, la temperatura, las características del terreno, etc. De
tal forma que esta información pueda ser utilizada para ayudar en el mapeo, en la
asociación de la información o para otros fines como el establecimiento de un camino o
para la recopilación de datos.
Este concepto de información auxiliar indirecta es más difícil de incorporar para la
formulación del SLAM tradicional. El estado está compuesto por un número discreto de
localizaciones de los hitos de tal forma que está mal adaptado para la tarea de
representar una gran cantidad de información espacial. J. Nieto [38] ha diseñado un
método llamado DenseSLAM para permitir parte de esta información indirecta.
Conforme el robot se mueve a través del entorno, la información auxiliar se almacena
en una estructura de datos adecuada, como una malla de ocupación, y la región
representada en cada celda esta determinada por un conjunto de hitos locales del mapa
global. Mientras el mapa evoluciona, y los hitos se mueven, la posición de la región de
la malla se desplaza y retrocede como corresponde. El resultado es una manera
consistente de mantener una densa cantidad de información asociada a una posición
espacial utilizando las estimaciones de los hitos.
2.7.3.6 Entornos dinámicos
Los entornos reales no son estáticos. Contienen numerosos elementos en
movimiento, como personas, y estructuras temporales que parecen estáticas durante un
tiempo pero luego se mueven, como por ejemplo las sillas o los coches aparcados.
Pueden ser detectados o ignorados, pueden ser tratados como hitos móviles, pero no se
deben añadir objetos móviles al mapa y entonces se asume que son estacionarios.
Proyecto Fin de Carrera Implementación del FKE para SLAM
41
La solución convencional del SLAM es redundante. Los hitos pueden eliminarse del
mapa sin perder consistencia, y a veces es posible eliminar una gran cantidad de ellos
con una baja tasa en el cambio de la convergencia. Esta propiedad se ha explotado para
mantener un mapa actualizado eliminando hitos que se han quedado obsoletos debidos
a los cambios del entorno. Para manejar objetos móviles de forma explícita D. Hähnel[39]
desarrollo una rutina de identificación auxiliar y con ella eliminaba la información
dinámica de un escaneo antes de enviarla al algoritmo del SLAM. En cambio, C. C.
Wang [40] añadió objetos móviles a sus estados estimados y proporcionó modelos para
tratar ambos casos, objetivos estacionarios y objetivos dinámicos. Simultáneamente la
estimación de objetivos móviles y estacionarios es muy costosa debido a la adición del
modelo predictivo. Por esta razón, la implementación de la solución involucra primero
una actualización estacionaria del SLAM más un seguimiento de objetivos móviles.
Top Related