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