Forums Neueste Beiträge
 

RRT mit Python

24/06/2016 - 21:37 von Manuel Rodriguez | Report spam
Hallo,
das ist mein erstes Posting hier in der Gruppe. Keineswegs soll hier
der Versuch unternommen werden, Python schlechtzumachen, ganz im
Gegenteil. Python ist eine der besseren Programmiersprachen. Besonders
bemerkenswert ist die Eigenschaft in wenigen Zeilen Code elaborierte
Programme zu schreiben. Und wirklich langsam ist Python auch nicht,
weil es jedem frei steht, Erweiterungsbibliotheken in purem C-Code zu
schreiben und über import einzubinden.

Aber genug der Vorrede, ich möchte zum eigentlichen Thema kommen. Und zwar
habe ich mir für den Anfang ein Problem aus der Robotik herausgesucht
und zwar die Erstellung eines Rapidly-exploring random tree (RRT). Der
soll mit Hilfe von unterschiedlichen Instanzen von Box2D arbeiten um so
als Solver zu fungieren.

Eine erste Version ist bereits erstellt, keine Angst den Sourcecode gibt
es hier nicht zu sehen. Vielmehr geht es allgemein darum, wie man ein
derartiges Problem struktuiert. In der aktuellen Version wird der RRT
Tree als Klasse implementiert und die einzelnen Nodes als Array innerhalb
dieser Klasse. Leider hat das zur Folge, dass das etwas unübersichtlich
ist. Es gibt ziemlich viele Methoden und noch mehr Variablen. Erschwerend
kommt hinzu, dass man dabei sowohl in der Zeit vorwàrtsgeht als auch
unterschiedliche Abzweigungen verwaltet.

Die generelle Frage die mich umtreibt ist, ob und welche
Datenstrukturen man einsetzen sollte, für derartige Probleme. Eine
Recherche bei Google hat bisher nur wenig Informationen gebracht. Es
gibt einerseits die RRT Tree Referenzimplementierung von Lavelle,
http://msl.cs.uiuc.edu/~lavalle/code.html und zum anderen einen
ausgewachsenen Motion Planner genannt OMPL. Die Lavelle Version ist zwar
schön übersichtlich, ist jedoch nicht dafür gedacht um unterschiedliche
Physik-Engine-Instanzen zu verwalten. Die OMPL Software hingegen ist
zwar leistungsfàhig, setzt aber auf C++ als Programmiersprache und ist
didaktisch gesehen eine Katastrophe.

RRT Bàume sind eng verwand mit Backtracking und A* Algorithmen. Hier wird
hàufig Rekursion eingesetzt die auch in Python realisierbar wàre. Aber,
Rekursion ist nicht gerade etwas, was leicht verstàndlich ist. Gibt es
womöglich noch etwas, was ich übersehen habe?
 

Lesen sie die antworten

#1 Stefan Schwarzer
25/06/2016 - 10:32 | Warnen spam
On 2016-06-24 21:37, Manuel Rodriguez wrote:
das ist mein erstes Posting hier in der Gruppe. Keineswegs soll hier
der Versuch unternommen werden, Python schlechtzumachen, ganz im
Gegenteil. Python ist eine der besseren Programmiersprachen. Besonders
bemerkenswert ist die Eigenschaft in wenigen Zeilen Code elaborierte
Programme zu schreiben. Und wirklich langsam ist Python auch nicht,
weil es jedem frei steht, Erweiterungsbibliotheken in purem C-Code zu
schreiben und über import einzubinden.



Danke für deine freundliche Einleitung. Willkommen! :-)

Ich kenne mich mit deinem Fachgebiet nicht wirklich aus,
deshalb stochere ich im Folgenden etwas im Nebel.

Aber genug der Vorrede, ich möchte zum eigentlichen Thema kommen. Und zwar
habe ich mir für den Anfang ein Problem aus der Robotik herausgesucht
und zwar die Erstellung eines Rapidly-exploring random tree (RRT). Der
soll mit Hilfe von unterschiedlichen Instanzen von Box2D arbeiten um so
als Solver zu fungieren.

Eine erste Version ist bereits erstellt, keine Angst den Sourcecode gibt
es hier nicht zu sehen.



