Movimientos de robots y variedades matemáticas (manifolds)

¡Compártelo!
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

(An English version has been published in Mapping Ignorance)

Hoy abordaremos un reciente artículo de Jaillet y Porta (Instituto de Robótica i Informàtica Industrial, IRI), que revela nuevas aplicaciones prácticas de entidades matemáticas tan abstractas como son las variedades.

Cuando se trata de robots no podemos olvidar que su objetivo fundamental siempre estará de alguna manera relacionado con moverse. Ya se trate de brazos robóticos como las que se encuentran en las fábricas de coches, encargadas de soldar o de alimentar con piezas a otras máquina, o se trate de robots móviles, que se mueven a ellos mismos por todo el espacio de trabajo.

«¿Por dónde tiro que no la líe?» (Créditos: 1)

En general, la posición y la orientación de un robot con N grados de libertad se puede parametrizar completamente por medio de N coordenadas. Sin embargo, hacer que el sistema se mueva desde una configuración inicial q0 a un estado objetivo q1 puede no ser tan sencillo como parece. Para empezar, pueden existir obstáculos en el camino, así que se deben considerar para evitar colisiones. En segundo lugar, tenemos lo que se llaman restricciones no holónomas. Los vehículos con ruedas son un ejemplo perfecto. Es fácil entender que la posición y orientación de un vehículo terrestre se pueden definir perfectamente mediante tres coordenadas (la posición en 2D sobre el suelo, más un ángulo para la orientación). Pero el vehículo en sí, considerado como un mecanismo, sólo tiene dos grados de libertad: la posición de cada una de las dos ruedas motrices si es diferencial, o la velocidad y la dirección del volante en automóviles comerciales. Existe una relación compleja (una ecuación diferencial) entre las velocidades de las ruedas y la posición en la que el vehículo termina. ¡Basta con pensar en lo difícil que se hace aparcar en un espacio estrecho!

Maniobrar con un coche para llegar a una posición deseada es un ejemplo perfecto de la familia más amplia de problemas matemáticos conocidos como planificación de la trayectoria o, más visualmente, el problema de mover un piano. Resumiendo, las principales dificultades surgen cuando se considera que los objetos pueden rotar, ya que el espacio de estados en el que hay que buscar soluciones aumenta su número de dimensiones. Si salir de un laberinto 2D es difícil, más lo es hacerlo de uno donde pudieras moverte en 3D, ¿verdad? Pues imagina ahora uno en seis o más dimensiones… ese tipo de desafíos es al que se enfrentan los planificadores de movimiento en robótica.
Construcción incremental de un rapidly exploring random tree (RRT).  Recomiendo ver también esta animación del proceso de construcción (Fuente: [1])


Durante la década de 1990 los investigadores descubrieron que integrar algo de aleatoriedad en este gigantesco proceso de búsqueda resultaba ser una buena idea. Los rapidly exploring random trees (RRT) [1] son ​​un tipo estructuras en forma de árbol construidas escogiendo puntos objetivos al azar en el espacio libre, comprobando a continuación si la ruta de acceso hasta el árbol está libre de obstáculos y, si es el caso, ampliando el árbol con una nueva rama.

Una aplicación real de RRTs se puede ver en el siguiente vídeo, aplicado a una carretilla elevadora automatizada:


Los métodos RRT son muy populares hoy en día porque funcionan bien en muchos casos. Ahora bien, ¿qué pasaría si imponemos restricciones adicionales al problema? Por ejemplo, imaginemos que tenemos que planificar el trayecto para el brazo robótico de un camarero que debe mantener los platos en horizontal todo el tiempo para que no vuelquen. Escoger configuraciones aleatorias al azar para la construcción de un árbol es ahora una idea condenada a fracasar, ya que sólo una minúscula fracción de todas las posibles configuraciones cumplen las restricciones. De hecho, tenemos una probabilidad de cero de escoger un punto válido que, sin embargo, no implica que sea absolutamente imposible.

