Navegación autónoma

by @gazkune

De poco sirve construir robots si estos nos son capaces de hacer nada. No podemos detenernos ahora que ya hemos conseguido construir uno con sus ruedas, sensores, brazos y demás dispositivos descritos en la entrada Sobre eso que llaman robótica. Ahora tenemos que lograr que nuestro robot sea capaz de ejecutar tareas que sean útiles para nosotros. Y para ello, debemos dotarlo de habilidades. Por ejemplo, si queremos que nuestro robot nos traiga un refresco del frigorífico, debemos de asegurarnos de que éste posee las habilidades de navegar por nuestra casa, de manipular objetos con sus brazos y de agarrar objetos, entre otras cosas.

Vamos a iniciar un minicurso centrado en una de esas habilidades: la navegación autónoma. Entendemos por navegación autónoma la capacidad de ir de un punto del espacio a otro evitando obstáculos. Esta habilidad ha sido considerada como vital para los robots que nos interesan, ya que de poco nos sirve un robot que no sea capaz de moverse en su entorno. Historicamente la navegación es uno de los campos que más esfuerzos ha concentrado. Hoy en día, es un campo de estudio muy maduro que está sirviendo de base para investigaciones muy interesantes como el campo de la manipulación móvil. Por ello, consideramos que es básico conocer los trabajos que se han hecho en navegación para entender la robótica actual.

El problema de la navegación

Intuitivamente hablando, si alguien nos dice que vayamos a la cocina de casa para algo concreto, nosotros nos encontraremos ante el problema de navegar. Para ello, hemos de saber varias cosas:

1.- Primero hemos de saber dónde estamos.

2.- Segundo, tenemos que saber donde está la cocina, para lo cual es indispensable conocer la casa y haber memorizado la estructura de la misma.

Pues bien, una vez que sabemos nuestra posición y nuestro destino, tenemos que dar con una ruta que una a ambas posiciones. Acto seguido procederemos a caminar para completar la ruta que hemos previsto. En ese caminar, puede que nos salga el perro de casa y tengamos que esquivarlo para finalmente llegar a la cocina sin ningún problema.

Este proceso que acabamos de describir y que nos parece tan simple por lo cotidiano del mismo, ha requerido de años y años de investigación antes de que se haya podido implementar en un robot móvil. En los pasos que hemos identificado se encuentran los retos de la navegación autónoma:

a)  Localización: el robot debe saber en todo momento dónde se encuentra.

b) Mapeo: el robot debe saber construir una representación de su entorno o mapa.

c) Planificador de rutas: el robot debe saber calcular el mejor camino para llegar a su destino.

d) Seguimiento de rutas: el robot debe ser capaz de seguir la ruta calculada evitando obstáculos.

En el siguiente diagrama vamos a dibujar la relación de todos estos bloques.

Como antes, tenemos que imaginar que a nuestro robot le hemos comandado que vaya a una posición concreta de su entorno. Por ahora solo consideraremos la navegación en dos dimensiones. Es decir, imaginaremos que nuestro robot es solo capaz de desplazarse en un plano. No es capaz de volar, ni de subir unas escaleras, ni trepar por una pared. Esta restricción nos permite representar la posición del robot con un vector de tres elementos: , donde e representan la posición en el plano cartesiano y la orientación del robot.

Por tanto, hemos comandado a nuestro robot que vaya hasta una posición desde su posición actual . Estas posiciones se dan respecto a un marco de referencia al que llamamos sistema de coordenadas del mundo y se sitúa respecto al mapa del entorno. No importa mucho dónde situemos el marco de referencia respecto al mapa (en el centro, en una esquina,…), pero una vez fijado el marco, todas las posiciones del mapa se dan respecto a ese punto. Suponiendo que el mapa es un plano finito, por sencillez, situaremos el origen del sistema de coordenadas del mundo en el centro del mapa.