Ironischerweise könnte der Sourcecode sogar helfen, weitere
Vorschlàge zu machen (siehe unten). Sicher kommt es auch
darauf an, wie viel Code es ist. Wenn es sehr viel ist,
rümpfen vielleicht manche die Nase. ;-)

Vielmehr geht es allgemein darum, wie man ein
derartiges Problem struktuiert. In der aktuellen Version wird der RRT
Tree als Klasse implementiert und die einzelnen Nodes als Array innerhalb
dieser Klasse. Leider hat das zur Folge, dass das etwas unübersichtlich
ist. Es gibt ziemlich viele Methoden und noch mehr Variablen. Erschwerend
kommt hinzu, dass man dabei sowohl in der Zeit vorwàrtsgeht als auch
unterschiedliche Abzweigungen verwaltet.

Die generelle Frage die mich umtreibt ist, ob und welche
Datenstrukturen man einsetzen sollte, für derartige Probleme. Eine
Recherche bei Google hat bisher nur wenig Informationen gebracht. Es
gibt einerseits die RRT Tree Referenzimplementierung von Lavelle,
http://msl.cs.uiuc.edu/~lavalle/code.html und zum anderen einen
ausgewachsenen Motion Planner genannt OMPL. Die Lavelle Version ist zwar
schön übersichtlich, ist jedoch nicht dafür gedacht um unterschiedliche
Physik-Engine-Instanzen zu verwalten. Die OMPL Software hingegen ist
zwar leistungsfàhig, setzt aber auf C++ als Programmiersprache und ist
didaktisch gesehen eine Katastrophe.



Du fragst nach Datenstrukturen, aber wenn du nicht gerade
ein Performance-Problem hast, sind dein Problem vielleicht
gar nicht die Datenstrukturen, sondern die
Programmierschnittstellen. Manche ekligen Datenstrukturen
verlieren ihren Schrecken, wenn man sie hinter einer
intuitiven API verstecken kann. Achte beim Entwurf der API
darauf, dass sie deinem Denken über die zu lösenden Probleme
entspricht. Du solltest dich also auf einem eher hohen als
niedrigen Abstraktionsniveau bewegen. Mach es aber nicht
_zu_ abstrakt, das macht es auch wieder kompliziert. Es kann
auch helfen, die API iterativ zu entwickeln, sie also erst
mal für einfachere Probleme zu entwerfen und sie dann für
komplexere Probleme umzubauen. Das reduziert die
Wahrscheinlichkeit, den Wald vor lauter Bàumen nicht mehr zu
sehen.

Mit einiger Wahrscheinlichkeit wirst du mehrere API-Ebenen
brauchen, um das ganze übersichtlich zu halten.

Unter Umstànden ist der beste Ansatz, eine der vorhandenen
Bibliotheken mit einer "denkfreundlicheren" API zu kapseln.

RRT Bàume sind eng verwand mit Backtracking und A* Algorithmen. Hier wird
hàufig Rekursion eingesetzt die auch in Python realisierbar wàre. Aber,
Rekursion ist nicht gerade etwas, was leicht verstàndlich ist. Gibt es
womöglich noch etwas, was ich übersehen habe?



Ja, Rekursion ist manchmal nicht leicht verstàndlich. Ich denke
aber, dass man Rekursion einsetzen sollte, wenn das Problem
"natürlicherweise" rekursiv ist. Ein Beispiel ist die
Iteration über Baumstrukturen. Netterweise kann man aber die
Rekursion oft hinter einer nicht-rekursiven API verstecken.
Ein Beispiel ist `os.walk` in der Standardbibliothek. Du
kannst in Python die Iteration über Datenstrukturen oft sehr
schön mit Generator-Funktionen verstecken (Stichwort:
`yield`).

Ich fand Rekursion auch mal kompliziert und unübersichtlich,
aber es ist auch Gewöhnungssache. Ich habe festgestellt,
dass Rekursion für mich intuitiver wurde, als ich mich mit
funktionaler Programmierung (am Beispiel Haskell)
beschàftigte. Davon profitiere ich auch jetzt noch. :-)

Viele Grüße
Stefan

Ähnliche fragen