imported>Invisigoth67: typo

2026-02-08T07:00:56Z

typo

Neue Seite

[[Datei:Rapidly-exploring Random Tree (RRT) 500x373.gif|mini|Rapidly-exploring Random Tree (RRT) 500x373]]
'''Rapidly-exploring random tree (RRT)''' (dt. etwa ''schnell erkundender zufälliger Baum'') ist ein [[Suchverfahren|Suchalgorithmus]] (und dessen zugrunde liegende [[Baum (Graphentheorie)|Baum-Datenstruktur]]), der hochdimensionale [[Suchraum|Suchräume]] zufällig nach möglichen Pfaden absucht. In der [[Robotik]] werden der Algorithmus und Variationen davon häufig für [[Motion planning]] verwendet, also für die Planung von effizienten Bewegungen, z. B. von Greifarmen.<ref name="Lavalle1998">{{cite journal
| author = Lavalle, S.M.
| year = 1998
| title = Rapidly-exploring random trees: A new tool for path planning
| journal = Computer Science Dept, Iowa State University, Tech. Rep. TR
| pages = 98–11
| url = http://citeseer.ist.psu.edu/311812.html
}}</ref>

== Geschichte ==
Um Pfadplanung für Roboter um Hindernisse herum durchzuführen, wurde relativ früh in der Informatik der [[A*-Algorithmus]] entwickelt (1960er Jahre). Dieser sucht in einem Graphen nach dem kürzesten Pfad von A nach B. RRT erweitert [[A*-Algorithmus|A*]] um zwei wesentliche Elemente: einmal wird ein [[Voronoi-Diagramm|Voronoi bias]] verwendet, der den Problemraum in gleichmäßige Bereiche unterteilt und zweitens kann der Graph an einer beliebigen zufälligen Stelle um neue Knoten erweitert werden. Der Voronoi Bias kommt überwiegend bei geometrischen Pfadplanungs-Problemen zum Einsatz. Das Ziel ist es, den Graphen überall dort zu erweitern wo bisher der Raum nicht gut ausgeleuchtet wurde. Damit ist es möglich, auch Wege zu planen die zunächst durch eine Verengung führen und sich dann aufgabeln wie es bei komplizierten Labyrinthen der Fall ist. Die Möglichkeit an einer beliebigen Stelle neue Nodes hinzuzufügen ist dafür erforderlich.<ref name="rohrmoserimplementierung" />

RRT gilt als eines der effizientesten Verfahren um in Labyrinthen und unter Berücksichtigung von Hindernissen Wege zu planen.

Neben dem ursprünglichen RRT-Algorithmus wurden viele Erweiterungen entwickelt, wovon RRTConnect die bekannteste ist. Obwohl häufig effizient, so schneidet RRT in einigen Fällen sogar schlechter ab als ein klassischer [[Dijkstra-Algorithmus]]<ref name="knispel2013performance" />.

== Voronoi Bias ==
Der Voronoi Bias dient dazu, das Wachstum des RRT-Baumes zu steuern<ref name="urmson2003approaches" /> und wird daher auch als „guided policy search“ oder als „shaping“ bezeichnet. Die Spielfläche wird in gleichmäßige Kästchen unterteilt, von jedem Quadranten die Anzahl der darin enthaltenen [[Knoten (Graphentheorie)|Nodes]] bestimmt und der Bereich mit den wenigsten Nodes wird um einen neuen Node erweitert.

Diese Möglichkeit der Effizienzsteigerung funktioniert leider nicht bei weiteren Problemen aus der Robotik wie z. B. Graspplanning weil dort der Problemraum sich nicht als 2D Spielfeld abbilden lässt, sondern eine höhere Anzahl von Variablen vorliegt. In solchen Fällen lässt sich nicht berechnen welche Bereiche des Spielfeldes eng nebeneinander liegen und welche weit voneinander entfernt sind. Anders ausgedrückt, es mangelt an einem Gütekriterium um die Ausbreitung des RRT-Baumes einzuschätzen.

== DARRT ==
'''Diverse Action Rapidly-exploring Random Tree (DARRT)''' ist ein spezieller RRT-Algorithmus, welcher Motion Primitive mit einem RRT-Solver kombiniert. Damit können komplexe Robotik Aufgaben wie das Greifen eines Objektes oder das Gehen in unwegsamem Gelände bewältigt werden.

=== Beschreibung ===
Ausgangspunkt für die Entwicklung von DARRT war die Frage, wie man einen bestimmten Sollzustand im [[Konfigurationsraum|C-Space]] (Configuration space) erreicht. Normalerweise ist der Problemraum zu groß um ihn mittels [[Brute-Force-Methode]]n durchzuprobieren. In der Vergangenheit ist an dieser Herausforderung jedes Robot-Control-System gescheitert. DARRT löst das Problem dadurch, dass in einem ersten Schritt bestimmte Motion Primitive definiert werden (Diverse Actions). Diese Motion Primitive werden mit Hilfe eines Solvers durchprobiert und zwar in Form eines Graph. Daher auch der Zusatz RRT.

