… y con Bayes hemos topado!


Al final de la entrada anterior sobre localización comentamos que detrás del proceso explicado con el ejemplo del pasillo y las puertas, se encontraba el llamado Filtro Bayesiano. En esta entrada intentaremos explicar por encima en qué consiste y cómo hemos aplicado dicho filtro para localizar a nuestro robot en su mundo.

El Filtro Bayesiano es un algoritmo probabilístico recursivo que permite estimar una variable dada en función de otras. Es decir, tenemos una variable que no se puede medir directamente (la posición del robot), pero que sí se puede inferir teniendo la información de otras variables (mediciones de sensores, movimientos ejecutados y el mapa del entorno). Este algoritmo se puede utilizar para muchísimas cosas, entre ellas, para estimar la posición de un robot. Lo que el Filtro Bayesiano nos dará es una forma de calcular p(x | z, u, m), que es justo lo que necesitamos en el problema de la localización. Antes de entrar en harina quisiéramos resaltar lo potente que es este algoritmo a pesar de su sencillez.

La idea del algoritmo es que podemos estimar la posición en el instante t, sabiendo la posición del instante t-1, el movimiento ejecutado en el instante t y la medición del sensor del mismo instante. Para ello, el algoritmo consta de dos pasos: el paso de la predicción y el paso de la corrección. En el primer paso, se actualiza la creencia del instante anterior bel(x_{t-1}) utilizando la información del movimiento ejecutado u_t. Esta información viene dada por el modelo de movimiento que se discutió en la entrada Modelando la incertidumbre descrito por la función p(x_t | u_t, x_{t-1}). La operación de actualización que se lleva a cabo en el paso de predicción no es más que una integral que tiene este aspecto:

\bar{bel}(x_t) = \int p(x_t | u_t, x_{t-1}) bel(x_{t-1}) dx_{t-1}

Para que la integral asuste menos, pensad que en un espacio discreto dónde la posición sólo puede tomar unos valores dados, la integral se convierte en una simple suma. Aquí, para calcular la predicción \bar{bel}(x_t), es decir, la probabilidad de estar en la posición en el instante t, estamos sumando (integrando) el modelo de movimiento para todas las posiciones posibles en el instante anterior (t-1). Vamos a ilustrar esto con un ejemplo sencillo.

Como siempre, vayamos a nuestro mundo unidimensional, que ahora, además es discreto. Tenemos cinco posiciones posibles x = \{1, 2, 3, 4, 5\}. Y nuestro robot sólo puede ejecutar tres movimientos: u = {adelante, atrás, quieto}. No nos olvidemos que tenemos cierta incertidumbre en nuestro movimiento. Digamos que si estamos en la casilla y el robot ejecuta el movimiento adelante, la probabilidad de estar en n+1 es 0.8, la de permanecer en n es 0.1 y la de estar en n+2 es 0.1. Además, supongamos que la creencia en t-1 era \{0.2, 0.5, 0.1, 0.1, 0.1\}. Esto indica que lo más probable es que el robot se encontrara en x = 2 en el instante anterior. ¡Ah! Para que esto sea más divertido, nuestro mundo unidimensional es un toroide, es decir, si en la casilla 5 el robot ejecuta el movimiento adelante su nueva posición será la casilla 1. Este mundo, con las creencias y todo, queda ilustrado en la Figura 1.

Figura 1

Imaginemos que nuestro robot va hacia adelante. Según el paso de predicción, ¿cuál será la distribución de la creencia en el instante t? Vamos a calcularlo paso a paso para la casilla 3. Habiéndose movido hacia adelante, para poder estar ahora en la casilla 3 sólo caben tres posibilidades, según el modelo de movimiento que hemos descrito:

  1. El robot estaba en la casilla 2 en el instante anterior: por lo tanto bel(x_{t-1} = 2) = 0.5. Desde allí ha dado un paso hacia adelante y ahora está en la casilla 3. Según lo dicho anteriormente, esto tiene una probabilidad de 0.8. Por lo tanto el producto bel(x_{t-1} = 2) p(x_t = 3 | u_t = adelante, x_{t-1} = 2) es simplemente 0.5 x 0.8 = 0.4. Fijáos que la segunda parte del producto sólo se refiere a la probabilidad de encontrarse en la casilla 3, habiendo estado en el instante anterior en la casilla 2 y habiéndose movido hacia adelante.
  2. El robot estaba en la casilla 1 en el instante anterior, por lo tanto bel(x_{t-1} =1) = 0.2. Según el modelo de movimiento un salto de dos casillas tiene una probabilidad de 0.1. En total 0.2 \times 0.1 = 0.02
  3. Por último, cabía la posibilidad de estar en la casilla 3 en el instante anterior y no haberse movido a pesar de ejecutar un movimiento. Por lo que 0.1 \times 0.1 = 0.01

El paso de predicción indicaba que teníamos que sumar todas estas posibilidades (recordad la suma/integral): 0.4 + 0.02 + 0.01 = 0.43. Así pues, la probabilidad o creencia de estar en la casilla 3 en el instante actual después de habernos movido hacia adelante es 0.43. Estos cálculos simples que hemos hecho hay que repetirlos para cada una de las casillas. El resultado se puede ver en la Figura 2:

Figura 2

Se puede apreciar claramente que en virtud del movimiento ejecutado, lo más probable es que el robot se encuentre en la casilla 3. Sin embargo, en el instante anterior la certidumbre era de 0.5 contra el 0.43 de ahora. Esto ya lo habíamos visto en la entrada anterior. Su significado es profundo: en un sistema robótico dónde la medición del movimiento tiene incertidumbre (por muy pequeña que sea), aunque se sepa la posición inicial con total certidumbre, después de un tiempo suficientemente largo la posición del robot será totalmente desconocida. Es decir, todas las casillas tenderán al mismo número  sin remedio alguno (en nuestro caso 1/5). Necesitamos algo más que la predicción para poder localizarnos de forma fiable.

