De lo global a lo local y vuelta a empezar

Ha pasado mucho tiempo desde la última entrada sobre navegación autónoma. Seguramente, pocos tendremos frescos los conceptos explicados en las últimas entradas. Conceptos que ahora pretendemos recuperar para explicar cómo se relacionan. Por ello, recomendamos volver sobre las dos últimas entradas:

Planificación de rutas

Planificación local

Resumiendo mucho, en la primera entrada descubrimos cómo planificar la ruta entre dos puntos dados teniendo el mapa del entorno. En la segunda entrada, vimos cómo calcular las velocidades que el robot debe ejecutar para seguir la ruta calculada, evitando a la vez los obstáculos percibidos por los sensores.

Ahora, en esta corta entrada veremos cómo se relacionan el planificador de rutas y el planificador local para trabajar como un único sistema.

En el escenario ideal, parecería que la relación es totalmente natural: el planificador de rutas calcula una trayectoria, se la manda al planificador local, y éste, va calculando las velocidades adecuadas iteración a iteración. Si hay algún obstáculo por el camino, no contemplado en el mapa del planificador de rutas, no pasa nada, ya que el planificador local está preparado para ello. Se esquiva el obstáculo, alejándose de la ruta establecida, pero una vez superado el obstáculo, la función de coste empezará a generar velocidades que nos devuelvan a la ruta.

Hasta allí todo normal. Cómo programador de robots podemos estar orgullosos de que nuestro robot haya sido capaz de esquivar al gato y seguir con su ruta. Pero (ya llegan los peros), ¿qué pasa si nuestra ruta nos lleva por una puerta que al llegar, se encuentra cerrada? Lo obvio sería abrirla. Eso, sin embargo, nos llevaría a otros campos de la robótica como la manipulación, el agarre y etc que ahora no vamos a tratar. Desde el punto de vista de la navegación autónoma nos encontramos ante el problema de una ruta bloqueada.

Una ruta bloqueada no puede gestionarse desde la planificación local. De alguna manera, necesitamos actualizar el mapa del planificador de rutas y pedir a éste que calcule una nueva trayectoria dadas las nuevas condiciones. Lo que acabamos de describir es la re-planificación.

En un sistema de navegación que funcione en el mundo real, la actualización del mapa global y la re-planificación son indispensables. Normalmente, un sistema de navegación suele tener un mapa global (el que usa el planificador de rutas) y un mapa local (el que usa el planificador local). El mapa global contiene la información de la estructura de todo el entorno del robot. Si nuestro robot trabajara en un supermercado, el mapa global representaría el plano completo de dicho supermercado. Por el contrario, el mapa local suele tener una extensión mucho más reducida (típicamente 5 x 5 metros). El mapa local se refresca continuamente, cada vez que recibimos un nuevo dato de los sensores, para que el planificador local cuente con información fresca en cada iteración.

Para que la re-planificación sea posible, el mapa global también ha de refrescarse con nueva información. Los criterios de refresco del mapa global son varios, y dependen mucho de las capacidades de computación y memoria de los ordenadores usados. Imaginemos que podemos actualizar el mapa global cada vez que tengamos datos nuevos (nuestro ordenador nos permite ser tan chulos). En ese caso, ¿cómo planteamos la re-planificación? En esto, también, hay varios criterios. Con una fuerza computacional enorme, podríamos re-planificar constantemente las rutas, y casi no necesitaríamos tener un planificador local. Esto, sin embargo, no es posible, sobre todo cuando hablamos de entornos grandes. Un planificador local puede estar haciendo cálculos a unos 20 Hz (20 iteraciones por segundo), que es más o menos el refresco que tienen los sensores. Hoy en día, los planificadores globales en entornos más o menos grandes (hablamos de un supermercado, no un pueblo entero), pueden tardar del orden de un segundo. Tened en cuenta que estos datos dependen muchísmo de la extensión del entorno mapeado y la capacidad de computación. No os quedéis con los datos en sí. Lo que nos interesa es ver no los tiempos concretos, sino la diferencia de tiempos entre un planificador de rutas y un planificador local.

Dada la «lentitud» de un planificador de rutas, hay que establecer criterios de re-planificación eficientes. Tenemos que re-planificar cuando sea necesario, confiando en el planificador local en los demás casos. Una vez más, los criterios son varios. Vamos a ver uno sencillo.

Una ruta no es más que una secuencia de puntos. Por lo tanto, el robot intenta pasar por cada uno de esos puntos. Un criterio de re-planificación sencillo puede ser aquel que verifique si el siguiente punto es alcanzable en línea recta. Si hay un obstáculo entre dos puntos consecutivos, pedimos al re-planificador que nos planifique una ruta nueva desde el punto actual al punto final. Simple y efectivo.

Este criterio es básico. Hay muchísimas cosas más que podríamos añadir. Por ejemplo, ¿por qué planificar hasta el punto final y no sólo hasta el siguiente punto libre de obstáculos? Eso nos permitiría reaprovechar gran parte de la ruta original. Pues bien, estas y otras ideas se aplican a los planificadores actuales, con tal de lograr una re-planificación eficiente.

Lo más importante de esta entrada era darse cuenta de la necesidad de alterar los planes cuando un robot opera en un entorno dinámico, es decir, en un entorno que cambia. La re-planificación, al margen de cómo se lleve adelante, es un elemento crucial para un sistema de navegación. Intenta relacionar armoniosamente el trabajo del planificador de rutas con el planificador local.

Nos seguimos leyendo…