Lo que presentamos en este diagrama es la solución más común al problema de la navegación. Cabe señalar que como otras tantas veces en robótica, el mismo problema se puede abordar de distintas formas. Sin embargo, la solución genérica que se plasma en el diagrama es el más común y el que vamos a analizar.

Los componentes de la navegación

Vamos a explicar por encima los problemas que tratan de resolver cada uno de los bloques del diagrama representado en la figura. En las siguientes entradas profundizaremos en cada una de ellas y propondremos soluciones bien fundamentadas. Por ahora, nos conformaremos con entender lo que queremos hacer, que no es poco. Lo primero es que interpretemos bien lo que cada bloque representa. Para nosotros, estos bloques tienen entradas de información, sobre la cual corren uno o varios algoritmos, produciendo a su vez salidas de información. Vamos allá:

Localización
El bloque de localización trata de estimar la posición actual del robot respecto a las coordenadas del mundo. Normalmente, en un robot móvil, se suelen tener tres fuentes de información:

1.-  La posición según la odometría: recordad los encoders que explicábamos en la entrada Sobre eso que llaman robótica. Explicaremos con más profundidad este proceso por su relevancia, pero por ahora quedémonos con que la odometría nos da la posición relativa del robot respecto a su punto de comienzo y suele acumular mucho error a medida que el robot va moviéndose. Es decir, la posición estimada tiene una fiabilidad muy baja. En una simple analogí­a con los humanos, estimar la posición por odometría equivaldrí­a a que nosotros estimáramos nuestra posición contando los pasos que estamos dando. Haced la prueba en vuestro barrio y ya veréis que pronto os perdéis.

2.- Las observaciones de los sensores: nosotros empezaremos con un láser raspao.

3.- Un mapa del entorno: idealmente debería ser creado por un proceso de mapeo, pero también se puede trabajar con planos elaborados a priori que se ajusten al entorno y a las observaciones del sensor de localización. En definitiva, nosotros supondremos que contamos con un mapa en forma de bitmap (ampliaremos esto en la entrada sobre mapeo).

Seguro que alguien habrá pensado ya: ¡pero que use un GPS que a mí me funciona de cine! Para robots móviles que operan en exteriores, esta es una opción que se suele utilizar. Sin embargo, en interiores el GPS de siempre no funciona. En su defecto sí hay sistemas de localización de interiores que se podrían usar. La cuestión es que nosotros no queremos usarlos. Nos interesa programar robots que no tengan dependencia con sistemas externos al mismo. Nos interesan robots que sean capaces de reconocer sus entornos y saber dónde están en cada momento. Queremos no modificar nuestros entornos habituales para que un robot funcione.

Mapeo
El problema del mapeo consiste en construir una representación útil del entorno del robot. En navegación, un mapa se suele utilizar basicamente para dar soporte a otros dos procesos que aparecí­an en el diagrama de la figura: la localización y la planificación de rutas. Hay varias representaciones posibles que pueden ayudar para estos dos procesos pero en este minicurso nos centraremos en los llamados mapas geométricos. Estos ofrecen un marco ideal para trabajar con sensores como el láser y simplifican y unifican las tareas de localización y planificación, en el sentido de que podemos abordar las dos tareas utilizando un mismo mapa. Hay que tener en cuenta que no todas las representaciones permiten crear un mapa que dé soporte a los dos procesos a la vez.

De este modo, definiremos el mapeo como el proceso de construir una representación geométrica del entorno utilizando las observaciones de un sensor (láser en nuestro caso) y la estimación de la posición según la odometrí­a (permitidnos que no profundicemos más en este tema por el momento, pero en entradas futuras veremos que esto no es tan simple; por ahora dos preguntas al aire: ¿cómo podemos mapear sin saber dónde estamos? y ¿cómo podemos saber dónde estamos sin mapa alguno? Ahí lo dejamos…).

