Rapidly-exploring random tree
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]
_500x373.gif)
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* 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
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
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 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
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:
Einzelnachweise
- 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.
- 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.
- 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.
- Chris Urmson, Raid G. Simmons: Approaches for heuristically biasing RRT growth. In: IROS. Band 2, 2003, S. 1178–1183.
- darrt Documentation, ROS.org, 2013, abgerufen 21. Dezember 2016
- Leslie Kaelbling, Thomas Lozano-Perez: Intelligence in the Now: Robust Intelligence in Complex Domains. In: DTIC Document. 2015.
- Jennifer Lynn Barry: Manipulation with diverse actions. In: MIT. 2013.
- Jennifer Barry professional biography, LinkedIn, 2016
- Personal Website Jennifer Barry, CSAIL, MIT 2013, abgerufen 21. Dezember 2016
- 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.
- Matt Klingensmith, Youtube Video: DARRT Tool Regrasp (4x) 2014
- Jennifer Barry: Planning and Manufacturing Robots. In: NSF Workshop on Robot Planning in the Real World. 2013.
- 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.
- 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.