Modifikation des A*-Algorithmus für energieeffizientes 3D-Routing
Um eine Route zu berechnen, greifen die meisten Navigationssysteme auf zweidimensiona-les 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 ver-wenden 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 wer-den. Eine Modifikation des A*-Algorithmus ermöglicht mit dieser Datenbasis eine Berech-nung der energieeffizientesten Route bezüglich der Steigung. Somit können große Anstiege umfahren werden und eine effizientere Nutzung der Akkukapazität erzielt werden. Dieser Beitrag stellt die notwendigen Modifikationen und Optimierungen bei dem A*-Algorithmus vor, mit deren Hilfe eine Berechnung der effizientesten Route bezüglich der Streckenstei-gung 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.