Es aquí donde entra en juego el segundo paso del algoritmo del Filtro Bayesiano: el paso de corrección. En este paso lo único que se hace es multiplicar el modelo de medición por la predicción hecha en el paso anterior para calcular la creencia final:

bel(x_t) = \eta p(z_t | x_t, m) \bar{bel}(x_t)

El término \eta no es más que un normalizador, para que las creencias de todas las casillas sumen a uno. ¿Nos atrevemos con otro ejemplillo? ¡Pues claro! En nuestro mundo unidimensional de 5 casillas hay dos puertas: uno en la casilla 3 y el otro en la casilla 5. Como no, nuestro robot está equipado con un sensor que detecta puertas. El modelo de medición ha de indicarnos cual es la probabilidad de detectar una puerta en cualquier posición, así como la probabilidad de no detectar una puerta en cualquier posición. Digamos que en las casillas donde hay puertas, la probabilidad de detectarlas es de 0.9. En las casillas donde no hay puertas, tenemos una probabilidad residual de 0.1. Por lo tanto, nuestro sensor es bastante fiable.

Seguiendo con el ejemplo anterior, en donde nuestro robot se había movido adelante dado un estado inicial del mundo (Figura 1), imaginemos que el sensor ha detectado una puerta. ¿Cómo se ejecuta el paso de corrección con esta nueva información? Muy sencillo. Hagamos el cálculo de nuevo para la casilla 3: la probabilidad de haber detectado una puerta en la casilla 3 era de 0.9, ya que en esa casilla existe una puerta. Por lo tanto:

\hat{bel}(x_t = 3) = p(z_t = puerta | x_t = 3, m) \bar{bel}(x_t = 3) = 0.9 x 0.43 = 0.387

Por ahora no hemos introducido el normalizador, es por ello que escribimos \hat{bel}(x_t). Hagamos los mismos cálculos para todas las casillas restantes:

  1. \hat{bel}(x_t = 1) = 0.1 x 0.11 = 0.011
  2. \hat{bel}(x_t = 2) = 0.1 x 0.22 = 0.022
  3. \hat{bel}(x_t = 3) = 0.9 x 0.43 = 0.387
  4. \hat{bel}(x_t = 4) = 0.1 x 0.14 = 0.014
  5. \hat{bel}(x_t = 5) = 0.9 x 0.1 = 0.09

El normalizador \eta no es más que la inversa de la suma de todas las creencias no normalizadas. Por lo tanto, después de multiplicar el normalizador a las creencias anteriores, obtenemos la creencia final del robot de su posición: \{0.021, 0.042, 0.738, 0.0267, 0.1717\}

¿Qué es lo que vemos? El robot está bastante seguro de estar en la casilla 3, que es su posición real. Vemos que la certidumbre del robot ha subido del 0.43 al 0.738 tal y como esperábamos. El paso de la corrección hace que la seguridad del robot aumente considerablemente, mostrando la importancia de tener buenas observaciones y mediciones del entorno.

Lo que acabamos de explicar en las últimas dos entradas es algo impresionante. Por muy simple que parezca, esta es la base del método de localización que usa el coche autónomo de Google. Lo que cambia en esencia es la forma de percibir y medir el mundo. El Google Car utiliza láseres de 3 dimensiones que le permiten construir modelos tridimensionales de su entorno. Los modelos de medición que utiliza son muy complejos y costosos de poner en marcha (por no hablar del precio de los sensores). Además, el mundo en el que se mueve poco tiene que ver con nuestro ejemplo unidimensional, pero queremos resaltar que la idea básica de la localización está en el Filtro Bayesiano que acabamos de ver. Ni más ni menos :O

Nos seguimos leyendo…

Anuncios

9 Respuestas a “… y con Bayes hemos topado!

  1. Hola!!! Le agradezco por la información que proporciona, he estado leyendo algunas de sus entradas y la verdad me han resultado muy útiles, Felicidades!!!, nada más tengo una duda con respecto a la manera en que calculó el normalizador para obtener la creencia final, no comprendo esa parte, le agradecería mucho si me lo pudiera explicar.
    Saludos

  2. Muy buena manera de explicarlo! felicidades!

  3. La creencia cm se halla? es arbitraria?

    • ¿A qué te refieres con la “creencia cm”? Lo siento, pero no he entendido tu pregunta.

      • los valores de la figura 1 en cada casilla.. si se ponen al azar siempre que la suma sea 1 o es con alguna formula.. es que es la primera vez que veo esto y estoy un poco perdida

        • OK! Esas creencias en concreto las he puesto al azar. En un algoritmo recursivo como este, en el que dependes del estado anterior, siempre tienes el problema de definir los valores en el estado inicial. En ese estado, no se tiene ninguna información, pero para que el algoritmo funcione, necesitas asignar algunos valores. Normalmente se suelen barajar dos alternativas: 1) inicializar todos las casillas con el mismo valor (1 dividido por el número de casillas) 2) pedir a un usuario externo que nos diga dónde se encuentra el robot en el instante 0, para inicializar las casillas contiguas con valores más altos. La estrategia 1 implica conocimiento 0 del entorno, por lo que asigna igual probabilidad a todas las casillas. Aún y todo, se ha demostrado que después de unas iteraciones el algoritmo converge a la posición real del robot. La estrategia 2 facilita una mejor localización desde el principio, pero cuenta con el inconveniente de tener que saber la posición inicial.

          Espero haberlo explicado bien 😉

        • It’s great to read something that’s both enjoyable and provides pragmatisdc solutions.

  4. mira celina ,que interesante.luis

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s