Zum Inhalt springen

„Rapidly-exploring random tree“ – Versionsunterschied

aus Wikipedia, der freien Enzyklopädie
Versionsgeschichte interaktiv durchsuchen
[gesichtete Version][gesichtete Version]
← Zum vorherigen Versionsunterschied
Inhalt gelöscht Inhalt hinzugefügt
VisuellWikitext
DARRT
→DARRT: Artikel wurde gelöscht
 
(34 dazwischenliegende Versionen von 21 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
[[File:Rapidly-exploring Random Tree (RRT) 500x373.gif|thumb|Rapidly-exploring Random Tree (RRT) 500x373]]
[[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
'''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.&nbsp;B. von Greifarmen.<ref name="Lavalle1998">{{cite journal
| author = Lavalle, S.M.
| author = Lavalle, S.M.
| year = 1998
| year = 1998
Zeile 6: Zeile 6:
| journal = Computer Science Dept, Iowa State University, Tech. Rep. TR
| journal = Computer Science Dept, Iowa State University, Tech. Rep. TR
| pages = 98–11
| pages = 98–11
| url = http://citeseer.ist.psu.edu/311812.html
| url = http://citeseer.ist.psu.edu/311812.html
}}</ref>
}}</ref>


==Geschichte==
== Geschichte ==
Um Pfadplanung für Roboter um Hindernisse herum durchzuführen wurde relativ früh in der Informatik der [[A*-Algorithmus]] entwickelt (1960'er 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 Pfadplannungs-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" />
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.
Performancemäßig ist RRT leistungsfähiger als [[A*-Algorithmus|A*]]. 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. Aber, die Leistungssteigerung von RRT gegenüber dem originalen [[A*-Algorithmus]] ist in der Praxis nicht höher als um den Faktor 3 bis 4. Auch A* verwendet bereits einen Graphen, der effizient nach dem kürzesten Weg durchsucht wird. In einigen Fällen schneidet RRT 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.


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" />.
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==
== 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.&nbsp;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.
'''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===
=== 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 manuell durchzuprobieren mittels [[Brute-Force-Methode|Brute-Force]]. 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.
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 soetwas 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.
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 OpenSource auf den Webseiten des ROS Projektes<ref name="ros2013" />. Das Greifen von Objekten wird hier <ref name="kaelbling2015intelligence" /> erläutert.
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'''
'''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|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.
[[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'''
'''Hybridsystem'''
Zeile 41: Zeile 43:
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.
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===
=== 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.
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.
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:
Weitere Anwendungen in der Praxis waren:
Zeile 51: Zeile 53:
* Steuerung von Roboterarmen um ein Objekt auf dem Tisch zu verschieben<ref name="king2015nonprehensile" />
* Steuerung von Roboterarmen um ein Objekt auf dem Tisch zu verschieben<ref name="king2015nonprehensile" />


==Einzelnachweise==
== Einzelnachweise ==
<references>
<references>
<ref name="urmson2003approaches">
<ref name="urmson2003approaches">
{{Literatur
{{cite book|
|Autor=Chris Urmson, Raid G. Simmons
title = Approaches for heuristically biasing RRT growth.|
|Titel=Approaches for heuristically biasing RRT growth
author=Chris Urmson, Raid G Simmons|
journal = IROS|
|Sammelwerk=IROS
volume = 2|
|Band=2
|Nummer=
pages = 1178–1183|
year = 2003|
|Datum=2003
|Seiten=1178-1183}}
url = http://www-preview.ri.cmu.edu/pub_files/pub4/urmson_christopher_2003_1/urmson_christopher_2003_1.pdf
}}
</ref>
</ref>
<ref name="rohrmoserimplementierung">
<ref name="rohrmoserimplementierung">
{{Literatur
{{cite book|
|Autor=Bertram Rohrmoser, Christopher Parlitz
title = Implementierung einer Bewegungplanung für einen Roboterann Implementation of a path-planning algorithm for a robot arm|
|Titel=Implementierung einer Bewegungplanung für einen Roboterann Implementation of a path-planning algorithm for a robot arm
last1 = Rohrmoser|
|Sammelwerk=Fraunhofer IPA
first1 = Dipl-Ing Bertram|
|Band=
last2 = Parlitz|
|Nummer=
first2 = Christopher|
|Datum=2002
last3 = Fraunhofer|
|Seiten=}}
first3 = IPA|
journal = |
url = http://www.morpha.de/download/publications/IPA_Implementation_of_PathPlanningAlgorithm_Robotic2002.pdf
}}
</ref>
</ref>
<ref name="knispel2013performance">
<ref name="knispel2013performance">
{{Literatur
{{cite book|
|Autor=Lukas KNispel, Radomil Matousek
title = A Performance Comparison of Rapidly-exploring Random Tree and Dijkstra’s Algorithm for Holonomic Robot Path Planning|
|Titel=A Performance Comparison of Rapidly-exploring Random Tree and Dijkstra’s Algorithm for Holonomic Robot Path Planning
last1 = Knispel|
|Sammelwerk=Institute of Automation and Computer Science, Faculty of Mechanical Engineering, Brno University of Technology
first1 = Lukas|
|Band=
last2 = Matousek|
|Nummer=
first2 = Radomil|
|Datum=2013
journal = Institute of Automation and Computer Science, Faculty of Mechanical Engineerig, Brno University of Technology|
|Seiten=}}
year = 2013|
url = http://www.wseas.us/e-library/conferences/2013/Budapest/MATH/MATH-22.pdf
}}
</ref>
</ref>
<ref name="ros2013">
<ref name="ros2013">
[http://wiki.ros.org/darrt darrt Documentation], ROS.org, 2013, abgerufen am 21. Dezember 2016
{{cite book|
title = darrt Documentation|
last1 = ROS.org|
first1 = |
year = 2013|
journal = |
url = http://wiki.ros.org/darrt|
accessdate = December 21, 2016
}}
</ref>
</ref>
<ref name="mitwebsite">
<ref name="mitwebsite">
[http://people.csail.mit.edu/jbarry/ Personal Website Jennifer Barry, CSAIL, MIT 2013], abgerufen am 21. Dezember 2016
{{cite book|
title = Personal Website Jennifer Barry|
last1 = MIT|
first1 = CSAIL|
year = 2013|
journal = |
url = http://people.csail.mit.edu/jbarry/|
accessdate = December 21, 2016
}}
</ref>
</ref>
<ref name="arms">
<ref name="arms">
Matt Klingensmith, Youtube-Video: DARRT Tool Regrasp (4x) 2014
{{cite book|
title = Youtube Video: DARRT Tool Regrasp (4x)|
last1 = Klingensmith|
first1 = Matt|
journal = |
year = 2014|
url = https://www.youtube.com/watch?v=bQL90xah33M|
accessdate = December 21, 2016
}}
</ref>
</ref>
<ref name="linkedln">
<ref name="linkedln">
[https://www.linkedin.com/in/jennifer-barry-742a0799 Jennifer Barry professional biography, LinkedIn, 2016]
{{cite book|
title = Jennifer Barry professional biography|
last1 = Linkedln|
journal = |
year = 2016|
url = https://www.linkedin.com/in/jennifer-barry-742a0799|
accessdate = December 21, 2016
}}
</ref>
</ref>
<ref name="barry2013workshop">
<ref name="barry2013workshop">
{{Literatur
{{cite book|
|Autor=Jennifer Barry
title = Planning and Manufacturing Robots, NSF Workshop on Robot Planning in the Real World|
|Titel=Planning and Manufacturing Robots
last1 = Barry|
|Sammelwerk=NSF Workshop on Robot Planning in the Real World
first1 = Jennifer Lynn|
|Band=
journal = |
|Nummer=
year = October 28, 2013|
|Datum=2013
url = http://robotics.cs.unc.edu/PlanningWorkshop2013/slides/Barry.pdf
|Seiten=}}
}}
</ref>
</ref>
<ref name="kaelbling2015intelligence">
<ref name="kaelbling2015intelligence">
{{Literatur
{{cite book|
|Autor=[[Leslie Kaelbling]], Thomas Lozano-Perez
title = Intelligence in the Now: Robust Intelligence in Complex Domains|
|Titel=Intelligence in the Now: Robust Intelligence in Complex Domains
last1 = Kaelbling|
|Sammelwerk=DTIC Document
first1 = Leslie P|
|Band=
last2 = Lozano-Perez|
|Nummer=
first2 = Thomas|
|Datum=2015
journal = |
|Seiten=}}
year = 2015|
institution = DTIC Document|
url = http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA627156
}}
</ref>
</ref>
<ref name="jentzsch2015mopl">
<ref name="jentzsch2015mopl">
{{Literatur
{{cite book|
|Autor=Sören Jentzsch, Andre Gaschler, Oussama Khatib, Alois Knoll
title = MOPL: A multi-modal path planner for generic manipulation tasks|
|Titel=MOPL: A multi-modal path planner for generic manipulation tasks
last1 = Jentzsch|
|Sammelwerk=International Conference on Intelligent Robots and Systems (IROS)
first1 = Sören|
|Band=
last2 = Gaschler|
|Nummer=
first2 = Andre|
|Datum=2015
last3 = Khatib|
|Seiten=6208–6214}}
first3 = Oussama|
last4 = Knoll|
first4 = Alois|
journal = Intelligent Robots and Systems (IROS), 2015 IEEE/RSJ International Conference on|
pages = 6208–6214|
year = 2015|
organization = IEEE|
url = http://www6.in.tum.de/Main/Publications/mopl.pdf
}}
</ref>
</ref>
<ref name="barry2013thesis">
<ref name="barry2013thesis">
{{Literatur
{{cite book|
|Autor=Jennifer Lynn Barry
title = Manipulation with diverse actions|
|Titel=Manipulation with diverse actions
last1 = Barry|
|Sammelwerk=MIT
first1 = Jennifer Lynn|
|Band=
year = 2013|
|Nummer=
journal = |
|Datum=2013
school = Massachusetts Institute of Technology|
|Seiten=}}
url = http://dspace.mit.edu/bitstream/handle/1721.1/82342/861700257-MIT.pdf
}}
</ref>
</ref>
<ref name="gupta2015using">
<ref name="gupta2015using">
{{Literatur
{{cite book|
|Autor=Megha Gupta, Jörg Müller, Gaurav Sukhatme
title = Using manipulation primitives for object sorting in cluttered environments|
|Titel=Using manipulation primitives for object sorting in cluttered environments
last1 = Gupta|
|Sammelwerk=IEEE transactions on Automation Science and Engineering
first1 = Megha|
|Band=12
last2 = Müller|
|Nummer=2
first2 = Jörg|
|Datum=2015
last3 = Sukhatme|
|Seiten=608-614}}
first3 = Gaurav S|
journal = IEEE transactions on Automation Science and Engineering|
volume = 12|
number = 2|
pages = 608–614|
year = 2015|
publisher = IEEE|
url = https://pdfs.semanticscholar.org/713c/4bf10611caec8d460667be936ac4b342a1f6.pdf
}}
</ref>
</ref>
<ref name="king2015nonprehensile">
<ref name="king2015nonprehensile">
{{Literatur
{{cite book|
|Autor=Jennifer E. King, Joshua A. Haustein, Siddharta S. Srinivasa, Tamim Asfour
title = Nonprehensile whole arm rearrangement planning on physics manifolds|
|Titel=Nonprehensile whole arm rearrangement planning on physics manifolds
last1 = King|
|Sammelwerk=IEEE International Conference on Robotics and Automation (ICRA)
first1 = Jennifer E|
|Band=
last2 = Haustein|
|Nummer=
first2 = Joshua A|
|Datum=2015
last3 = Srinivasa|
|Seiten=2508–2515}}
first3 = Siddhartha S|
last4 = Asfour|
first4 = Tamim|
journal = 2015 IEEE International Conference on Robotics and Automation (ICRA)|
pages = 2508–2515|
year = 2015|
organization = IEEE|
url = https://www.ri.cmu.edu/pub_files/2015/5/ICRA15_1356_FI.pdf
}}
</ref>
</ref>
</references>
</references>

Aktuelle Version vom 28. März 2025, 10:01 Uhr

Rapidly-exploring Random Tree (RRT) 500x373

Rapidly-exploring random tree (RRT) (dt. etwa schnell erkundender zufälliger Baum) ist ein Suchalgorithmus (und dessen zugrunde liegende Baum-Datenstruktur), der hochdimensionale 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.[1]

Geschichte

[Bearbeiten | Quelltext bearbeiten]

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* um zwei wesentliche Elemente: einmal wird ein 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.[2]

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[3].

Voronoi Bias

[Bearbeiten | Quelltext bearbeiten]

Der Voronoi Bias dient dazu, das Wachstum des RRT-Baumes zu steuern[4] 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 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

[Bearbeiten | Quelltext bearbeiten]

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

[Bearbeiten | Quelltext bearbeiten]

Ausgangspunkt für die Entwicklung von DARRT war die Frage, wie man einen bestimmten Sollzustand im C-Space (Configuration space) erreicht. Normalerweise ist der Problemraum zu groß um ihn mittels Brute-Force-Methoden 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 prozeduralen Animation wo so etwas schon länger eingesetzt wird um Charaktere in Computerspielen realistisch zu animieren. Das RRT-Sampling hingegen basiert auf einer 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, 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[5]. Das Greifen von Objekten wird hier[6] erläutert.

Erfinder

Jennifer L. Barry ist die Erfinderin von DARRT. Sie hat das Verfahren erstmals im Jahr 2013 in ihrer Dissertation beschrieben[7]. Jennifer L. Barry ist bei Boston Dynamics angestellt[8]. Zuvor war sie bei Rethink Robotics und am MIT tätig. Auf dem Server des MIT ist ihre Webseite abrufbar[9], 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[10]. 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

[Bearbeiten | Quelltext bearbeiten]

Der DARRT-Algorithmus wurde bisher auf dem ROS Standardroboter PR2 implementiert. Es gibt dazu Videos[7] 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 DARPA ARM-S Projektes auch für „dexterous grasping“ Aufgaben eingesetzt[11]. Dort bestand die Aufgabe darin, für den „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[12]
  • zum Sortieren von Lego-Steinen durch einen PR2 Roboter[13] (ein dem DARRT-Algorithmus verwandtes Verfahren)
  • Steuerung von Roboterarmen um ein Objekt auf dem Tisch zu verschieben[14]

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. ↑ Lavalle, S.M.: Rapidly-exploring random trees: A new tool for path planning. In: Computer Science Dept, Iowa State University, Tech. Rep. TR. 1998, S. 98–11 (psu.edu).
  2. ↑ Bertram Rohrmoser, Christopher Parlitz: Implementierung einer Bewegungplanung für einen Roboterann Implementation of a path-planning algorithm for a robot arm. In: Fraunhofer IPA. 2002.
  3. ↑ Lukas KNispel, Radomil Matousek: A Performance Comparison of Rapidly-exploring Random Tree and Dijkstra’s Algorithm for Holonomic Robot Path Planning. In: Institute of Automation and Computer Science, Faculty of Mechanical Engineering, Brno University of Technology. 2013.
  4. ↑ Chris Urmson, Raid G. Simmons: Approaches for heuristically biasing RRT growth. In: IROS. Band 2, 2003, S. 1178–1183.
  5. ↑ darrt Documentation, ROS.org, 2013, abgerufen am 21. Dezember 2016
  6. ↑ Leslie Kaelbling, Thomas Lozano-Perez: Intelligence in the Now: Robust Intelligence in Complex Domains. In: DTIC Document. 2015.
  7. ↑ a b Jennifer Lynn Barry: Manipulation with diverse actions. In: MIT. 2013.
  8. ↑ Jennifer Barry professional biography, LinkedIn, 2016
  9. ↑ Personal Website Jennifer Barry, CSAIL, MIT 2013, abgerufen am 21. Dezember 2016
  10. ↑ Sören Jentzsch, Andre Gaschler, Oussama Khatib, Alois Knoll: MOPL: A multi-modal path planner for generic manipulation tasks. In: International Conference on Intelligent Robots and Systems (IROS). 2015, S. 6208–6214.
  11. ↑ Matt Klingensmith, Youtube-Video: DARRT Tool Regrasp (4x) 2014
  12. ↑ Jennifer Barry: Planning and Manufacturing Robots. In: NSF Workshop on Robot Planning in the Real World. 2013.
  13. ↑ Megha Gupta, Jörg Müller, Gaurav Sukhatme: Using manipulation primitives for object sorting in cluttered environments. In: IEEE transactions on Automation Science and Engineering. Band 12, Nr. 2, 2015, S. 608–614.
  14. ↑ Jennifer E. King, Joshua A. Haustein, Siddharta S. Srinivasa, Tamim Asfour: Nonprehensile whole arm rearrangement planning on physics manifolds. In: IEEE International Conference on Robotics and Automation (ICRA). 2015, S. 2508–2515.
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Rapidly-exploring_random_tree&oldid=254615018“