Es evidente que necesitamos algo diferente cuando existen estas limitaciones. La propuesta de Jaillet y Porta, publicada recientemente en la revista IEEE Transactions on Robotics [2], en gran medida se basa en la comprensión de la geometría abstracta de las variedades. Resulta que el espacio de estados de todas las configuraciones permitidas es una variedad, de ahí la importancia del concepto.


Pero, ¿qué son exactamente las variedades? Informalmente, se puede pensar en ellas como en espacios (2D, 3D, etc) que parecen euclídeos a nivel local y que «viven» incrustados en un espacio de mayor dimensionalidad. Un ejemplo perfecto es la superficie de la Tierra: es una variedad 2D porque, bueno … ¡es una superficie! Sin embargo, «vive» en un mundo 3D (el planeta visto en su conjunto), por lo que tiene una curvatura que, aún siendo muy pequeña, se puede ver cuando observamos grandes porciones de la superficie. Una área pequeña de la superficie podría aproximarse muy bien como una superficie perfectamente plana.

Con esta idea en mente, podemos tomar una variedad entera y construir lo que se llama un atlas de aproximaciones lineales locales (los llamados mapas o charts de los espacios tangentes) para un conjunto discreto de ubicaciones sobre la variedad:


(Izquierda) Un atlas de una esfera: cada polígono es una aproximación planar a la esfera en esa región. (Derecha):  La malla topológica generada por dicho atlas. (Fuente: [2])




En su artículo, Jaillet y Porta proponen un algoritmo que intercala la ejecución de RRT con la construcción del atlas de la variedad asociada al problema cinemático que se trate. Puesto que el error introducido por la aproximación lineal (los mapas) de la variedad en un punto dado aumenta con la distancia a su centro, proponen un conjunto de heurísticas para determinar en qué puntos establecer las fronteras entre los diferentes mapas.

(Arriba) La variedad es la línea negra sólida, sobre la que se construye un mapa alrededor de xi. Para un punto lejano en la variedad, como xj, la aproximación introducida por el mapa lineal puede dar lugar a grandes errores. (Abajo) Cuando eso ocurre, se debe crear un nuevo mapa. (Fuente: [2])


La clara ventaja de esta propuesta es que ahora podemos contar con los mapas existentes para generar nuevas configuraciones aleatorias, las cuales serán válidas y cumplirán todas las restricciones, permitiendo ejecutar el algoritmo RRT «clásico» para evitar obstáculos.


Skeletal formulas of both conformations
Ball-and-stick model
Ball-and-stick model
«Boat-chair»
«Crown»

Las dos posibles configuraciones de una molécula de ciclooctano (Créditos: Wikipedia)




Encontrar un camino entre las dos configuraciones de ciclooctano (ver tabla arriba) llevó 1,94 segundos con el algoritmo propuesto, en el que 139 mapas y 5812 nodos fueron evaluados en la variedad de las configuraciones posibles de la molécula. Para dar otro ejemplo, podemos ver el método aplicado a la planificación de la mano de un robot en la siguiente figura, que costó 8,23 segundos a pesar de requerir un menor número de mapas (50) y nodos (1503).


Posición inial (izquierda) y final (derecha), para una mano robótica que sujeta una herramienta. (Fuente: [2])


En resumen, este nuevo enfoque parece prometedor para la planificación de movimiento de manera eficiente y robusta tanto en robots móviles como en manipuladores robóticos. Juntando a esto que los autores han tenido el detalle de publicar una implementación de código abierto hace que, probablemente, esta técnica se convierta en una solución popular en futuros diseños robóticos.

Referencias:

  •         [1] S. LaValle, «Rapidly-exploring random trees: A new tool for path planning,» Technical Report 98-11, Iowa State University, Ames,IA, Oct. 1998
  •          [2] Jaillet, L.; Porta, J. M.; , «Path Planning Under Kinematic Constraints by Rapidly Exploring Manifolds,» IEEE Transactions on Robotics, vol.29, no.1, pp.105-117, Feb. 2013. doi: 10.1109/TRO.2012.2222272


¡Compártelo!
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
Etiquetado con: , ,