Die Performance der Implementierung wurde gemessen und mithilfe von Charts visualisiert. Die Daten wurden für den gleichen Agenten aus 40 Wiederholungen eines Durchlaufes gemittelt. Ein Durchlauf entspricht sequentiellen Instanzen _j mit0 ≤ j ≤ 50. Dabei wurde ₀ mit null Hindernissen initialisiert. Ist eine Lösung für _j gefunden worden, werden 10 neue Hindernisse zu _j+1 hinzugefügt. An dem Zeitpunkt der ersten gefunden Lösung für _j, wird der Algorithmus gestoppt und die Datenerhoben. Für eine Instanz _j werden neben der benötigten Zeit t_L und der Anzahl der Hindernisse folgende weitere Daten erhoben: die Anzahl der durch eval bewerteten Wegpunkte, die insgesamte Anzahl an Versuchen von reach und die insgesamte Anzahl an Kollisionsprüfungen.

Hindernisse besitzen einen zufälligen Radius zwischen 0.001 und 0.0005 und ihre Startposition wurde zufällig gewählt, allerdings mit einem Mindestabstand von 0.1 zum Startpunkt s_A. Dies war notwendig, damit der Agent sich nicht von Anfang an in einer auswegslosen Situation befindet. Nachdem die Position zufällig bestimmt war, wurde ihre Geschwindigkeit so angepasst, dass sie zu einem zufälligen Zeitpunkt t_r mit der zuletztgefunden Lösung kollidieren, so dass jedes neue Hindernis nicht trivial für die alte Lösung ist. Auch hier wurde darauf geachtet, dass der Zeitpunkt t_r mit ≤ t_r ≤ t_L nicht zu früh gewählt wird, damit der Agent eine Chance hat eine Lösung zufinden.

Betrachtet man die Charts in Abbildung 4.7, besteht eine interessante Korrelation zwischen der benötigten Zeit und der Anzahl der Kollisionsprüfungen. Die beiden Graphen gleichen sich auffällig genau (siehe Abbildung 4.8). Daraus lässt sich schlussfolgern, dass die meiste Zeit des Algorithmus dafür benötigt wird, Bewegungen auf Kollisionen zu prüfen. Bei genauerer Betrachtung muss die RAMP Heuristik bei jedem Aufruf von reach genau I Versuche durchführen. Jeder der D Schritte innerhalb eines Versuches muss auf Kollision gegen Hindernisse getestet werden, bis eine Kollision gefunden wird. Das sind im Fall einer gesuchten kollisionsfreien elementaren Bewegung alle Hindernisse. Wie man im Chart sieht, werden bei 500 Hindernissen ca. 150 Kollisionsprüfungen pro Schritt durchgeführt. Auch wenn die Kollisionsprüfung nach Abschnitt 2.3 in konstanter Zeit berechnet werden kann, verbrauchen diese 150 Kollisionsprüfungen den größten Anteil der benötigten Zeit. Verbessert man die benötigteZeit einer Kollisionsprüfung auch nur um eine Mikrosekunde, sind das bei ca. 2.250.000 Kollisionsprüfungen bei 500 Hindernissen schon 2,25 Sekunden und damit eine 75% Geschwindigkeitssteigerung. Deswegen war es auch so wichtig den Abschnitt 2.3 in der Arbeit detailliert zu beschreiben und die während der Arbeit entstandenen Ergebnisse zur Beschleunigung der Kollisionsprüfung zu nennen.

Abbildung 4.7: Verschiedene Charts veranschaulichen die Performance der Implementierung

Abbildung 4.8: Die Differenz der Graphen ist die Zeit, die ohne Kollisionsprüfungbenötigt werden würde.

• Zusammenfassung
• Einführung
• Physikalische Grundlagen
• Lösungsansatz RAMP
• Implementierung
• Diskussion

• Page:
•  1 
•  2 
•  3