Besser spät als nie! Hier der abschließende Post zu RRT - Eine Simulationsumgebung. Ich habe mich an einer typischen RRT Aufgabe Versucht: Parke das Auto in eine enge Parklücke und stelle es am Ende möglichst paralell zum Bordstein hin. Dabei nutzen wir genau das Automodell wie es im ersten Post eingeführt und verwendet wurde. Für anspruchsvollere Simulationen kann man z.B ein Auto mit Anhänger nehmen. Hier ist das Fahrverhalten nochmal komplett anders, RRT findet aber meist auch schöne Lösungen.

Das Interface der simplen Parksimulation hat ein paar Einstellmöglichkeiten spendiert bekommen. So können auch User die nicht im Sourcecode Werte manipulieren wollen mit der Simulation rumspielen. Ich freue mich übrigens auf Screenshots von euren schönsten Einparkmanövern in den Kommentaren

Bevor ihr allerdings mit Simulieren loslegen könnt, braucht ihr noch ein paar Informationen zur Simulationsumgebung: Die Umgebung ist 200 x 100 Pixel groß, das Auto startet bei (100,20) und will nach (102, 78). Dabei kann es Lenkwinkel von -50° bis +50° annehmen und dabei eine Stecke von -20 bis 20px pro “Schritt” zurücklegen. Der Lenkwinkel und die Geschwindigkeit kann jeweils mit einem Multiplikator versehen werden, die voreingestellten Werte liefern ganz gute Resultate.

Spannend wird es, wenn man das Verhalten des Autos einschränkt: Wie parkt es, wenn es plötzlich nur noch nach Rechts lenken darf? Oder der Rückwärsgang kaputt ist und nur vorwährtsfahrend einparken muss? Ein paar dieser Fälle sind weiter unten mit Gif und Erklärung zu sehen .

Die Option “Show Full Random Tree” ist eine Art Debug-Option. Es schreibt den ganzen aufgespannten Tree in ein Image-File und zeigt es mit dem Standartprogramm in Windows an. Damit kann man sehen, dass das Auto garnicht den gewünschten Bereich erreichen kann oder nur eine bestimmte Strecke mit diesen Werten abdecken kann. Generell gilt: Wenn ihr nicht die Parklücke in dem Tree trefft, spielt erstmal mit der Velocity rum. So macht ihr größere “Schritte” und erreicht mehr auf der Karte. Erst dann würde ich den Angle-Multiplikator verändern, die Schrittanzahl würde ich genau so lassen oder reduzieren wenn ihr einen schwachen Computer habt.

Videos von Szenarien mit Erklärung:

Hier eine normale Einparksituation mit den voreingestellten Werten. Keine Restrictions sind gesetzt, das Auto kann also jede Position auf der Karte erreichen:

Was macht das Auto, wenn es nur Links lenken darf? Ohne dass man eine Wegfindung oder sonstiges benutzt findet es eine Lösung zum einparken. Dabei lenkt es immer wieder Links, um beim Zurücksetzen gerade zu fahren und sich so seitlich zu bewegen:

Ein weiterer spanneder Fall ist, wenn das Auto nur Vorwärs fahren darf. Hier bekommen wir zum ersten mal Probleme mit den Standartwerten. Das Programm findet keine Lösungen, also schauen wir uns den gesammten aufgespannten Tree an (Show Full Random Tree):

Hier sind die beiden Spektren abgebildet, also einfach alle Positionen die das Auto während der gesammten Simulation erreicht hat. Im rechten Fall ist das Vorwärtsfahren mit normalen Parametern zu sehen. Man kann erkennen, dass es zwar versucht die Kurve richtung Parkplatz zu machen, aber es einfach nicht schafft. Der Wendewinkel ist zu klein um nur Vorwärs einzuparken. Erwöht man den Winkelmultiplikator, so haben wir plötzlich das volle Sprektrum: Alle Punkte sind erreichbar. Und somit finden wir auch eine “Lösung” die so aussieht:

Natürlich gibt es auch Fälle, die einfach in dieser beschränkten Umgebung nicht funktionieren. Z.B. wenn man nur Links und Vorwärts fahren darf:

Erhöht man allerdings die größe der Karte, so dass das Auto einen vollen Kreis fahren kann, sieht die Sache schon ganz anders aus:

Das dazugehörige Spektrum kann sich auch sehen lassen:

 

 

Nachdem man jetzt so viele Bilder gesehen hat, sollte ich zum Abschluss noch etwas über den RRT Algorithmus ansich sagen. Es ist nicht der original RRT, da dieser fordert dass man den Tree in jede Richtung erweitern kann. Wir sind aber Bewegungsgebunden!

Im Prinzip spannt man einen Baum auf, der zu beginn mit der Startposition gefüllt wird. Nun wählt man eine beliebige Position innerhalb der Karte Q_new und berechnet, welcher Punkt der sich bereits im Baum befindet zu Q_new am nähsten ist. Dieser wird als Q_old gespeichert. Nun errechnet man (eigentlich) einen Zwischenpunkt, der zwischen Q_new und Q_old liegt. Wenn dieser Kollisionsfrei ist (bzw allgemein eine gültige Konfiguration) fügen wir diesen zum Baum hinzu. Dabei wird Q_old als Parent gesetzt, dass man später den Baum wieder bis zum Anfangsknoten zurücklaufen kann.

In dem Auto-Fall können wir keinen Zwischenpunkt berechnen, sondern wählen einfach zufällige Werte in die wir uns als nächstes Bewegen. Wenn der neue Punkt kollisionsfrei ist, fügen wir ihn zum Baum hinzu. Sonst wird der Punkt verworfen. Der Nachteil bei dieser Methode ist, dass wir keinen so schönen Baum aufspannen, sondern “nur” mehrere Pfade erkunden. Aber es reicht ja

Download Binary: RandomTree_Car_Binary.zip (4 Downloads)

Download Source: RandomTree_Car_src.zip (6 Downloads)