RRT*

Auch genannt: RRT star, RRT-star, optimal RRT
Kategorie: Planning & manipulation › Motion planning
Schlagwörter: motion-planning, sampling-based-planning, path-planning, optimization, manipulation

Eine asymptotisch optimale Version des Planers Rapidly-exploring Random Tree, die ihren Baum beim Wachsen neu verdrahtet, sodass sich der zurückgegebene Pfad stetig in Richtung des Pfads mit den geringsten Kosten verbessert.

Definition

RRT\ (gesprochen „RRT star“) ist ein samplingbasierter Algorithmus der Bewegungsplanung, der kollisionsfreie Pfade findet und bei genügend Samples gegen einen optimalen Pfad konvergiert. Er wurde 2011 von Sertac Karaman und Emilio Frazzoli als Erweiterung des 1998 von Steven LaValle vorgeschlagenen Algorithmus Rapidly-exploring Random Tree (RRT) vorgestellt.

Der ursprüngliche RRT lässt von der Startkonfiguration aus einen Baum wachsen, indem er wiederholt einen zufälligen Punkt im Konfigurationsraum sampelt, den nächstgelegenen Knoten im Baum findet und einen kurzen Schritt in Richtung des Samples erweitert, falls diese Bewegung kollisionsfrei ist. RRT findet machbare Pfade schnell, auch in hochdimensionalen Räumen wie dem Gelenkraum eines Roboterarms, aber seine Pfade sind meist zackig und weit vom kürzesten entfernt, und sie verbessern sich nicht, wenn mehr Samples hinzukommen.

RRT* ändert zwei Dinge. Wird ein neuer Knoten hinzugefügt, prüft er alle Baumknoten innerhalb eines Nachbarschaftsradius und verbindet sich mit demjenigen, der die geringsten Kosten vom Start ergibt, nicht einfach mit dem nächstgelegenen. Dann verdrahtet er neu (Rewiring): Ergibt für einen Nachbarn der Weg über den neuen Knoten einen günstigeren Pfad, wird der Elternknoten dieses Nachbarn geändert. Karaman und Frazzoli zeigten, dass bei einem Nachbarschaftsradius, der mit wachsendem Baum angemessen schrumpft, die Kosten der Lösung gegen das Optimum konvergieren, wenn die Zahl der Samples gegen unendlich geht, eine Eigenschaft, die asymptotische Optimalität heißt.

Der Preis ist zusätzlicher Rechenaufwand pro Sample, daher findet RRT eine erste Lösung langsamer als RRT. Varianten wie Informed RRT und BIT* bündeln das Sampling, um die Konvergenz zu beschleunigen.

Warum es wichtig ist

Viele Roboter brauchen nicht irgendeinen Pfad, sondern einen guten: kürzer, glatter oder energiesparender. RRT* gibt samplingbasierten Planern, die auf hochdimensionale Konfigurationsräume skalieren, einen fundierten Weg zu Pfadqualität und ist eine Standard-Baseline in der Forschung und Software zur Bewegungsplanung.

Wichtige Anwendungen

Kollisionsfreie Bewegungsplanung für Roboterarme in vollgestellten Arbeitsräumen
Globale Pfadplanung für mobile Roboter und Drohnen
Planung in hochdimensionalen Konfigurationsräumen, in denen Gittersuche unpraktikabel ist
Erzeugung von Referenzpfaden für die Trajektorienoptimierung

In der Praxis

Robotikteams nutzen RRT meist über eine Planungsbibliothek, statt ihn selbst zu schreiben. Die Open Motion Planning Library (OMPL), die MoveIt für Roboterarme verwendet, enthält RRT und mehrere seiner Varianten neben RRT, RRT-Connect und PRM. Ein übliches Muster ist, RRT mit festem Zeitbudget laufen zu lassen, den besten bis zum Ablauf der Zeit gefundenen Pfad zu nehmen und ihn dann abzukürzen und zu glätten, bevor er in eine zeitparametrierte Trajektorie umgewandelt wird. Für mobile Roboter und Drohnen setzen Teams RRT auch auf einer 2D- oder 3D-Belegungskarte als globalen Planer ein und wählen Planungszeit und Schrittweite so, dass Pfadqualität gegen Reaktionszeit abgewogen wird.

Häufige Missverständnisse

RRT* liefert den optimalen Pfad — er ist asymptotisch optimal, daher nähern sich die Pfadkosten dem Optimum erst, wenn die Zahl der Samples unbegrenzt wächst
RRT*-Pfade sind glatt — sie sind stückweise linear und brauchen vor der Ausführung meist Abkürzung und Glättung
RRT* ist immer besser als RRT — wenn nur schnell ein machbarer Pfad gebraucht wird, ist einfaches RRT oder RRT-Connect oft die bessere Wahl

Wer das wissen sollte

Ingenieure für Bewegungsplanung
Softwareentwickler für Roboterarme und Manipulation
Entwickler autonomer Drohnen und mobiler Roboter
Robotikstudierende, die Planungsalgorithmen lernen

Videos

Path Planning with A* and RRT | Autonomous Navigation, Part 4: MATLAB

Open Source Robotics