Algorithms for vehicle navigation

Abstract

Nowadays, navigation systems are integral parts of most cars. They allow the user to drive to a preselected destination on the shortest or quickest path by giving turn-by-turn directions. To fulfil this task the navigation system must be aware of the current position of the vehicle at any time, and has to compute the optimal route to the destination on that basis. Both of these subproblems have to be solved frequently, because the navigation system must react immediately if the vehicle leaves the precomputed route or the optimal path changes e.g. due to traffic jams. Therefore solving these tasks efficiently is crucial for safe and precise navigation.

In this thesis we first described a fully autonomous localization scheme based on the shape of the driven trajectory, which provides very accurately the position of the vehicle in the street network. In the second part we investigated route planning for electric vehicle, describing efficient algorithms which allow for retrieving paths with low energy consumption in a fraction of a second on large street networks.

Der Großteil moderner Autos ist mit einem eingebauten Navigationssystem ausgestattet. Diese erlauben dem Nutzer durch genaue Fahranweisungen ein beliebiges vorgegebenes Ziel möglichst rasch oder kostengünstig zu erreichen. Um diese Aufgaben erfüllen zu können muss zum einen stets die aktuelle Position des Fahrzeugs im Straßennetzwerk bekannt sein und darüber hinaus die optimale Route von dieser Position zum Ziel berechnet werden können. In dieser Arbeit wurden beide Probleme untersucht und Algorithmen sowie Beschleunigungstechniken vorgestellt, die die Beantwortung von Anfragen in Straßennetzwerken mit Millionen von Knoten und Kanten in Echtzeit ermöglichen.