Maurice Wippler:
Evaluation und Vergleich von Wegfindungsalgorithmen in dynamischen Umgebungen mit beweglichen Zielen
Kurzbeschreibung
Die vorliegende Arbeit evaluiert die Wegfindungsalgorithmen GAA* und MTD*Lite hinsichtlich ihrer Leistungsfähigkeit in dynamischen Umgebungen mit beweglichen Zielen. Sie zählen zu den schnellsten Wegfindungsalgorithmen auf diesem Anwendungsgebiet und werden unter anderem in der Robotik und Computer spielen genutzt. Zur Datenerhebung wurden die Algorithmen in C# implementiert und in verschiedenen Testszenarien auf zweidimensionalen Gittern getestet. Dabei wurden unterschiedliche Metriken, wie Laufzeit, Speicherverbrauch und expandierte Zustände gemessen. Die Ergebnisse zeigen, dass MTD*Lite in einer naiven Implementierung signifikant langsamer und speicherintensiver ist als GAA*. Gleichzeitig expandiert MTD*Lite im direkten Vergleich erheblich weniger Zustände und weist damit ein hohes Optimierungspotential auf, welches durch eine effizientere Implementierung erschlossen werden könnte.