Anhand eines einfachen Beispiels fassen wir nochmal den Ablauf der RAMP-Heuristikzusammen.
Aus der Startposition und initialer Geschwindigkeit des Agenten wird der Wurzelwegpunkt W_r erzeugt und in die noch leere Prioritätswarteschlange Q eingefügt.

In der ersten Iteration wird W_r aus Q entfernt und mit der Funktion reach(W_r) neue Nachfolge-Wegpunkt gesucht.

Die Menge Ω = reach(W_r) besteht aus den drei Wegpunkten W₁,W₂,W₃. Sei die Priorität eval(W₁ ) < eval(W₂) < eval(W₃). Diese werden ihrer Priorität nach in Q eingefügt.

Bei jeder weiteren Iteration wird der Wegpunkt W′ mit der kleinsten Priorität aus Q entfernt und mit reach(W′) neue Nachfolge-Wegpunkte gesucht, bewertet und in Q eingefügt.

Der Wegpunkt W₂₁ kann das Ziel direkt erreichen. Jedoch wird beim weiteren Suchen noch eine bessere Lösung über den Wegpunkt W₃ gefunden. Die Warteschlange wurde abgearbeitet. Alle anderen Wegpunkte in Q führten zu keiner Lösung.

Die Lösung 1 wurde zuerst gefunden, aber durch Lösung 2 noch übertroffen. Der Algorithmus ist terminiert. Die Bahnkurven werden angezeigt.

Die Laufzeit der RAMP-Heuristik kann vorerst nicht nach oben beschränkt werden, da eine Terminierung nach Abschnitt 3.2 nur stattfindet, wenn die Prioritätswarteschlange Q leer ist. Die Anzahl der gespeicherten Wegpunkte von Q wird zwar mit jedem Iterationsschritt um einen Wegpunkt verringert, aber durch das Finden von neuen Wegpunkten durch reach um maximal I Wegpunkte erhöht. In der Implementierung wurde deshalb eine künstliche Schranke eingefügt, die nach ϕ Schleifendurchläufen den Algorithmus terminieren lässt.

Angenommen der Algorithmus terminiert nach 0 < N ≤ ϕ Iterationsschritten. Sowohl das Validieren, ob ein Wegpunkt dem Zielpunkt entspricht, als auch das Evaluieren einer Priorität erfolgt in konstanter Zeit. Die Laufzeit von reach ergibt sich aus I Versuchen, bei denen jeweils maximal 3 * D Schritte auf Kollision getestet werden.

Ein Aufruf von reach besteht damit aus maximal 3 * I * D Kollisionsprüfungen. Vor einer Kollisionsprüfung muss die elementare Bewegung B für den Agenten berechnet werden, was nach Abschnitt 2.2 in konstanter Zeit möglich ist. Eine Kollisionsprüfung für zwei elementare Bewegungen ist nach Abschnitt 2.3 ebenfalls in konstanter Zeit berechenbar. Jedoch muss die Bewegung B gegen alle zeitlich überlappenden elementaren Bewegungen ϒ aller Hindernisse o ∈ O getestet werden. Die Laufzeit hängt also signifikant von der Anzahl n ≤|ϒ| der zu prüfenden elementaren Bewegungen ab und damit von der Anzahl der Hindernisse und der zeitlichen Dauer von B. n ist kleiner als |ϒ, weil bei einer ersten gefundenen Kollision die restlichen Bewegungen nicht mehr geprüft werden müssen.

Insgesamt ergibt sich folglich eine Laufzeit von (N * I * D * n), wobei N ≤ ϕ nach oben beschränkt ist und n ≤|ϒ| von der Anzahl der Hindernisse und deren Geschwindigkeit abhängt, da |O|≤|ϒ| gilt.

Anmerkung 1: Der Algorithmus terminiert auch ohne ein gegebenes ϕ, wenn eine vorläufige Lösung gefunden wurde, da jeder Wegpunkt mit einer schlechteren Reisezeit sofort verworfen wird und für jeden Wegpunkt W_i ∈ Ω = reach(W) die akkumulierte Zeit t_i > t größer sein muss als die vom untersuchten Wegpunkt W.

Anmerkung 2: Durch die restriktive Bewertung der Wegpunkte nach Abschnitt 3.4 und dem Schwellwert μ ist die Anzahl der Wegpunkte pro Datenfeld begrenzt. Jeder Wegpunkt erhöht für das jeweilige Datenfeld F den Wert von c. Da c zu der Priorität von W beiträgt, steigt die Priorität stetig an, je mehr Wegpunkte bewertet wurden. Daraus ergibt sich eine zwangsläufige Terminierung.

Anmerkung 3: Neue durch reach gefundende Wegpunkte können in logarithmischer Zeit in die Prioritätswarteschlange Q eingefügt werden, da diese durch einen Heap implementiert werden kann. Die logarithmische Zeit für das Einfügen hängt von der Größe der in Q gespeicherten Wegpunkte ab. Q wächst bei jedem Iterationschritt um 0 ≤|Ω|≤ I Wegpunkte abzüglich des untersuchten Wegpunktes. Q beinhaltet also nach N Schritten im Worst-Case e_max = ∑ _i=1^NI - 1 = N *I -N Elemente. Dadurch erhöht sich die Laufzeit auf (N * I * D * n + N * log(e_max)).

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

• Page:
•  1 
•  2 
•  3 
•  4