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

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

Licenze

• Open access
• Articolo: CC BY 4.0

Tutto ciò che segue si basa sull'articolo completo secondo la sua licenza CC BY 4.0; la figura è riportata citando gli autori.

In breve

Tratta gli spazi dei giunti che si richiudono su se stessi (basi mobili, giunti continui) come varietà piatte, così il pianificatore di cammini minimi GCS fornisce ancora percorsi globalmente ottimali e privi di collisioni.

Perché è importante

I manipolatori mobili e i bracci con giunti di base senza limiti possono ora usare un pianificatore che certifica che ogni punto della traiettoria è privo di collisioni e, se risolto in modo esatto, che è ottimale entro lo spazio libero certificato. L'articolo dimostra anche che la curvatura positiva (per esempio giunti sferici SO(3) o corpi in volo libero) rompe la convessità, il che segna dove questo approccio non può arrivare.

Problema

Il pianificatore GCS di Marcucci et al. trova percorsi privi di collisioni e globalmente ottimali tramite una decomposizione dello spazio delle configurazioni libero in insiemi convessi, ma solo per spazi delle configurazioni euclidei. Una base mobile che può ruotare di 360° completi, o un giunto rotoidale continuo, si richiude su se stesso, quindi il suo spazio delle configurazioni non è euclideo. Aggiungere limiti artificiali ai giunti o trattare gli angoli come reali illimitati rende l'ottimo irraggiungibile oppure richiede di conoscere in anticipo la risposta e molti insiemi duplicati.

Soluzione proposta

Gli autori modellano lo spazio delle configurazioni come una varietà riemanniana e definiscono un Graph of Geodesically-Convex Sets (GGCS, grafo di insiemi geodeticamente convessi), dimostrando che conserva le garanzie del GCS ordinario. Per le varietà piatte (a curvatura nulla), che coprono qualsiasi robot costruito con giunti a 1 DoF più una base SE(2), ogni insieme viene portato nello spazio euclideo tramite una carta di isometria locale, e il problema si riduce a un problema GCS standard di ottimizzazione convessa intera mista con vincoli di transizione affini. Le regioni vengono fatte crescere con IRIS e limitate giunto per giunto dal raggio di convessità, e le traiettorie di Bézier a tratti con vincoli di continuità restano valide.

Idee chiave

• SE(2), ogni varietà di dimensione 1 e i prodotti di varietà piatte sono piatti, quindi i robot composti da giunti a un solo DoF e una base mobile rientrano nel metodo; i giunti sferici a 3 DoF no
• Limitare ogni regione IRIS, giunto per giunto, con il raggio di convessità garantisce che la regione resti geodeticamente convessa quando viene riportata sulla varietà
• Su uno spazio piatto con coordinate allineate globalmente le mappe di transizione sono affini, quindi i vincoli di raccordo degli estremi e di continuità delle derivate restano convessi
• Basta un solo punto a curvatura positiva perché la funzione distanza riemanniana sia non convessa in ogni intorno di quel punto (Teorema 5)

Risultati principali

• Robot puntiforme su un toro: percorso ottimale con giro completo in 0,79 s; braccio planare a 5 giunti con giunti continui: pianifica in 5,36 s e 4,63 s, e uno dei piani ruota il giunto centrale di oltre 360°
• Braccio planare: percorsi relax-and-round (rilassa e arrotonda) di lunghezza 7,749 e 8,448 contro ottimi branch-and-bound di 7,274 e 8,008
• KUKA iiwa con un giunto di base continuo (simulazione): 14 movimenti di smistamento di tazze usando 18 regioni convesse, con una media di 25,75 s per movimento (intervallo da 4,63 a 50,30 s)
• PR2 (simulazione, spazio delle configurazioni a 15 dimensioni), 7 compiti di raggiungimento negli scaffali: i percorsi GGCS sono risultati privi di collisioni in tutti i casi, ad es. 1M→4M con lunghezza 3,875 contro 14,554 del PRM; Drake-Trajopt e PRM+Trajopt hanno talvolta dato percorsi più brevi, ma con lievi collisioni
• La pianificazione online del PR2 ha richiesto da 25,51 a 66,15 s per GGCS-Planner, contro 0,49-0,54 s del PRM, 2,26-15,23 s di Drake-Trajopt e 11,61-40,10 s di PRM+Trajopt
• Preparazione offline del PR2: una regione IRIS ha richiesto in media 30,20 s (da 8,56 a 75,42 s), tutte le regioni 156,63 s in parallelo; costruire il PRM da 100.000 campioni ha richiesto 124,39 s

Limiti

• Gli autori affermano che il metodo non può gestire costi e vincoli non convessi, come la dinamica non lineare e le catene cinematiche chiuse, né i giunti sferici
• Gli spazi a curvatura positiva come SO(3) sono esclusi, perché lì la funzione distanza è dimostrabilmente non convessa
• L'ottimalità vale solo entro lo spazio libero 'certificato' coperto dalle regioni; le prestazioni dipendono fortemente dalla scelta delle regioni, e per il PR2 alcune regioni intermedie sono state aggiunte a mano
• I tempi di pianificazione online del PR2 (da 25,51 a 66,15 s) sono stati superiori a quelli di tutte le baseline confrontate
• Tutti i risultati sui robot sono in simulazione; gli autori indicano come lavoro futuro la pianificazione bimanuale con vincoli cinematici impliciti e la pianificazione attraverso il contatto

Impatto sul settore

Finalista del RSS 2023 Best Paper Award, con 44 citazioni. Gli autori pubblicano registrazioni interattive di ogni traiettoria su un sito web dei risultati.

Abstract

Calcolare traiettorie ottimali e prive di collisioni per sistemi ad alta dimensionalità è un problema impegnativo. I pianificatori basati sul campionamento faticano con la dimensionalità, mentre gli ottimizzatori di traiettoria possono restare bloccati in minimi locali a causa delle non convessità intrinseche del paesaggio di ottimizzazione. L'uso della programmazione intera mista per incapsulare queste non convessità e trovare traiettorie globalmente ottimali si è dimostrato di recente molto promettente, grazie in parte a rilassamenti convessi stretti e a strategie di approssimazione efficienti che riducono notevolmente i tempi di esecuzione. Questi approcci erano finora limitati a spazi delle configurazioni euclidei, il che ne precludeva l'uso con basi mobili o giunti rotoidali continui. In questo articolo affrontiamo tali scenari modellando gli spazi delle configurazioni come varietà riemanniane, e descriviamo una procedura di riduzione, per il caso a curvatura nulla, a un problema di ottimizzazione convessa intera mista. Dimostriamo i nostri risultati su varie piattaforme robotiche, tra cui la generazione di traiettorie efficienti e prive di collisioni per un manipolatore mobile bimanuale PR2.

Link

• 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
• Pagina del progetto: https://ggcs-anonymous-submission.github.io/