Zurück Vor

Detailergebnis zu DOK-Nr. 66622

Modifikation des A*-Algorithmus für energieeffizientes 3D-Routing

Autoren	D. Franke D. Dzafic D. Baumeister
Sachgebiete	0.3 Tagungen, Ausstellungen 0.11 Datenverarbeitung

Angewandte Geoinformatik 2013: Beiträge zum 25. AGIT-Symposium Salzburg. Berlin u.a.: Wichmann, 2013, S. 414-423, 9 B, 9 Q

Um eine Route zu berechnen, greifen die meisten Navigationssysteme auf zweidimensionales Kartenmaterial zurück. In der Regel hat der Benutzer vor der Berechnung die Wahl, ob er die kürzeste oder schnellste Route berechnen lassen möchte. Navigationssysteme verwenden für die Routenberechnung oftmals den A*-Algorithmus. Um eine energieeffiziente Route unter Berücksichtigung der Steigung von Streckenabschnitten zu berechnen, wie das bei dem eNav-Projekt der Fall ist, werden jedoch auch Steigungs-/Höheninformationen benötigt. Aus diesen zusätzlichen Daten kann eine dreidimensionale Karte generiert werden. Eine Modifikation des A*-Algorithmus ermöglicht mit dieser Datenbasis eine Berechnung der energieeffizientesten Route bezüglich der Steigung. Somit können große Anstiege umfahren werden und eine effizientere Nutzung der Akkukapazität erzielt werden. Der Beitrag stellt die notwendigen Modifikationen und Optimierungen bei dem A*-Algorithmus vor, mit deren Hilfe eine Berechnung der effizientesten Route bezüglich der Streckensteigung auf 3D-Kartenmaterial ermöglicht wird. Zudem wird durch einen Korrektheitsbeweis der heuristischen Funktion des A*-Algorithmus gezeigt, dass die modifizierte Version des A*-Algorithmus ebenfalls korrekt ist.