Navigationsgeräte im Auto sollen den schnellsten Weg finden. Aber oft gibt es noch einen schnelleren. Der Rechenvorgang ist so komplex, dass die kleinen Computer sich meist mit einem ungefähren Ergebnis begnügen. Wissenschaftler der TU Clausthal haben jetzt ein neues Verfahren entwickelt, wodurch die Route exakter und schneller berechnet wird.
Navigationssysteme erleichtern dem Fahrer die Routenplanung und führen ihn während der Fahrt durch Sprachanweisungen bis zum Ziel. Die Grundlage dazu bildet elektronisches Kartenmaterial, das neben dem genauen Straßenverlauf, zusätzlich Informationen zu Straßenklasse (Autobahn, Landstraße, Fußgängerzone etc.), erlaubten Fahrtrichtungen und Abbiegemöglichkeiten enthält. Für die Routensuche geht das Navigationssystem immer Schritt für Schritt vor: Es bestimmt unter Einhaltung der Abbiegevorschriften eine Folge von aneinandergrenzenden Streckenabschnitten, die vom Start zum Ziel führen.
Die klassische mathematische Methode, um eine optimale Route zu bestimmen, heißt Dijkastra-Algorithmus. Mit dem Algorithmus durchsucht das System die elektronischen Daten gleichmäßig in alle Richtungen. Da jedoch für eine Routensuche in Europa bereits mehrere Gigabyte Daten berücksichtigt werden müssen, dauert die Anwendung mit dem Dijkastra-Algorithmus nicht nur ziemlich lang, sondern benötigt auch einen großen Arbeitsspeicher. Daher bedienen sich praktisch alle aktuellen Navigationssysteme weniger aufwändigen Methoden, die zwar eine „gute“ Route aber keine optimale Lösung bieten.
In der Praxis bewähren sich die vereinfachten Methoden meistens. Jedoch muss mancher Nutzer eines Navigationssystems doch hin und wieder feststellen, dass das Gerät eine eher ungünstige Route gefunden hat. Er benötigt mehr Zeit oder Benzin, um ans Ziel zu kommen. Ziel der aktuellen Entwicklungen ist es, die Routenberechnung parallel zu den computertechnischen Möglichkeiten zu optimieren und noch schneller zuverlässige Ergebnisse zu erhalten.
In einer Zusammenarbeit mit dem Unternehmen Innovative Systems in Hamburg haben Wissenschaftler des Instituts für Mathematik der TU Clausthal eine modifizierte Standardberechnungsmethode, den A-Stern-Algorithmus (kurz „A*“), mit kommerziellen Kartenmaterial getestet. Während der Dijkstra-Algorithmus gleichmäßig in alle Richtungen sucht, richtet A* die Suche direkt auf das Zielgebiet aus. Auf diese Weise findet man schnell zum Ziel und kann alle anderen möglichen Routen bereits daran messen.
Als Resümee stellte Harald Wellmann von Innovative Systems fest: „Die Zusammenarbeit mit der TU Clausthal hat in unserer Entwicklung von Navigationssystemen einen Prozess in Gang gesetzt.“ Neben der Optimierung der Routenberechnung bestünde das Ziel auch darin, die Routen detailgetreu und dreidimensional darzustellen.
(idw – Technische Universität Clausthal, 12.01.2006 – NPO)
