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

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

Lizenzen

Open Access
Paper: CC BY 4.0

Alles Folgende stützt sich auf das vollständige Paper unter seiner Lizenz CC BY 4.0; die Abbildung wird mit Nennung der Autoren gezeigt.

Kurz gesagt

Behandelt Gelenkräume mit Umlauf (mobile Basen, kontinuierliche Gelenke) als flache Mannigfaltigkeiten, sodass der GCS-Kürzeste-Wege-Planer weiterhin global optimale, kollisionsfreie Pfade liefert.

Warum es wichtig ist

Mobile Manipulatoren und Arme mit unbegrenzten Basisgelenken können nun einen Planer nutzen, der zertifiziert, dass jeder Punkt der Trajektorie kollisionsfrei ist, und der bei exakter Lösung innerhalb des zertifizierten freien Raums optimal ist. Das Paper beweist außerdem, dass positive Krümmung (zum Beispiel SO(3)-Kugelgelenke oder frei schwebende Körper) die Konvexität zerstört, und markiert damit, wohin dieser Ansatz nicht reicht.

Problem

Der GCS-Planer von Marcucci et al. findet kollisionsfreie, global optimale Pfade über eine Zerlegung des freien Konfigurationsraums in konvexe Mengen, jedoch nur für euklidische Konfigurationsräume. Eine mobile Basis, die sich volle 360° drehen kann, oder ein kontinuierliches Drehgelenk läuft in sich zurück, sodass sein Konfigurationsraum nicht euklidisch ist. Künstliche Gelenkgrenzen hinzuzufügen oder Winkel als unbeschränkte reelle Zahlen zu behandeln, macht entweder das Optimum unzulässig oder erfordert Vorwissen über die Lösung und viele duplizierte Mengen.

Lösungsansatz

Die Autoren modellieren den Konfigurationsraum als Riemannsche Mannigfaltigkeit und definieren einen Graph of Geodesically-Convex Sets (GGCS), für den sie beweisen, dass er die Garantien des gewöhnlichen GCS behält. Für flache Mannigfaltigkeiten (Krümmung null), die jeden aus 1-DoF-Gelenken und einer SE(2)-Basis aufgebauten Roboter abdecken, wird jede Menge über eine lokal isometrische Karte in den euklidischen Raum abgebildet, und das Problem reduziert sich auf ein gewöhnliches gemischt-ganzzahliges konvexes GCS-Problem mit affinen Übergangsnebenbedingungen. Regionen werden mit IRIS erzeugt und pro Gelenk durch den Konvexitätsradius begrenzt, und stückweise Bézier-Trajektorien mit Stetigkeitsnebenbedingungen lassen sich übertragen.

Wichtigste Erkenntnisse

SE(2), jede 1-D-Mannigfaltigkeit und Produkte flacher Mannigfaltigkeiten sind flach, sodass Roboter aus Gelenken mit einem DoF und einer mobilen Basis zur Methode passen; Kugelgelenke mit 3 DoF nicht
Wird jede IRIS-Region pro Gelenk durch den Konvexitätsradius begrenzt, ist garantiert, dass die Region bei der Rückabbildung auf die Mannigfaltigkeit geodätisch konvex bleibt
Auf einem flachen Raum mit global ausgerichteten Koordinaten sind die Übergangsabbildungen affin, sodass Endpunkt- und Ableitungsstetigkeits-Nebenbedingungen konvex bleiben
Schon ein einziger Punkt positiver Krümmung macht die Riemannsche Abstandsfunktion in jeder Umgebung dieses Punktes nichtkonvex (Theorem 5)

Hauptergebnisse

