Graph of Convex Sets

También llamado: GCS, graphs of convex sets
Categoría: Planning & manipulation › Trajectory optimisation
Etiquetas: motion-planning, convex-optimization, trajectory-optimization, configuration-space, manipulation

Una formulación de planificación de movimiento que enlaza regiones convexas del espacio libre en un grafo y encuentra un camino suave y libre de colisiones a través de ellas mediante optimización convexa.

Definición

Grafo de conjuntos convexos (graph of convex sets, GCS) es un grafo en el que cada vértice es un conjunto convexo y el punto elegido dentro de cada conjunto es una variable de decisión continua. Las aristas conectan conjuntos entre los que se puede pasar, y los costes y las restricciones de las aristas son funciones convexas de los puntos de cada extremo. Encontrar la ruta más barata a través de un grafo así combina una elección discreta, por qué conjuntos pasar, con una continua, a qué lugar de cada conjunto ir. Tobia Marcucci, Russ Tedrake y sus colegas formularon este problema de camino más corto y demostraron que, aunque en general es un problema entero mixto, tiene una relajación convexa fuerte que a menudo es exacta o casi exacta.

Para la planificación de movimiento, la parte libre de colisiones del espacio de configuraciones se cubre primero con una colección de regiones convexas, por ejemplo con el algoritmo IRIS, que hace crecer grandes politopos libres de obstáculos a partir de puntos semilla. Cada región se convierte en un vértice, las regiones que se solapan se unen mediante aristas y, dentro de cada región, la trayectoria se representa como una curva suave, normalmente una curva de Bézier, que permanece dentro de la región porque sus puntos de control también lo hacen. Los costes como la longitud del camino, la duración o la energía, y los límites de velocidad y aceleración, se escriben como restricciones convexas. Resolver la relajación y redondearla da una trayectoria suave y libre de colisiones sin búsqueda basada en muestreo ni posprocesamiento.

El enfoque supone una geometría euclídea ordinaria dentro de cada conjunto. Los robots cuyos espacios de configuraciones dan la vuelta sobre sí mismos, como las articulaciones de revolución continuas sin límites o el rumbo de una base móvil, no encajan directamente en esa suposición. Las extensiones sustituyen los conjuntos convexos por conjuntos geodésicamente convexos sobre una variedad: conjuntos en los que dos puntos cualesquiera están unidos por un único camino más corto, o geodésica, que permanece dentro del conjunto. Con ese cambio, la misma formulación de grafo puede planificar en estos espacios no euclídeos. GCS está disponible en la caja de herramientas Drake.

Por qué importa

Los planificadores basados en muestreo encuentran caminos factibles, pero normalmente necesitan suavizado y no dan ninguna medida de lo bueno que es el camino. GCS produce trayectorias suaves que respetan las restricciones en una sola optimización, a menudo con un certificado de lo cerca del óptimo que está el resultado, lo que es valioso para brazos robóticos que trabajan repetidamente en celdas fijas como estanterías y puestos de trabajo.

Aplicaciones clave

Planificación de trayectorias libres de colisiones para brazos robóticos en celdas de trabajo fijas
Planificación para robots con articulaciones continuas o espacios de configuraciones que dan la vuelta sobre sí mismos
Planificación de pisadas y contactos sobre regiones convexas del terreno
Trayectorias de tiempo mínimo para drones en entornos con muchos obstáculos
Planificación bimanual y multibrazo en espacios de trabajo compartidos

En la práctica

Un equipo que despliega un brazo robótico para recoger de un conjunto fijo de cubetas de estantería genera primero, sin conexión, regiones convexas del espacio de configuraciones libre de colisiones, sembrando IRIS en configuraciones delante y dentro de cada cubeta. Esto lleva tiempo, pero solo hay que rehacerlo cuando cambia la celda. En tiempo de ejecución, cada petición de recogida se convierte en una consulta GCS desde la configuración actual hasta una meta en una cubeta. El solver devuelve una trayectoria suave que respeta los límites de velocidad, y el tiempo de resolución crece con el número de regiones, así que el equipo mantiene el conjunto de regiones no mayor de lo que necesita la celda. Si una meta queda fuera de todas las regiones, la consulta falla, así que el equipo añade semillas donde falta cobertura. Una comprobación de colisiones de horizonte corto sigue protegiendo frente a objetos que no estaban en el modelo.

Ideas erróneas comunes

GCS exige que el espacio libre sea convexo — exige que el espacio libre esté cubierto por una unión de regiones convexas, que puede aproximar formas complejas
GCS siempre devuelve el óptimo global mediante optimización convexa — la relajación a menudo es exacta, pero no siempre; puede hacer falta un redondeo o una resolución entera mixta
GCS sustituye por completo la comprobación de colisiones — garantiza la ausencia de colisiones solo respecto a las regiones usadas, así que las regiones deben reflejar el entorno real

Quién debería saberlo

Ingenieros de planificación de movimiento para brazos robóticos y drones
Investigadores en planificación basada en optimización
Integradores de sistemas de picking y ensamblaje en celdas fijas
Estudiantes de robótica que estudian planificación y optimización convexa

Tecnologías relacionadas

Drake
Generación de regiones IRIS (IRIS Region Generation)
Curvas de Bézier (Bézier Curves)
Optimización convexa (Convex Optimization)
Programación convexa entera mixta (Mixed-Integer Convex Programming)

Términos relacionados

Proyectos relacionados

LeRobot: HuggingFace ML library for real-world robotics in PyTorch
Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim
NVIDIA Isaac GR00T: NVIDIA open foundation model for humanoid robot reasoning and skills
OpenVLA: 7B-parameter Vision-Language-Action model for robotic manipulation
Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
OpenArm: 7DOF humanoid arm for physical AI research in contact-rich environments

Vídeos

MIT Robotics - Russ Tedrake - Planning with Graphs of Convex Sets (in the age of foundation models): MIT Robotics