Kinodynamic Planning

Auch genannt: kinodynamic motion planning
Kategorie: Planning & manipulation › Motion planning
Schlagwörter: motion-planning, dynamics, sampling-based-planning, trajectory-optimization, state-space

Bewegungsplanung, die sowohl geometrische Beschränkungen wie Kollisionen als auch die Dynamik des Systems berücksichtigt und Stellgrößen über die Zeit statt nur eines kollisionsfreien Pfads bestimmt.

Definition

Kinodynamische Planung (kinodynamic planning) ist Bewegungsplanung, bei der die Lösung zugleich kinematische Beschränkungen, etwa das Vermeiden von Hindernissen und Gelenkgrenzen, und dynamische Beschränkungen, etwa begrenzte Beschleunigungen, Kräfte oder Drehmomente, erfüllen muss. Der Begriff wurde 1993 von Donald, Xavier, Canny und Reif eingeführt. Statt einen geometrischen Pfad im Konfigurationsraum zu suchen und ihn später zeitlich zu parametrieren, sucht ein kinodynamischer Planer eine Dauer und eine Steuerfunktion, deren resultierende Trajektorie, gewonnen durch Integration der Systemdynamik, im Anfangszustand beginnt, im freien Raum bleibt und in einer Zielregion endet.

Die Suche findet daher im Zustandsraum statt, der neben Positionen auch Geschwindigkeiten umfasst und oft die doppelte Dimension des Konfigurationsraums hat. Die Hauptschwierigkeit ist, dass zwei benachbarte Zustände im Allgemeinen nicht durch eine gerade Linie verbunden werden können: Ihre Verbindung erfordert die Lösung eines Zweipunkt-Randwertproblems unter der Dynamik, was für einfache Systeme wie Doppelintegratoren oder Dubins-Fahrzeuge leicht, im Allgemeinen aber schwer ist. Sampling-basierte Planer wie das von LaValle und Kuffner eingeführte kinodynamische RRT umgehen dies, indem sie einen Baum vorwärts wachsen lassen: Sie wählen einen Knoten, wenden gesampelte oder gewählte Stellgrößen für kurze Zeit an und behalten die resultierenden Zustände. Spätere Verfahren wie SST bieten asymptotische Beinahe-Optimalität, ohne eine Steuerungsfunktion zu benötigen.

Andere Verfahrensfamilien gehen dasselbe Problem anders an. Suchbasierte Planer verwenden ein Gitter vorberechneter Bewegungsprimitive, von denen jedes dynamisch ausführbar ist. Methoden der Trajektorienoptimierung, darunter direkte Kollokation und Shooting, behandeln Stellgrößen und Zustände als Entscheidungsvariablen und lösen ein beschränktes nichtlineares Programm, das lokal schnell konvergiert, aber in lokalen Minima hängen bleiben kann. Praktische Systeme kombinieren oft beides: Eine Sampling- oder Suchstufe findet eine ausführbare Trajektorie, und eine Optimierung verfeinert sie anschließend. Wenn die Dynamik unsicher ist, wie beim Schieben von Objekten, können Planer gelernte oder Residualmodelle des Systems verwenden und mit Stellgrößen im offenen Regelkreis planen, die dann durch Rückführung korrigiert werden.

Warum es wichtig ist

Schnelle oder schwere Roboter, Autos, Drohnen und geschobene Objekte können nicht beliebigen geometrischen Pfaden folgen: Ein Pfad, der Impuls oder Aktuatorgrenzen ignoriert, ist unter Umständen nicht ausführbar. Kinodynamische Planung erzeugt Trajektorien, denen das System tatsächlich folgen kann, was am wichtigsten ist, wenn sich der Roboter schnell bewegt oder nur begrenzte Stellautorität hat.

Wichtige Anwendungen

Trajektorienplanung für Autos und andere nichtholonome Fahrzeuge
Planung aggressiver Flüge für Drohnen und Starrflügler
Nicht greifende Manipulation wie die Planung von Schiebefolgen
Schnelle Armbewegungen nahe Drehmoment- und Geschwindigkeitsgrenzen
Bewegungsplanung für Lauf- und humanoide Roboter mit Kontaktdynamik
Manövrieren von Raumfahrzeugen und Unterwasserfahrzeugen

In der Praxis

Ein Roboterarm soll eine Kiste über einen Tisch in eine Zielregion schieben und dabei einem Hindernis ausweichen, ohne sie zu greifen. Das Team modelliert die Bewegung der Kiste als Funktion von Schiebeparametern wie Kontaktpunkt, Richtung und Dauer, mithilfe eines analytischen Schiebemodells, das durch ein gelerntes Residuum korrigiert wird. Ein kinodynamisches RRT sampelt Schiebeaktionen ausgehend vom aktuellen Kistenzustand, propagiert jede durch das Modell und fügt die resultierenden Kistenposen dem Baum hinzu, wobei Schübe verworfen werden, die mit dem Hindernis kollidieren würden. Sobald ein Ast die Zielregion erreicht, wird die Schiebefolge ausgeführt, und die Kistenpose wird nach jedem Schub neu beobachtet, damit der Planer vom tatsächlichen Zustand aus neu planen kann, falls das Modell falsch lag.

Häufige Missverständnisse

Kinodynamische Planung ist geometrische Planung mit anschließender Zeitparametrierung — entkoppelte Pipelines können Pfade erzeugen, denen keine dynamisch ausführbare Trajektorie folgen kann, während kinodynamische Planer die Dynamik schon während der Suche berücksichtigen
Jeder Sampling-basierte Planer lässt sich durch Austausch der Distanzmetrik kinodynamisch machen — die Verbindung zweier Zustände erfordert im Allgemeinen die Lösung eines Randwertproblems oder die Vorwärtspropagation von Stellgrößen, nicht das Ziehen einer geraden Linie
Ein kinodynamischer Plan kann im offenen Regelkreis ausgeführt werden — Modellfehler und Störungen summieren sich, daher wird der Plan normalerweise mit einem Rückführungsregler verfolgt oder neu geplant

Wer das wissen sollte

Ingenieure für Bewegungsplanung bei Fahrzeugen, Drohnen und Armen
Manipulationsforschende, die am Schieben und an anderen dynamischen Aufgaben arbeiten
Planungsingenieure für autonomes Fahren
Robotikstudierende, die Planung jenseits des Konfigurationsraums lernen

Videos

6.8210 Spring 2024 Lecture 18: Sampling-based (kinodynamic) motion planning: underactuated

Open Source Robotics