Anzeige
Informatik

Navigation wird schneller

Neue Methode beschleunigt Navigationssysteme um das 100fache

Navigationssystem © MMCD

Auch Navigationshilfen geraten manchmal in Hektik – beispielsweise dann, wenn der Fahrer einen angesagten Abzweig verpasst. Eine ganze Weile rechnet das Navigationsprogramm dann, ehe es einen neuen Weg verkündet. Jetzt haben Wissenschaftler eine Methode entwickelt, die Navigationshilfen um das 100fache beschleunigen könnte. Für Logistikunternehmen aber auch Routenplaner im Netz wäre dieses jetzt in „Science“ veröffentlichte Verfahren ein großer Fortschritt

Wer sein Auto aus der heimischen Garage gesteuert hat, passiert in der Regel immer wieder dieselben markanten Punkte. Will er in Richtung Norden, mag das eine naheliegende Autobahnauffahrt sein, in Richtung Süden vielleicht auch. Und zu allen westlichen Zielen bringt ihn möglicherweise ein Verteilerkreis, während er gen Osten immer eine bestimmte Kreuzung quert. Aus dieser Idee haben Wissenschaftler vom Max-Planck-Institut für Informatik eine Methode entwickelt, die den gegenwärtig schnellsten Routenplaner um einen Faktor 100 schlägt.

Weniger Knotenpunkte – schnelleres Ergebnis

„Wir reduzieren die Zahl der Knotenpunkte, die ein solches Programm berücksichtigen muss, drastisch“, erklärt Stefan Funke vom Max-Planck-Institut für Informatik in Saarbrücken. Zusammen mit Forschern der Universität Karlsruhe entwickelten er und seine Kollegen die neue Methode. Von knapp 20 Millionen Knotenpunkten im Straßennetz Westeuropas bleiben dabei nur noch gut 11.000 Transitknoten übrig. Die Entfernungen zwischen diesen Knoten braucht ein Routenplaner nur noch in einer Tabelle nachzuschlagen. „Das Programm wird auf diese Weise um Größenordnungen schneller, was mit vorherigen Ansätzen nicht möglich gewesen wäre“, sagt Holger Bast, der andere Part des Saarbrücker Forscherduos.

Bislang tastet sich ein Routenplaner von Knotenpunkt zu Knotenpunkt im Straßennetz. Und obwohl er in der Mitte zwischen zwei Zielen nur noch Autobahnen und Bundesstraßen berücksichtigt, braucht er dafür 100 Mal länger als für die Rechnung mit Transitknoten. „Manche kommerziellen Navigationshilfen rechnen zwar schnell, ermitteln aber nicht immer die beste Route“, sagt Bast. Die neue Methode liefert dagegen immer die beste Strecke, was sich insbesondere bei Logistikunternehmen in barer Münze auszahlt. „Mit unserem Algorithmus können auch relativ rechenschwache mobile Navigationssysteme die Route in Sekundenbruchteilen neu bestimmen, was jetzt manchmal noch Minuten dauert“, sagt Funke.

Knotennetz im Nahbereich feiner

Bleibt noch ein Detail: Zwischen Berlin und Barcelona funktioniert der Routenplaner schnell und zuverlässig, wenn er nur das grobe Netz aus Transitknoten berücksichtigt. Liegen jedoch Start und Ziel zu dicht beieinander, beispielsweise Berlin Tiergarten und Berlin Mitte, müssen die Forscher anders vorgehen. Sie könnten hier herkömmliche Methoden einsetzen, da diese für kurze Strecken relativ schnell berechnen.

Anzeige

„Wir favorisieren aber eine hierarchische Abfrage“, sagt Funke. Damit meint er, dass das Programm in diesem Fall mit einem etwas feineren Netz von Transitknoten rechnen soll. Das feinere Netz für Westeuropa haben die Wissenschaftler zum Beispiel aus gut 300.000 Transitknoten geknüpft. Und noch kürzere Distanzen fängt ein Netz von knapp drei Millionen Knoten auf. „Auf diese Weise können wir extrem schnell die beste Route zwischen beliebigen Punkten bestimmen“, sagt Bast.

(MPG, 30.04.2007 – NPO)

Teilen:
Anzeige

In den Schlagzeilen

Diaschauen zum Thema

keine Diaschauen verknüpft

Dossiers zum Thema

Smart Dust - Die unsichtbaren Computernetze der Zukunft

Galileo - Europas Satellitennavigationssystem auf dem Weg ins All

News des Tages

Feldhase

Genom des "Osterhasen" entschlüsselt

Erstes Bild der Magnetfelder ums Schwarze Loch

Ägypten: Wandbilder aus der Totenstadt

Wie das Klima den antarktischen Zirkumpolarstrom beeinflusst

Bücher zum Thema

Maschinen mit Bewusstsein - Wohin führt die künstliche Intelligenz? von Bernd Vowinkel

Das Maß der Welt - Die Suche nach dem Urmeter von Ken Alder

Menschmaschinen - Wie uns die Zukunftstechnologien neu erschaffen von Rodney Brooks

Top-Clicks der Woche