Graph of Convex Sets

Auch genannt: GCS, graphs of convex sets
Kategorie: Planning & manipulation › Trajectory optimisation
Schlagwörter: motion-planning, convex-optimization, trajectory-optimization, configuration-space, manipulation

Eine Formulierung der Bewegungsplanung, die konvexe Regionen des freien Raums in einem Graphen verknüpft und durch konvexe Optimierung einen glatten, kollisionsfreien Pfad durch sie findet.

Definition

Ein Graph konvexer Mengen (Graph of Convex Sets, GCS) ist ein Graph, in dem jeder Knoten eine konvexe Menge ist und der in jeder Menge gewählte Punkt eine kontinuierliche Entscheidungsvariable. Kanten verbinden Mengen, zwischen denen man wechseln kann, und Kantenkosten und Nebenbedingungen sind konvexe Funktionen der Punkte an beiden Enden. Den günstigsten Weg durch einen solchen Graphen zu finden, kombiniert eine diskrete Wahl, welche Mengen durchquert werden, mit einer kontinuierlichen, wohin man in jeder Menge geht. Tobia Marcucci, Russ Tedrake und Kollegen formulierten dieses Kürzeste-Wege-Problem und zeigten, dass es, obwohl im Allgemeinen ein gemischt-ganzzahliges Problem, eine starke konvexe Relaxation hat, die oft scharf oder nahezu scharf ist.

Für die Bewegungsplanung wird der kollisionsfreie Teil des Konfigurationsraums zuerst mit einer Sammlung konvexer Regionen überdeckt, zum Beispiel mit dem IRIS-Algorithmus, der von Startpunkten aus große hindernisfreie Polytope wachsen lässt. Jede Region wird zu einem Knoten, überlappende Regionen werden durch Kanten verbunden, und innerhalb jeder Region wird die Trajektorie als glatte Kurve dargestellt, typischerweise als Bézier-Kurve, die in der Region bleibt, weil ihre Kontrollpunkte es tun. Kosten wie Pfadlänge, Dauer oder Energie sowie Grenzen für Geschwindigkeit und Beschleunigung werden als konvexe Nebenbedingungen geschrieben. Das Lösen der Relaxation und anschließendes Runden liefert eine glatte, kollisionsfreie Trajektorie ohne stichprobenbasierte Suche oder Nachbearbeitung.

Der Ansatz setzt innerhalb jeder Menge gewöhnliche euklidische Geometrie voraus. Roboter, deren Konfigurationsräume sich umschlagen, etwa kontinuierliche Drehgelenke ohne Anschläge oder der Kurswinkel einer mobilen Basis, passen nicht direkt zu dieser Annahme. Erweiterungen ersetzen konvexe Mengen durch geodätisch konvexe Mengen auf einer Mannigfaltigkeit: Mengen, in denen je zwei Punkte durch einen eindeutigen kürzesten Weg, eine Geodäte, verbunden sind, der innerhalb der Menge bleibt. Mit dieser Änderung kann dieselbe Graphformulierung auf solchen nichteuklidischen Räumen planen. GCS ist in der Drake-Toolbox verfügbar.

Warum es wichtig ist

Stichprobenbasierte Planer finden zulässige Pfade, brauchen aber meist eine Glättung und liefern kein Maß dafür, wie gut der Pfad ist. GCS erzeugt glatte, nebenbedingungskonforme Trajektorien in einer einzigen Optimierung, oft mit einem Nachweis, wie nah das Ergebnis am Optimum liegt, was für Arme wertvoll ist, die wiederholt in festen Zellen wie Regalen und Arbeitsstationen arbeiten.

Wichtige Anwendungen

Kollisionsfreie Trajektorienplanung für Manipulatoren in festen Arbeitszellen
Planung für Roboter mit kontinuierlichen Gelenken oder sich umschlagenden Konfigurationsräumen
Schritt- und Kontaktplanung über konvexen Geländeregionen
Zeitminimale Trajektorien für Drohnen durch verstellte Umgebungen
Zweiarm- und Mehrarmplanung in gemeinsamen Arbeitsräumen

In der Praxis

Ein Team, das einen Arm zum Kommissionieren aus einem festen Satz von Regalfächern einsetzt, erzeugt zuerst offline konvexe Regionen des kollisionsfreien Konfigurationsraums und setzt IRIS-Startpunkte an Konfigurationen vor und in jedem Fach. Das kostet Zeit, muss aber nur wiederholt werden, wenn sich die Zelle ändert. Zur Laufzeit wird jede Kommissionieranfrage zu einer GCS-Anfrage von der aktuellen Konfiguration zu einem Ziel in einem Fach. Der Löser liefert eine glatte Trajektorie unter Einhaltung der Geschwindigkeitsgrenzen, und die Lösungszeit wächst mit der Zahl der Regionen, daher hält das Team die Regionenmenge nicht größer, als die Zelle erfordert. Liegt ein Ziel außerhalb aller Regionen, scheitert die Anfrage, daher fügt das Team dort Startpunkte hinzu, wo Abdeckung fehlt. Eine Kollisionsprüfung mit kurzem Horizont schützt weiterhin vor Objekten, die nicht im Modell waren.

Häufige Missverständnisse

GCS verlangt, dass der freie Raum konvex ist — es verlangt, dass der freie Raum durch eine Vereinigung konvexer Regionen überdeckt wird, die komplexe Formen annähern kann
GCS liefert durch konvexe Optimierung immer das globale Optimum — die Relaxation ist oft scharf, aber nicht immer; Runden oder eine gemischt-ganzzahlige Lösung können nötig sein
GCS ersetzt die Kollisionsprüfung vollständig — es garantiert Kollisionsfreiheit nur bezüglich der verwendeten Regionen, daher müssen die Regionen die reale Umgebung widerspiegeln

Wer das wissen sollte

Ingenieure für Bewegungsplanung von Manipulatoren und Drohnen
Forschende in optimierungsbasierter Planung
Integratoren von Kommissionier- und Montagesystemen in festen Zellen
Robotikstudierende, die Planung und konvexe Optimierung lernen

Videos

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

Open Source Robotics