Rapidly-exploring random tree

Auch genannt: RRT
Kategorie: Planning & manipulation › Motion planning
Schlagwörter: motion-planning, sampling-based-planning, path-planning, kinodynamic-planning, collision-avoidance

Ein stichprobenbasierter Bewegungsplaner, der vom Startzustand aus einen Baum wachsen lässt, indem er wiederholt einen zufälligen Zustand zieht und den nächstgelegenen Baumknoten darauf zu erweitert, und so große Räume schnell erkundet.

Definition

Der Rapidly-exploring Random Tree (RRT) ist ein stichprobenbasierter Algorithmus, um einen zulässigen Pfad von einem Startzustand zu einer Zielregion zu finden. Er wurde 1998 von Steven LaValle eingeführt. Der Algorithmus lässt einen Baum mit dem Start als Wurzel wachsen: In jeder Iteration zieht er einen zufälligen Zustand im Konfigurations- oder Zustandsraum, findet den nächstgelegenen Knoten im Baum und erweitert von diesem Knoten aus ein kurzes Stück in Richtung der Stichprobe. Ist die Erweiterung kollisionsfrei, wird der neue Zustand dem Baum hinzugefügt. Die Suche endet, wenn der Baum die Zielregion erreicht, und der Pfad wird über den Elternknoten jedes Knotens zurückgelesen.

Die entscheidende Eigenschaft ist der Voronoi-Bias. Knoten am Rand des Baums haben die größten Voronoi-Regionen und sind daher am wahrscheinlichsten einer zufälligen Stichprobe am nächsten, sodass der Baum in unerforschten Raum gezogen wird, statt bereits abgedeckte Regionen aufzufüllen. Das macht RRT in hochdimensionalen Räumen wie dem Gelenkraum eines Roboterarms wirksam. RRT ist probabilistisch vollständig: Wenn eine Lösung existiert, nähert sich die Wahrscheinlichkeit, sie zu finden, mit wachsender Stichprobenzahl eins. Übliche Verbesserungen sind Goal Biasing, bei dem ein Teil der Stichproben am Ziel gezogen wird, und RRT-Connect, das Bäume sowohl vom Start als auch vom Ziel wachsen lässt und versucht, sie gierig zu verbinden.

Da der Erweiterungsschritt nur eine Möglichkeit braucht, sich von einem Zustand auf einen anderen zuzubewegen, beherrscht RRT auch kinodynamische Planung, bei der sich der Roboter nicht auf Geraden durch seinen Zustandsraum bewegen kann. Der Erweiterungsschritt wendet dann abgetastete oder optimierte Steuergrößen an und simuliert die Dynamik vorwärts, wie im kinodynamischen RRT von LaValle und Kuffner, oder verkettet vorab berechnete Bewegungsprimitive. Das macht ihn nützlich für Fahrzeuge, Laufroboter und kontaktreiche Manipulation, bei denen Distanzmaß und Erweiterungsschritt um die Dynamik herum entworfen werden müssen. Die Pfade von RRT sind typischerweise zackig und nicht optimal, und weitere Stichproben verbessern einen einmal gefundenen Pfad nicht. RRT\ fügt einen Schritt zur Wahl des Elternknotens und einen Rewiring-Schritt hinzu, der benachbarte Knoten neu verbindet, wann immer ein günstigerer Weg existiert; das macht ihn asymptotisch optimal, auf Kosten von mehr Rechenaufwand pro Stichprobe. Wenn schnell ein zulässiger Pfad benötigt wird, bleibt einfaches RRT oder RRT-Connect mit anschließendem Shortcutting und Glätten eine gängige Wahl.

Warum es wichtig ist

RRT hat die Bewegungsplanung für Roboter mit vielen Freiheitsgraden und für Systeme mit Dynamik praxistauglich gemacht und ist weiterhin ein Standardplaner in Bibliotheken wie OMPL und MoveIt. Viele spätere Planer, darunter RRT*, bauen auf seiner Struktur auf.

Wichtige Anwendungen

Bewegungsplanung für Manipulatoren in vollgestellten Arbeitsräumen
Kinodynamische Planung für Autos, Drohnen und Laufroboter
Planung kontaktreicher Manipulation mit eigenen Distanzmaßen
Planung über Graphen von Bewegungsprimitiven für die Fortbewegung
Exploration unbekannter Umgebungen

In der Praxis

Ein Team, das MoveIt für einen siebenachsigen Arm konfiguriert, der Artikel aus Regalen nimmt, verwendet RRT-Connect aus OMPL als Standardplaner. Die Kollisionsprüfung nutzt das Robotermodell und einen Octree, der aus einer Tiefenkamera aufgebaut wird. Das Team setzt das Planungszeitlimit und die Schrittweite der Erweiterung im Verhältnis zum Freiraum der Regalöffnungen und bearbeitet dann jeden Pfad mit Shortcutting und Zeitparametrierung nach, damit sich der Arm gleichmäßig bewegt. Wenn die Planung Schwierigkeiten hat, tief in enge Regalfächer zu reichen, erhöht es das Goal Biasing oder probiert einen Planer mit besserem Verhalten in engen Durchgängen, und für wiederholte Anfragen in einer statischen Zelle zieht es stattdessen eine probabilistische Roadmap in Betracht.

Häufige Missverständnisse

RRT findet den kürzesten Pfad — er findet einen zulässigen Pfad; für gute Pfadqualität braucht man RRT* oder Nachbearbeitung
RRT findet garantiert innerhalb einer festen Zeit einen Pfad — er ist probabilistisch vollständig, findet also einen Pfad mit einer Wahrscheinlichkeit, die sich bei fortgesetzter Stichprobenziehung eins nähert, und enge Durchgänge können lange dauern
RRT* ist immer die bessere Wahl — er verbessert Pfade mit der Zeit, ist aber langsamer bis zur ersten Lösung; wenn Geschwindigkeit zählt, wird oft RRT-Connect mit Glättung bevorzugt

Wer das wissen sollte

Ingenieure für Bewegungsplanung
Entwickler von Manipulations- und mobilen Robotern, die MoveIt oder OMPL verwenden
Planungsingenieure für autonome Fahrzeuge und Drohnen
Robotikstudierende

Videos

Motion Planning: Rapidly Exploring Random Trees (RRT): Algorithm Implementation Step by Step!: VDEngineering

Wikipedia

Rapidly-exploring random tree

Open Source Robotics