Planificador de trayectorias
Un planificador de trayectorias debe ser capaz de generar una trayectoria libre de obstáculos entre dos posiciones cualquiera del mapa. Las posiciones que nos interesan, claro está, son la posición actual del robot y la posición objetivo comandado por el usuario del robot. Definimos trayectoria como la secuencia de posiciones del mapa que unen la posición de partida y de destino, dónde se cumple que la línea recta que une dos posiciones contiguas no contenga ningún obstáculo.

Para calcular dicha trayectoria, el planificador recibe la información de la posición actual del robot, el mapa del entorno y la posición objetivo. Es en el mapa del entorno donde el planificador podrá saber en qué posiciones se encuentran los obstáculos del entorno. Con esta información, se requiere que el planificador calcule la trayectoria óptima. La definición de óptima suele agrupar diversos parámetros, pero por ahora, nosotros identificaremos como trayectoria óptima a aquella que minimice la distancia a recorrer entre las dos posiciones.

Seguimiento de trayectorias
Una vez se calcule la trayectoria, necesitamos que el robot se mueva sobre la misma. Para ello hay que diseñar un proceso que conociendo la trayectoria pueda generar velocidades que los motores ejecuten y hagan que el robot se mueva siguiendo la trayectoria planificada. Cuando hablamos de velocidades nos referimos a la velocidad en los ejes y que denotaremos como . A estos tres componentes de la velocidad se les suele llamar respectivamente velocidad de traslación, velocidad lateral y velocidad de rotación. Nosotros supondremos que los motores de nuestro robot ya cuentan con unos controladores donde se sabe como transformar estos tres componentes de la velocidad, a velocidades de giro de los motores que tienen cada una de las ruedas (ya hablaremos de estos algoritmos en alguna entrada, como no podrí­a ser de otra forma).

Sin embargo, esto no es suficiente. Tal vez con lo descrito hasta ahora un robot podría sobrevivir y navegar en un mundo estático. Lamentablemente, el nuestro no lo es. En las casas la gente se mueve de un lado a otro, tenemos mascotas que hacen lo mismo, las puertas se abren y se cierran, las sillas se cambian de sitio… el seguimiento de trayectorias no puede ignorar todo esto. Es por ello que es necesario alimentar el proceso con la información del entorno en cada momento, utilizando un sensor láser, por ejemplo. Así­, el proceso de seguimiento de trayectorias debe evitar obstáculos y corregir sus movimientos en función de lo que va observando en su entorno más cercano, pero sin desviarse demasiado de la ruta planificada.

Ahora que hemos aclarado de forma ligera el contenido de cada uno de los bloques que forman un sistema de navegación, ya tenemos la foto global del problema. De aquí­ en adelante empezaremos a desgranar cada uno de los bloques descritos. Cabe señalar que no existe una única solución para los problemas que hemos descrito. Es más, en los más de 50 años de robótica, se han diseñado cantidad de soluciones. Normalmente ninguna de ellas es perfecta. Siempre hay ventajas y desventajas. Por ello, nos es imposible ir introduciendo todo en este minicurso. Aún sabiendo que dejaremos al lado interesantes soluciones que funcionan bien, a lo largo de las siguientes entradas tenderemos a centrarnos en una solución concreta. Si algún bloque genera más expectación entre los lectores, se podría plantear escribir entradas describiendo más soluciones y discutiendo las implicaciones de cada una de las decisiones. Por nuestra parte, los criterios de selección de un algoritmo frente a otros han sido:

1.-  Las ventajas que ofrece el algoritmo frente a otros.

2.- El uso del algoritmo por parte de la comunidad robótica.

3.- Disponer de una implementación del algoritmo que podamos utilizar para probarlo.

Sí­, como podéis leer en el último punto, nuestra intención es que los lectores podáis probar estos algoritmos, uno a uno, en vuestros ordenadores, hasta tener un robot que navegue autonomamente en un entorno de simulación. Esperemos que os guste la idea y que seamos capaces de explicar todo bien para que juguéis con vuestros propios robots virtuales.

Nos seguimos leyendo…

by @gazkune