El slalom de los robots

En la última entrada Buscando caminos nos enfrentamos al problema de cómo calcular la trayectoria más corta entre dos puntos. Ya señalamos entonces que una vez calculada la ruta, tendríamos que hacer que nuestro robot fuera capaz de ejecutar esa ruta. En otras palabras, sabiendo la trayectoria que nos llevará a nuestro destino, tenemos que calcular los comandos de velocidad que haremos llegar a los motores en cada instante, para seguir la trayectoria calculada. En la literatura, este problema recibe muchos nombres diferentes: navegación local, evitación de obstáculos, seguimiento de trayectorias, planificación local… todos ellos tienen matices que los hacen ligeramente diferentes. Sin meternos a justificar nuestra elección, el problema descrito lo conoceremos cómo planificación local.

Pero no sólo hay muchos nombres para el problema de la planificación local, sino que también hay muchísimas soluciones. Lamentablemente no existe un método experimental ni analítico para decidir qué solución es mejor. Esto se debe a muchas razones que ahora no podemos explicar. Sin embargo quisiéramos subrayar que hoy en día la comunidad está dedicanco importantes esfuerzos en esta dirección.

Nosotros, en esta entrada intentaremos explicar una de las soluciones más usadas hoy en día para robots móviles. El algoritmo que vamos a decribir se llama Dynamic Window Approach (DWA en adelante), y nuestra descripción se basa en el artículo original:

D. Fox, W. Burgard, and S. Thrun. Controlling synchro-drive robots with the dynamic window approach to collision avoidance. In Proc. of thelEEE/RSJ International Conference on IntelligentRobots and Systems, 1996

¡Vamos allá! Primero empecemos por definir mejor el contexto. Supongamos que tenemos un robot móvil capaz de ejecutar comandos de velocidad. Un comando de velocidad se define con el vector , es decir, velocidad de traslación y rotación del robot. Recordad que nuestro robot tiene un escáner láser o similar para poder ver los obstáculos que le rodean. Además, también conocemos la trayectoria que nos ha planificado el planificador de rutas. Con esta información, busquemos el comando de velocidad que nos permita seguir la ruta establecida evitando los obstáculos que puedan salir a nuestro paso.

Lo primero que hace el DWA es simplificar el problema de las trayectorias con una aproximación muy útil: vamos a suponer que toda trayectoria es una suma de arcos de círculo ejecutados en intervalos cortos de tiempo. Es decir, siendo el intervalo de tiempo entre dos cálculos de velocidad del algoritmo, la trayectoria que ha hecho el robot en ese intervalo es el arco de círculo definido por . Esta aproximación se hace buena para intervalos cortos de tiempo ( para robots de velocidad máxima de ).

En cada ciclo del algoritmo se define el grupo de velocidades candidato entre los que elegiremos la velocidad más adecuada. ¿Cómo se define este grupo de velocidades? Nada más y nada menos que calculando la intersección de tres grupos: el grupo de todas las velocidades ejecutables por el robot, las llamadas  velocidades admisibles y las velocidades de la ventana dinámica (el algoritmo debe su nombre a este último grupo). Como el primer grupo no necesita mayor explicación, vamos a ver los dos últimos.

El grupo de velocidades admisibles () se define como el grupo de velocidades que permiten parar al robot en el siguiente intervalo de tiempo antes de chocar contra un obstáculo. Supongamos que es la distancia a la que se encuentra un obstáculo en el arco definido por la velocidad . Entonces, cosiderando las ecuaciones de cinemática para un cuerpo con aceleración constante, tenemos que dónde:

y

Fijaos que y se refieren a la aceleración lineal y aceleración rotacional del robot, es decir, la capacidad de frenada de nuestro robot. Lo que conseguimos con la definición de es considerar sólo aquellas velocidades que no nos lleven a colisionar con un obstáculo. Por lo que nos aseguramos que la velocidad elegida al final del ciclo será una velocidad segura.

