Non-Euclidean Motion Planning with Graphs of Geodesically-Convex Sets

Autores: Thomas Cohn, Mark Petersen, Max Simchowitz, Russ Tedrake · RSS 2023

Licencias

• Acceso abierto
• Artículo: CC BY 4.0

Todo lo que sigue se basa en el artículo completo bajo su licencia CC BY 4.0; su figura se muestra con crédito a los autores.

En resumen

Trata los espacios articulares que dan la vuelta sobre sí mismos (bases móviles, articulaciones continuas) como variedades planas, de modo que el planificador de caminos más cortos GCS sigue dando caminos globalmente óptimos y sin colisiones.

Por qué importa

Los manipuladores móviles y los brazos con articulaciones de base sin límites pueden usar ahora un planificador que certifica que cada punto de la trayectoria está libre de colisiones y, cuando se resuelve de forma exacta, que es óptima dentro del espacio libre certificado. El artículo también demuestra que la curvatura positiva (por ejemplo, articulaciones de rótula SO(3) o cuerpos en flotación libre) rompe la convexidad, lo que marca hasta dónde no puede llegar este enfoque.

Problema

El planificador GCS de Marcucci et al. encuentra caminos sin colisiones y globalmente óptimos mediante una descomposición del espacio de configuración libre en conjuntos convexos, pero solo para espacios de configuración euclídeos. Una base móvil que puede girar 360° completos, o una articulación de revolución continua, da la vuelta sobre sí misma, por lo que su espacio de configuración no es euclídeo. Añadir límites articulares artificiales o tratar los ángulos como reales no acotados hace que el óptimo sea inalcanzable o exige conocer de antemano la respuesta y muchos conjuntos duplicados.

Solución propuesta

Los autores modelan el espacio de configuración como una variedad riemanniana y definen un Graph of Geodesically-Convex Sets (GGCS, grafo de conjuntos geodésicamente convexos), y demuestran que conserva las garantías del GCS ordinario. Para variedades planas (de curvatura cero), que cubren cualquier robot construido con articulaciones de 1 DoF más una base SE(2), cada conjunto se lleva a un espacio euclídeo mediante una carta de isometría local, y el problema se reduce a un problema GCS estándar de optimización convexa entera mixta con restricciones de transición afines. Las regiones se hacen crecer con IRIS y se acotan por articulación con el radio de convexidad, y las trayectorias de Bézier por tramos con restricciones de continuidad se mantienen.

Ideas clave

• SE(2), toda variedad de dimensión 1 y los productos de variedades planas son planos, por lo que los robots formados por articulaciones de un solo DoF y una base móvil encajan en el método; las articulaciones de rótula de 3 DoF no
• Acotar cada región IRIS por articulación con el radio de convexidad garantiza que la región siga siendo geodésicamente convexa al llevarla de vuelta a la variedad
• En un espacio plano con coordenadas alineadas globalmente, los mapas de transición son afines, por lo que las restricciones de coincidencia de extremos y de continuidad de derivadas siguen siendo convexas
• Basta un solo punto de curvatura positiva para que la función de distancia riemanniana sea no convexa en todo entorno de ese punto (Teorema 5)

Resultados principales

• Robot puntual en un toro: camino óptimo con vuelta completa en 0,79 s; brazo plano de 5 articulaciones con articulaciones continuas: planifica en 5,36 s y 4,63 s, y uno de los planes gira la articulación central más de 360°
• Brazo plano: caminos de relax-and-round (relajar y redondear) de longitud 7,749 y 8,448 frente a los óptimos de branch-and-bound de 7,274 y 8,008
• KUKA iiwa con una articulación de base continua (simulación): 14 movimientos de clasificación de tazas usando 18 regiones convexas, con una media de 25,75 s por movimiento (rango de 4,63 a 50,30 s)
• PR2 (simulación, espacio de configuración de 15 dimensiones), 7 tareas de alcance en estanterías: los caminos de GGCS estuvieron libres de colisiones en todos los casos, p. ej., 1M→4M con longitud 3,875 frente a 14,554 del PRM; Drake-Trajopt y PRM+Trajopt dieron a veces caminos más cortos, pero con ligeras colisiones
• La planificación en línea del PR2 tardó de 25,51 a 66,15 s con GGCS-Planner, frente a 0,49 a 0,54 s del PRM, 2,26 a 15,23 s de Drake-Trajopt y 11,61 a 40,10 s de PRM+Trajopt
• Preparación fuera de línea del PR2: una región IRIS tardó 30,20 s de media (de 8,56 a 75,42 s), todas las regiones 156,63 s en paralelo; construir el PRM de 100.000 muestras tardó 124,39 s

Limitaciones

• Los autores afirman que el método no puede manejar costes y restricciones no convexos, como la dinámica no lineal y las cadenas cinemáticas cerradas, ni las articulaciones de rótula
• Los espacios de curvatura positiva como SO(3) quedan excluidos, porque allí la función de distancia es demostrablemente no convexa
• La optimalidad solo se cumple dentro del espacio libre 'certificado' que cubren las regiones; el rendimiento depende mucho de la elección de las regiones, y para el PR2 algunas regiones intermedias se añadieron a mano
• Los tiempos de planificación en línea del PR2 (de 25,51 a 66,15 s) fueron mayores que los de todos los métodos de referencia comparados
• Todos los resultados con robots son en simulación; los autores citan como trabajo futuro la planificación bimanual con restricciones cinemáticas implícitas y la planificación a través del contacto

Impacto en el campo

Finalista del RSS 2023 Best Paper Award, con 44 citas. Los autores publican grabaciones interactivas de todas las trayectorias en un sitio web de resultados.

Resumen

Calcular trayectorias óptimas y sin colisiones para sistemas de alta dimensión es un problema difícil. Los planificadores basados en muestreo tienen dificultades con la dimensionalidad, mientras que los optimizadores de trayectorias pueden quedarse atrapados en mínimos locales debido a las no convexidades inherentes del paisaje de optimización. El uso de la programación entera mixta para encapsular estas no convexidades y encontrar trayectorias globalmente óptimas se ha mostrado recientemente muy prometedor, gracias en parte a relajaciones convexas ajustadas y a estrategias de aproximación eficientes que reducen mucho los tiempos de ejecución. Estos enfoques se limitaban hasta ahora a espacios de configuración euclídeos, lo que impedía su uso con bases móviles o articulaciones de revolución continuas. En este artículo abordamos estos escenarios modelando los espacios de configuración como variedades riemannianas, y describimos un procedimiento de reducción, para el caso de curvatura cero, a un problema de optimización convexa entera mixta. Demostramos nuestros resultados en varias plataformas robóticas, incluida la generación de trayectorias eficientes y sin colisiones para un manipulador móvil bimanual PR2.

Enlaces

• arXiv 2305.06341: https://arxiv.org/abs/2305.06341
• DOI 10.1177/02783649241302419: https://doi.org/10.1177/02783649241302419
• PDF: https://arxiv.org/pdf/2305.06341v1
• Página del proyecto: https://ggcs-anonymous-submission.github.io/