Home | Sitemap | Kontakt | english  | Impressum | Datenschutz | KIT
Veranstaltungen
Freitag, 14.Dec 2018
CoderDojo
Montag, 17.Dec 2018
SDQ Winter Day 2018
Donnerstag, 20.Dec 2018
Informatik-Sonderkolloquium: "Predictability and Security for Cyber-Physical Systems"
Freitag, 11.Jan 2019
CoderDojo

Weitere Veranstaltungen...
Informatik mit Profil.
Instagram  

Mobile Open-Source Navigation

Mobile Open-Source Navigation
Ansprechpartner:

Christian Vetter

Projektgruppe:

Institut für Theoretische Informatik, Algorithmik II (Prof. Peter Sanders)

Starttermin:

2009

Mobile Open-Source Navigation

  • Stipendienempfänger: Christian Vetter
  • Projekt: »Mobile Open-Source Navigation«
  • Projektbeschreibung: Ziel ist es eine Open-Source Navigationssoftware für mobile Geräte zu erstellen, bei der aktuelle Techniken und Algorithmen zum Einsatz kommen. Weiterhin soll Wert auf die Verwendung öffentlicher Kartenmaterialien gelegt werden, insbesondere OpenStreetMap Daten.

  

v.l.n.r.: Christian Vetter; Prof. Dr. Peter Sanders

v.l.n.r.: Christian Vetter; Prof. Dr. Peter Sanders

 

Zusammenfassung

In den letzten Jahren gab es eine Fülle von Speedup Techniken und Algorithmen, die dafür sorgten, dass Routing selbst in großen Graphen mehrere Größenordnungen schneller ist als eine simple Dijkstra oder A* Suche. Einige dieser Algorithmen eignen sich durchaus sehr gut für den Einsatz auf mobilen Geräten.

Allerdings haben relativ wenige dieser Techniken ihren Weg in fertige Endanwendungen gefunden. Die meisten kommerziellen Produkte benutzen Heuristiken und freie Projekte beschränken sich oft auf das Anzeigen vorberechneter Routen.

Ziel ist es daher eine Open-Source Navigationssoftware für mobile Geräte zu erstellen, bei der aktuelle Techniken und Algorithmen zum Einsatz kommen. Weiterhin soll Wert auf die Verwendung öffentlicher Kartenmaterialien gelegt werden, insbesondere OpenStreetMap Daten.

Um den Einsatz zukünftiger Algorithmen leichter zu machen, wird das Projekt sehr modular gehalten.
So kann man dann mit relativ wenig Aufwand neuere Algorithmen integrieren und unter praxisnahen Bedingungen testen.

Details

Es wird großer Wert auf Modularität und Portabilität gelegt. Daher ist das Projekt in einzelne, zum Großteil disjunkte, Teilprojekte zerlegt:

Routing

  • Nutzt Speedup Techniken zum schnellen Berechnen kürzester Routen. Unter anderem ist
    geplant eine Implementierung von Contraction Hierarchies einzubauen, da diese Technik
    zum Beispiel auch noch Routen durch ganz Europa in unter 100ms auf einem Nokia
    N800 berechnen kann.
  • Fortgeschrittene Routing Varianten wie Abbiege-Verbote und Strafen oder dynamische
    Änderungen durch Staus sollen möglich sein
  • Unterstützt mehrere, im Vorfeld festlegbare, Geschwindigkeitsprofile

Geocoding

  • Ermitteln von Orten durch intelligente Eingabe (Tippfehler mit bestimmtem Editierabstand erkennen, Vorschläge machen)
  • Ermitteln von Orten durch GPS Daten

Renderer

  • Effizientes Darstellen der Karten und Routen
  • Abfahren der Routen
  • Anzeige von Points of Interest

Fahranweisungen

  • Aus Kartenmaterialien automatisch Fahranweisungen generieren