Diverse Action Rapidly-exploring Random Tree (DARRT)


Obwohl ich das Konzept bereits im Trollheaven Magazin erläutert habe, möchte ich an dieser Stelle auch noch einen Blogpost dazu verfassen. Worum geht es? Es geht um eine Methode zur Robotersteuerung welche von Jennifer Lynn im Jahr 2013 in ihrer Dissertation „Manipulation with diverse actions“ erläutert wurde. Das Konzept ist nicht komplett neu sondern stellt eher eine Zusammenfassung von vorheriger Forschung da. Neu ist jedoch, dass erstmal in einer längeren Abhandlung (200 Seiten) sowohl die Theorie als auch die praktische Realisierung aufgeschrieben wurde. Um DARRT richtig wertschätzen zu können zunächst ein kleiner Exkurs wie davor Motion Control bei Robotern betrieben wurde.

Die Grundproblem besteht darin herauszufinden, welche Steuerimpulse an einen Roboter gesendet werden müssen, damit er eine Aufgabe wie Grasping erledigt. Im einfachsten Fall steuert man den Robotern manuell, d.h. verwendet einen Joystick oder einen Datenhandschuh. Damit kann man überprüfen ob die Hardware funktioniert und die Signale beim Roboter ankommen. Wenn man jedoch eine automatische Lösung möchte wird es anspruchsvoller. Das Problem besteht darin, dass der Suchraum (also die Möglichkeiten welche existieren, auch als C-space bekannt) gigantisch ist. Selbst Supercomputer können nicht alle Möglichkeiten durchprobieren bis ein gewünschtes Ziel erreicht ist. Man hat lange Zeit das Problem nur theoretisch beschrieben. Meist so, dass man eine Zielfunktion definiert (Objekt A soll zu Punkt B gebracht werden) und dann gesagt, dass man eben diese Zielfunktion mithilfe von Solvern lösen muss. Das ist mathematisch gesehen sehr elegant, lässt sich praktisch jedoch nicht realisieren.

Das Konzept DARRT bietet eine Antwort auf diese Frage. Und zwar wird dabei Brute-Force-Suche (RRT) mit Motion Primitiven verknüpft. Das Prinzip ist vergleichbar als wenn in einem Passwordcracker wie Hashcat einerseits stur alle Möglichkeiten durchprobiert werden, gleichzeitig aber auch Heuristiken eingesetzt werden. DARRT überträgt diesen hybriden Ansatz auf das Motion Control Problem. Man könnte es beschreiben als eine Mischung aus „prozeduraler Animation“ (welche in der Gaming-Branche weit verbreitet ist) mit dem RRT Verfahren was ein sampling-basierender Solver ist mit dem normalerweise Pathplanning-Probleme gelöst werden.

Bei DARRT gibt es einerseits verschiedene Motion Primitive. Diese werden mit Hilfe von Programmcode erzeugt. Ein Motion Primitive könnte sein: Grasp, Pickup, walkto usw. Im Regelfall führt ein Motion Primitive zu einer Trajektorie und ja, Motion Primitive können parametrisiert werden. Unklar ist jedoch, welche Parameter in der aktuellen Situation benötigt werden und in welcher Reihenfolge sie eingesetzt werden. Hier kommt RRT ins Spiel. Dort wird über Brute-Force-Suche diese Frage beantwortet.

In einer konkreten Realisierung führt DARRT dazu, dass man einerseits Roboterprobleme mit Hilfe von Brute-Force löst. Das heißt, man startet das Programm, die CPU Auslastung geht auf 100% und der Lüfter geht an. Gleichzeitig ist jedoch die CPU Auslastung nicht unendlich sondern nachdem wenige hundert Parameter durchprobiert wurden gibt es Lösung. Es werden nicht Lowlevel Steuersignale erzeugt und auf Erfüllung der Constraints getestet, sondern es werden per Zufall Motion Primitive generiert. Auf diese Weise reduziert man den Suchraum dramatisch und man hat eine reelle Chance, dass der Computer nach weniger als 1 Minute eine Lösung findet.

Ein Nachteil von DARRT soll nicht verschwiegen werden. Die konkrete Realisierung ist programmiertechnisch anspruchsvoll. Im Gegensatz dazu sind moderne Chess-Engines, Passwortcracker wie Hashcat oder der Linux-Scheduler Anfängerprojekte. Das dürfte auch der Hauptgrund sein, warum es bisher nur wenige konkrete Software gibt, die damit erfolgreich arbeitet. Aber, meiner Meinung nach ist DARRT die Zukunft. Man kann im Einzelfall das Konzept sicher auch anders gestalten oder anders nennen, aber die Kombination aus Brute-Force-Suche plus Heuristiken ist der richtige Ansatz.

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s