Graph of Convex Sets

Detto anche: GCS, graphs of convex sets
Categoria: Planning & manipulation › Trajectory optimisation
Tag: motion-planning, convex-optimization, trajectory-optimization, configuration-space, manipulation

Una formulazione di pianificazione del movimento che collega in un grafo regioni convesse dello spazio libero e trova un percorso liscio e privo di collisioni attraverso di esse mediante ottimizzazione convessa.

Definizione

Grafo di insiemi convessi (graph of convex sets, GCS) è un grafo in cui ogni vertice è un insieme convesso e il punto scelto all'interno di ciascun insieme è una variabile decisionale continua. Gli archi collegano insiemi tra cui si può passare, e i costi e i vincoli sugli archi sono funzioni convesse dei punti alle due estremità. Trovare il percorso più economico in un grafo di questo tipo combina una scelta discreta, quali insiemi attraversare, con una continua, dove andare all'interno di ciascun insieme. Tobia Marcucci, Russ Tedrake e colleghi hanno formulato questo problema di cammino minimo e mostrato che, pur essendo in generale un problema intero misto, ha un rilassamento convesso forte che spesso è esatto o quasi esatto.

Per la pianificazione del movimento, la parte libera da collisioni dello spazio delle configurazioni viene prima coperta da una collezione di regioni convesse, per esempio con l'algoritmo IRIS, che fa crescere grandi politopi liberi da ostacoli a partire da punti seme. Ogni regione diventa un vertice, le regioni che si sovrappongono sono collegate da archi e, all'interno di ogni regione, la traiettoria è rappresentata come una curva liscia, tipicamente una curva di Bézier, che resta nella regione perché vi restano i suoi punti di controllo. Costi come lunghezza del percorso, durata o energia, e limiti di velocità e accelerazione, sono scritti come vincoli convessi. Risolvere il rilassamento e arrotondarlo dà una traiettoria liscia e libera da collisioni senza ricerca basata sul campionamento né post-elaborazione.

L'approccio presuppone una normale geometria euclidea all'interno di ciascun insieme. I robot i cui spazi delle configurazioni si richiudono su se stessi, come i giunti rotoidali continui senza limiti o la direzione di una base mobile, non rientrano direttamente in questa ipotesi. Le estensioni sostituiscono gli insiemi convessi con insiemi geodeticamente convessi su una varietà: insiemi in cui due punti qualsiasi sono uniti da un unico cammino minimo, o geodetica, che resta all'interno dell'insieme. Con questa modifica la stessa formulazione a grafo può pianificare su questi spazi non euclidei. GCS è disponibile nel toolbox Drake.

Perché è importante

I pianificatori basati sul campionamento trovano percorsi ammissibili, ma di solito richiedono una levigatura e non danno alcuna misura di quanto sia buono il percorso. GCS produce traiettorie lisce che rispettano i vincoli in un'unica ottimizzazione, spesso con un certificato di quanto il risultato sia vicino all'ottimo, cosa preziosa per bracci che lavorano ripetutamente in celle fisse come scaffali e postazioni di lavoro.

Applicazioni principali

Pianificazione di traiettorie prive di collisioni per manipolatori in celle di lavoro fisse
Pianificazione per robot con giunti continui o spazi delle configurazioni che si richiudono su se stessi
Pianificazione di appoggi e contatti su regioni convesse del terreno
Traiettorie a tempo minimo per droni in ambienti ingombri
Pianificazione bimanuale e multi-braccio in spazi di lavoro condivisi

In pratica

Un team che mette in servizio un braccio per prelevare da un insieme fisso di contenitori su scaffale genera prima, offline, regioni convesse dello spazio delle configurazioni libero da collisioni, seminando IRIS in configurazioni davanti e dentro ogni contenitore. Richiede tempo, ma va rifatto solo quando la cella cambia. In esecuzione, ogni richiesta di prelievo diventa una query GCS dalla configurazione attuale a un obiettivo in un contenitore. Il solver restituisce una traiettoria liscia che rispetta i limiti di velocità, e il tempo di soluzione cresce con il numero di regioni, quindi il team mantiene l'insieme delle regioni non più grande di quanto serva alla cella. Se un obiettivo cade fuori da ogni regione, la query fallisce, quindi il team aggiunge semi dove manca copertura. Un controllo delle collisioni a breve orizzonte protegge comunque dagli oggetti che non erano nel modello.

Idee sbagliate comuni

GCS richiede che lo spazio libero sia convesso — richiede che lo spazio libero sia coperto da un'unione di regioni convesse, che può approssimare forme complesse
GCS restituisce sempre l'ottimo globale tramite ottimizzazione convessa — il rilassamento è spesso esatto ma non sempre; possono servire un arrotondamento o una risoluzione intera mista
GCS sostituisce del tutto la verifica delle collisioni — garantisce l'assenza di collisioni solo rispetto alle regioni usate, quindi le regioni devono rispecchiare l'ambiente reale

Chi dovrebbe saperlo

Ingegneri di pianificazione del movimento per manipolatori e droni
Ricercatori di pianificazione basata sull'ottimizzazione
Integratori di sistemi di picking e assemblaggio in celle fisse
Studenti di robotica che studiano pianificazione e ottimizzazione convessa

Tecnologie correlate

Drake
Generazione di regioni IRIS (IRIS Region Generation)
Curve di Bézier (Bézier Curves)
Ottimizzazione convessa (Convex Optimization)
Programmazione convessa intera mista (Mixed-Integer Convex Programming)

Termini correlati

Progetti correlati

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

Video

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