Ahora vayamos a por las velocidades de la ventana dinámica (). Siendo la velocidad actual del robot , las velocidades de la ventana dinámica son aquellas velocidades alcanzables en este intervalo de tiempo. Para ello, una vez más necesitamos considerar las aceleraciones lineales y rotacionales del robot. La idea de este grupo de velocidades es eliminar aquellas velocidades que sabemos que no podremos ejecutar en ester intervalo por nuestra limitada capacidad de aceleración. Por lo tanto donde:

y

Así, una vez hemos definido todos los grupos, el grupo de velocidades candidatos será la intersección de los tres grupos. Intuitivamente, nos quedamos con aquellos arcos de círculo que sean seguros y alcanzables dados los obstáculos detectados con nuestro sensor, la velocidad actual del robot y las aceleraciones de los motores.

Ahora necesitamos una forma de elegir cuál de las velocidades es la mejor entre todos los candidatos dentro de . Para ello el DWA utiliza tres parámetros: la alineación con la dirección objetivo, el espacio libre y la velocidad. Vayamos poco a poco.

La alineación con la dirección objetivo se mide como el ángulo existente entre el punto de destino y la orientación del robot. Para ello, en vez de utilizar la posición actual del robot, se utiliza la predicción de la posición que tendría el robot si ejecutara la velocidad en el siguiente intervalo de tiempo (ver Figura 1).

Figura 1

¿Por qué se utiliza este parámetro? La idea es que si el robot se desvía de su trayectoria para esquivar un obstáculo, utilice esta medida de alineamiento para poder recuperar su dirección hacia el objetivo. Pero esto ya se verá mejor al final… ahora vamos con el segundo parámetro.

El espacio libre se mide facilmente utilizando la función , que nos daba la distancia al obstáculo más cercano para el arco de círculo definido por la velocidad . Se supone que en caso de poder elegir, elegiremos aquellas velocidades que nos permitan mantenernos más lejos de los obstáculos. Es decir, idealmente quisiéramos maximizar .

Por último nos queda el parámetro de velocidad, que no es más que el módulo del vector . Este parámetro también es muy intuitivo. Lo que viene a decir es que entre todas las velocidades queremos escoger aquella que nos haga llegar antes a nuestro destino. Dicho de otra forma, queremos maximizar la velocidad.

Bien. Ahora que tenemos tres parámetros, ¿cómo los combinamos? Intuitivamente, lo que queremos hacer es buscar una velocidad que mantenga la dirección respecto al objetivo, que a su vez nos permita mantener a los obstáculos lejos y que además sea la velocidad más alta posible. Estos problemas en las ciencias de computación se suelen resolver con una simple función de coste. Lo que hacemos es asignar un peso a cada uno de los parámetros (según la importancia que queramos que ese parámetro tenga en el resultado final) y buscar aquella velocidad que maximice la suma de los pesos por los parámetros calculados. Algo así:

Para unos pesos definidos, nos quedamos con aquel que maximice  la función de coste . Esa velocidad es la que mandaremos a los motores para que el robot se mueva en consecuencia.

Los pesos , y se establecen en función del comportamiento que queremos imprimir al robot. Los autores del DWA enseñan los pesos que utilizan en sus experimentos (, y ). Suelen ser unos valores buenos para empezar. Luego, con los experimentos, uno va ajustando sus propios pesos.

Para terminar con esta entrada, cabe destacar que el ciclo descrito se ejecuta una y otra vez, calculando continuamente nuevos comandos de velocidad, en función de la nueva información que nos aportan los sensores. Así, si algún obstáculo se mueve, el algoritmo es capaz de reaccionar a tiempo. De todas formas, en la próxima entrada explicaremos mejor la relación entre el planificador de rutas y el planificador local, que seguramente todavía no queda muy clara. Os explicaremos en más detalle cómo se integran ambos componentes, algo que en esta entrada hemos omitido aposta.

Para ir abriendo boca, podéis ver este vídeo para entender mejor de lo que un robot es capaz con los algoritmos descritos en estas entradas.

Nos seguimos leyendo…