¿Dónde estoy?


Uno de los problemas fundamentales de la navegación autónoma es la localización, es decir, que el robot sepa en cada momento dónde está. En otras palabras, nos interesa saber la posición (x, y, \theta) del robot respecto a un sistema de coordenadas fijo al que llamamos coordenadas del mundo. Aquí, la clave es que la posición es algo que no se puede medir directamente. En su defecto, tenemos que utilizar la información que nos dan los sensores para estimar cual es la posición del robot.

Tal y como vimos en la entrada anterior, la información de los sensores viene con incertidumbre. Pero no hay problemas, por qué en aquella entrada ya hablamos de cómo modelar dicha incertidumbre. También hablamos de que teníamos dos modelos diferentes: uno para el movimiento y el otro para la medición. Pues bien, combinando ambos modelos con un mapa del entorno del robot, podremos resolver el problema de la localización.

Antes de nada, hablemos un poco sobre lo que es un mapa del entorno. Hay miles de formas de representar un entorno: mapas métricos, mapas topológicos, mapas de características… nada de eso debe preocuparnos ahora. Lo que tenemos que tener en cuenta es que para que un robot sepa dónde está, necesita saber el mapa del entorno. Cuando nosotros nos vamos a una ciudad desconocida, casi lo primero que hacemos es agenciarnos un plano de la ciudad y utilizarlo para saber dónde estamos. Bien, pues un robot también necesita su plano. Ese plano, como quiera que sea, lo conoceremos como m.

Pasando a términos un poco más técnicos, el problema de la localización consiste en determinar la función p(x_t | z_{0:t}, u_{0:t}, m). Tenemos que buscar la distribución de probabilidades de la posición (x_t), en función de las mediciones que hemos obtenido desde el instante 0 hasta ahora (z_{0:t}), los comandos de movimiento que hemos ejecutado (u_{0:t}) y el mapa del entorno (m).

En vez de enredarnos con términos técnicos y distribuciones de probabilidad, vamos a explicar la solución a este problema con un ejemplo muy intuitivo (Figura 1). El ejemplo lo hemos sacado del fantástico libro “Probabilistic robotics”.

Figura 1

Vayámonos a un mundo unidimensional en el que hay tres puertas. Nuestro robot solo puede ir hacia delante o hacia atrás y tiene equipado un sensor que es capaz de detectar puertas. El sensor en cuestión, con su incertidumbre, nos dirá si estamos frente a una puerta o no. Simple, ¿verdad?

Cuando nuestro robot se despierta no tiene ni idea de dónde está (Figura 1). Es el instante t = 0, y como el robot no tiene ninguna información previa de su estado, la probabilidad de que esté en cualquier posición es la misma. Por ello, la gráfica negra que está debajo de la imagen muestra el mismo valor de bel(x) para todas las x posibles. Aquí utilizamos el término bel(x) (del inglés belief = creencia), por qué esta distribución de probabilidades se infiere de otra información. No tiene mayor importancia. Lo importante es que en este punto el robot no tiene ni idea de dónde está.

Figura 2

Sin embargo, en ese instante le llega la primera medición del sensor. Esta medición se ve en la Figura 2 en la gráfica roja de p(z|x), que no es más que la probabilidad de haber visto una puerta en función de la posición. Es decir, el sensor ha visto una puerta. Evidentemente, la probabilidad es más alta en aquellas posiciones en las que está la puerta. Utilizando esta información, el robot actualiza su creencia (gráfica negra de la Figura 2). Por ahora, actualizar significa realizar una operación entre la creencia del paso anterior (Figura 1), y la información de la última medición. La naturaleza de dicha operación la explicaremos en la siguiente entrada. Por lo tanto, volviendo al ejemplo, en el momento descrito en la Figura 2, el robot sabe con gran certeza que está delante de una puerta, pero no es capaz de decir delante de cual de las tres puertas está. Es por ello que bel(x) muestra tres picos iguales en aquellas posiciones en las que se encuentran las puertas.

Figura 3

Así las cosas, en la Figura 3 el robot decide dar un paso adelante. Sus encoders registran este movimiento y el robot actualiza su creencia de la posición. Como se puede ver, los tres picos se han desplazado hacia la derecha, en la misma dirección en la que se ha movido el robot. Además, seguro que os habéis dado cuenta de que los picos son más chatos y anchos ahora. Esto se debe a que la medición del movimiento añade más incertidumbre a la creencia.

Figura 4

Pero en la Figura 4, llega una nueva medición del sensor. Y otra vez nos dice que estamos viendo una puerta con gran certeza, por lo que tenemos de nuevo tres picos en las posiciones en las que se encuentran las puertas. Cuando el robot utiliza esta nueva información para actualizar su creencia, nos llevamos una bonita sorpresa. De los tres picos que teníamos antes, dos de ellos casi han desaparecido, han aparecido otros dos piquitos y uno de los picos, el que corresponde a la puerta dos, se ha vuelto muy alto y estrecho. Esto quiere decir que el robot cree con gran certeza que se encuentra delante de la puerta dos, lo cual es cierto.

Figura 5

En el siguiente paso (Figura 5) el robot vuelve a moverse hacia la derecha. Ello provoca que el pico más alto se achate y se anche, pero también hace lo mismo con los demás picos que casi desaparecen. ¡Esto es extraordinario! En tan solo dos mediciones y dos movimientos, el robot ha pasado de no saber nada acerca de su posición, a estar muy seguro de saber donde está.

En la próxima entrada os explicaremos cómo hemos procedido a actualizar la creencia del robot con la información del movimiento y las mediciones del sensor. Si os habéis fijado, las mediciones nos han aportado más seguridad en la creencia (picos más altos y estrechos), mientras que los movimientos han aumentado la incertidumbre (picos más chatos y anchos). Las razones de todo esto son muy simples y se limitan a sumas y multiplicaciones. Nada más que simples sumas y multiplicaciones. Todo ello dentro del llamado Filtro Bayesiano. Pero eso ya lo veremos en la siguiente entrada.

Nos seguimos leyendo…

Anuncios

4 Respuestas a “¿Dónde estoy?

  1. Pingback: El problema del huevo y la gallina | Cuentos Cuánticos

  2. Pingback: … y con Bayes hemos topado! | Cuentos Cuánticos

  3. Muy interesante, enhorabuena.

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