Punktroboter auf einem Torus: optimaler Pfad mit Umlauf in 0,79 s; planarer 5-Gelenk-Arm mit kontinuierlichen Gelenken: plant in 5,36 s und 4,63 s, wobei einer der Pfade das mittlere Gelenk um mehr als 360° dreht
Planarer Arm: Relax-and-Round-Pfade der Länge 7,749 und 8,448 gegenüber Branch-and-Bound-Optima von 7,274 und 8,008
KUKA iiwa mit kontinuierlichem Basisgelenk (Simulation): 14 Bewegungen zum Sortieren von Tassen mit 18 konvexen Regionen, im Mittel 25,75 s pro Bewegung (Bereich 4,63–50,30 s)
PR2 (Simulation, 15-D-Konfigurationsraum), 7 Aufgaben zum Greifen in Regale: GGCS-Pfade waren in jedem Fall kollisionsfrei, z. B. 1M→4M Länge 3,875 gegenüber 14,554 bei PRM; Drake-Trajopt und PRM+Trajopt lieferten teils kürzere Pfade, die jedoch leicht kollidierten
Die Online-Planung für den PR2 dauerte 25,51–66,15 s für GGCS-Planner, gegenüber 0,49–0,54 s für PRM, 2,26–15,23 s für Drake-Trajopt und 11,61–40,10 s für PRM+Trajopt
Offline-Vorbereitung für den PR2: eine IRIS-Region dauerte im Mittel 30,20 s (8,56–75,42 s), alle Regionen parallel 156,63 s; der Aufbau des PRM mit 100.000 Stichproben dauerte 124,39 s

Einschränkungen

Die Autoren geben an, dass die Methode keine nichtkonvexen Kosten und Nebenbedingungen wie nichtlineare Dynamik und geschlossene kinematische Ketten verarbeiten kann, ebenso wenig Kugelgelenke
Räume positiver Krümmung wie SO(3) sind ausgeschlossen, weil die Abstandsfunktion dort nachweislich nichtkonvex ist
Optimalität gilt nur innerhalb des von den Regionen abgedeckten 'zertifizierten' freien Raums; die Leistung hängt stark von der Wahl der Regionen ab, und beim PR2 wurden einige Zwischenregionen von Hand hinzugefügt
Die Online-Planungszeiten für den PR2 (25,51–66,15 s) waren höher als bei jeder verglichenen Baseline
Alle Roboterergebnisse stammen aus der Simulation; die Autoren nennen zweiarmige Planung mit impliziten kinematischen Nebenbedingungen und Planung durch Kontakt als künftige Arbeit

Wirkung auf das Fachgebiet

Finalist für den RSS 2023 Best Paper Award, mit 44 Zitationen. Die Autoren veröffentlichen interaktive Aufzeichnungen jeder Trajektorie auf einer Ergebnis-Website.

Zusammenfassung

Die Berechnung optimaler, kollisionsfreier Trajektorien für hochdimensionale Systeme ist ein anspruchsvolles Problem. Abtastbasierte Planer haben mit der Dimensionalität zu kämpfen, während Trajektorienoptimierer aufgrund inhärenter Nichtkonvexitäten in der Optimierungslandschaft in lokalen Minima stecken bleiben können. Der Einsatz gemischt-ganzzahliger Programmierung, um diese Nichtkonvexitäten abzubilden und global optimale Trajektorien zu finden, hat sich in jüngster Zeit als sehr vielversprechend erwiesen, teilweise dank enger konvexer Relaxationen und effizienter Approximationsstrategien, die die Laufzeiten stark verkürzen. Diese Ansätze waren bisher auf euklidische Konfigurationsräume beschränkt, was ihren Einsatz mit mobilen Basen oder kontinuierlichen Drehgelenken ausschloss. In diesem Paper behandeln wir solche Szenarien, indem wir Konfigurationsräume als Riemannsche Mannigfaltigkeiten modellieren, und wir beschreiben ein Reduktionsverfahren für den Fall verschwindender Krümmung auf ein gemischt-ganzzahliges konvexes Optimierungsproblem. Wir demonstrieren unsere Ergebnisse auf verschiedenen Roboterplattformen, unter anderem durch die Erzeugung effizienter, kollisionsfreier Trajektorien für einen PR2, einen zweiarmigen mobilen Manipulator.

Open Source Robotics