Ein Motion Primitive kann sein „walk forward“, „grasp“ oder „reachpoint“. Das Konzept der Motion Primitive ist abgeleitet von der [[Prozedurale Animation|prozeduralen Animation]], wo so etwas schon länger eingesetzt wird, um Charaktere in Computerspielen realistisch zu animieren. Das RRT-Sampling hingegen basiert auf einer [[Suchverfahren#Suche in Graphen|graphenbasierenden Suche]]. Jeder Node entspricht einem Zustand der [[Physik-Engine]], von dem ausgehend Sub-Knoten generiert werden. Auf diese Weise braucht eine Forward Simulation der Physik-Engine nur für einen kleinen Moment ausgeführt werden, was CPU-Zeit einspart. Ursprünglich entstammt RRT dem pathplanning wird aber bei DARRT eingesetzt, um Instanzen von [[Box2D]], [[Open Dynamics Engine|ODE]] oder anderen Physik-Engines zu sampeln.

Eine Implementierung als ausführbares Programm von DARRT befindet sich als Open-Source auf den Webseiten des ROS-Projektes<ref name="ros2013" />. Das Greifen von Objekten wird hier<ref name="kaelbling2015intelligence" /> erläutert.

'''Erfinder'''

[[Jennifer L. Barry]] ist die Erfinderin von DARRT. Sie hat das Verfahren erstmals im Jahr 2013 in ihrer Dissertation beschrieben<ref name="barry2013thesis" />. Jennifer L. Barry ist bei [[Boston Dynamics]] angestellt<ref name="linkedln" />. Zuvor war sie bei Rethink Robotics und am [[Massachusetts Institute of Technology|MIT]] tätig. Auf dem Server des MIT ist ihre Webseite abrufbar<ref name="mitwebsite" />, wo DARRT und weitere Projekte der Öffentlichkeit vorgestellt werden.

'''Hybridsystem'''

Der Grund warum bei DARRT sowohl Motion Primitive als auch RRT eingesetzt wird, hat damit zu tun, dass beide Verfahren Stärken als auch Schwächen haben, die sich optimal ergänzen. RRT alleine gilt als zu rechenaufwendig, ist aber programmiertechnisch leicht zu implementieren. Motion Primitive benötigen nur wenig CPU-Ressourcen, lassen sich aber nur schwer programmieren, da manueller C++ Sourcecode erstellt werden muss der stark vom konkreten Problem abhängig ist. Kombiniert man jedoch beide Verfahren erhält man einerseits einen Algorithmus der wenig CPU Leistung benötigt gleichzeitig aber sehr mächtig ist.

'''Verallgemeinerung'''

DARRT ist ein sogenannter Multi-Modal-Planner<ref name="jentzsch2015mopl" />. Dieser Begriff entstammt dem [[PDDL]] Umfeld und definiert Macroactions um komplexe hierarchische Probleme zu lösen. Beispielsweise eine Aufgabe, bei dem ein Roboter zuerst einen Schlüssel aus einem Zimmer holen muss, um mit diesem eine Schatztruhe zu öffnen. Solche Probleme lassen sich mit herkömmlichen Verfahren der Künstlichen Intelligenz nicht lösen.

=== Anwendungsmöglichkeiten ===
Der DARRT-Algorithmus wurde bisher auf dem [[Robot Operating System|ROS]] Standardroboter PR2 implementiert. Es gibt dazu Videos<ref name="barry2013thesis" /> die zeigen, wie dieser eine komplexe Aktionsfolge plant und ausführt. Zuerst fährt er zu einem Tisch, führt dann eine Push-Aktion mit einem Teller durch, greift diesen an der Tischkante, fährt mit dem Teller zu einem zweiten Tisch, legt den Teller dort ab und führt eine erneut eine Push Aktion aus. An diesem Ablauf erkennt man wie DARRT in der Praxis arbeitet. Es gibt eine Reihe von vordefinierten Motion Primitiven die hintereinander ausgeführt werden. Die genaueren Parameter sowie die Reihenfolge werden über einen Planner bestimmt.

Weiterhin wurde DARRT im Rahmen des [[Defense Advanced Research Projects Agency|DARPA]] ARM-S Projektes auch für „dexterous grasping“ Aufgaben eingesetzt<ref name="arms" />. Dort bestand die Aufgabe darin, für den „[[Carnegie Mellon University|CMU]] Andy Roboter“ eine Software zu schreiben, die ein Werkzeug von einem Tisch aufnimmt und an einer anderen Stelle wieder ablegt. DARRT wurde verwendet, um den [[Behavior Tree]] on-the-fly zu generieren, der die Aktionsfolge plant.

Weitere Anwendungen in der Praxis waren:
* auf einem Baxter-Roboter der Firma Rethink Robotics im Rahmen eines Workshops<ref name="barry2013workshop" />
* zum Sortieren von Lego-Steinen durch einen PR2 Roboter<ref name="gupta2015using" /> (ein dem DARRT-Algorithmus verwandtes Verfahren)
* Steuerung von Roboterarmen um ein Objekt auf dem Tisch zu verschieben<ref name="king2015nonprehensile" />

== Weblinks ==
{{Commonscat|Rapidly exploring random tree|Rapidly-exploring random tree}}

== Einzelnachweise ==
<references>
<ref name="urmson2003approaches">
{{Literatur
|Autor=Chris Urmson, Raid G. Simmons
|Titel=Approaches for heuristically biasing RRT growth
|Sammelwerk=IROS
|Band=2
|Nummer=
|Datum=2003
|Seiten=1178-1183}}
</ref>
<ref name="rohrmoserimplementierung">
{{Literatur
|Autor=Bertram Rohrmoser, Christopher Parlitz
|Titel=Implementierung einer Bewegungplanung für einen Roboterann Implementation of a path-planning algorithm for a robot arm
|Sammelwerk=Fraunhofer IPA
|Band=
|Nummer=
|Datum=2002
|Seiten=}}
</ref>
<ref name="knispel2013performance">
{{Literatur
|Autor=Lukas KNispel, Radomil Matousek
|Titel=A Performance Comparison of Rapidly-exploring Random Tree and Dijkstra’s Algorithm for Holonomic Robot Path Planning
|Sammelwerk=Institute of Automation and Computer Science, Faculty of Mechanical Engineering, Brno University of Technology
|Band=
|Nummer=
|Datum=2013
|Seiten=}}
</ref>
<ref name="ros2013">
[http://wiki.ros.org/darrt darrt Documentation], ROS.org, 2013, abgerufen am 21. Dezember 2016
</ref>
<ref name="mitwebsite">
[http://people.csail.mit.edu/jbarry/ Personal Website Jennifer Barry, CSAIL, MIT 2013], abgerufen am 21. Dezember 2016
</ref>
<ref name="arms">
Matt Klingensmith, Youtube-Video: DARRT Tool Regrasp (4x) 2014
</ref>
<ref name="linkedln">
[https://www.linkedin.com/in/jennifer-barry-742a0799 Jennifer Barry professional biography, LinkedIn, 2016]
</ref>
<ref name="barry2013workshop">
{{Literatur
|Autor=Jennifer Barry
|Titel=Planning and Manufacturing Robots
|Sammelwerk=NSF Workshop on Robot Planning in the Real World
|Band=
|Nummer=
|Datum=2013
|Seiten=}}
</ref>
<ref name="kaelbling2015intelligence">
{{Literatur
|Autor=[[Leslie Kaelbling]], Thomas Lozano-Perez
|Titel=Intelligence in the Now: Robust Intelligence in Complex Domains
|Sammelwerk=DTIC Document
|Band=
|Nummer=
|Datum=2015
|Seiten=}}
</ref>
<ref name="jentzsch2015mopl">
{{Literatur
|Autor=Sören Jentzsch, Andre Gaschler, Oussama Khatib, Alois Knoll
|Titel=MOPL: A multi-modal path planner for generic manipulation tasks
|Sammelwerk=International Conference on Intelligent Robots and Systems (IROS)
|Band=
|Nummer=
|Datum=2015
|Seiten=6208–6214}}
</ref>
<ref name="barry2013thesis">
{{Literatur
|Autor=Jennifer Lynn Barry
|Titel=Manipulation with diverse actions
|Sammelwerk=MIT
|Band=
|Nummer=
|Datum=2013
|Seiten=}}
</ref>
<ref name="gupta2015using">
{{Literatur
|Autor=Megha Gupta, Jörg Müller, Gaurav Sukhatme
|Titel=Using manipulation primitives for object sorting in cluttered environments
|Sammelwerk=IEEE transactions on Automation Science and Engineering
|Band=12
|Nummer=2
|Datum=2015
|Seiten=608-614}}
</ref>
<ref name="king2015nonprehensile">
{{Literatur
|Autor=Jennifer E. King, Joshua A. Haustein, Siddharta S. Srinivasa, Tamim Asfour
|Titel=Nonprehensile whole arm rearrangement planning on physics manifolds
|Sammelwerk=IEEE International Conference on Robotics and Automation (ICRA)
|Band=
|Nummer=
|Datum=2015
|Seiten=2508–2515}}
</ref>
</references>

[[Kategorie:Robotik]]
[[Kategorie:Suchalgorithmus]]

Rapidly-exploring random tree - Versionsgeschichte

imported>Invisigoth67: typo