Mobile Open-Source Navigation

• Scholarship Recipient: Christian Vetter
• Project: »Mobile Open-Source Navigation«
• Description of the Project: The goal is to develop an open-source navigation software for mobile devices, which uses up-to-date technologies and algorithms. Furthermore, the use of public map material, in particular OpenStreetMap data, is to play an important role.

f.l.t.r.: Christian Vetter; Prof. Dr. Peter Sanders

Brief Description

The last years saw a huge number of speed-up technologies and algorithms that ensured that routing in large graphs of several magnitudes is still faster than a simple Djikstra or A* search. Some of these algorithms are well suited for use on mobile devices.

However, only a quite small number of these technologies have found their way into usable devices. Most commercial products use heuristics and free projects are often restricted to showing precalculated routes.

Thus, the aim is to develop an open-source navigation software for mobile devices which is to use up-to-date technologies and algorithms. Furthermore, the use of public map material, in particular OpenStreetMap  data, is to play an important role.

To simplify the use of future algorithms, the project will be kept modular.
Thus, it will only take little effort to integrate new algorithms and to test them under real-life  conditions.

Details

We put great emphasis on modularity and portability. Thus, the project is divided into individual, mostly disjunct sub-projects:

Routing

• Uses speed-up technologies for a fast calculation of shortest routes. Amongst others, we plan the the implementation of contraction hierarchies as this technology can, for example, routes across Europe in less than 100 ms on a Nokia N800.
• Advanced routing variations such as turning restrictions and penalties or dynamic changes due to traffic jams are to be possible.
• Speed profiles, which have to be defined in advanced, are supported as well.

Geocoding

• Recognizing towns using intelligent input (recognizing typos with a certain editing distance, making suggestions)
• Recognizing towns using GPS data

Renderer

• Efficient display of maps and routes
• Playing the routes
• Showing points of interest

Driving Instructions

• Automatically generating driving instructions from map material