Routenplanung mit Bus, Bahn, Flugzeug und Transfer in Echtzeit und unter aktueller Stauberücksichtigung – was nach einer Zukunftsvision klingt, könnte dem Internetanwender schon bald zur Verfügung stehen. Die Freiburger Professorin Hannah Bast und ihr Team forschen genau daran und haben dafür Googles höchsten Forschungspreis erhalten.
Die Freiburger Professorin Hannah Bast und ihr Team wurden für das Projekt „Next-Generation Route Planning“ mit dem Google Focused Research Award, Googles höchstem Forschungspreis ausgezeichnet.
Ziel des Projekts „Next Generation Route Planning“ ist es, eine Software zu entwickeln, die multimodale Routenplanung ermöglicht. Die freie Kombinationsmöglichkeit von Auto, Bus, Bahn, Taxi, Flugzeug, Fahrrad unter unmittelbarer Berücksichtigung von Staus und Fahrplanänderungen, sowie das Anbieten von Alternativen sollen die Routenplanung im Internet verbessern und stehen dem Anwender vielleicht schon in wenigen Jahren zur Verfügung.
Sie haben den Google Focused Research Award gewonnen – mit welcher Arbeit genau?
Um den Preis, den Google Focused Research Award, haben wir uns mit multimodalder Routenplanung beworben. Die meisten kennen die normale Routenplanung von Google Maps. Man kann eingeben, ich möchte von hier nach da, mit dem Auto, zu Fuß, mit Bus und Bahn. Das, was wir in den nächsten drei Jahren machen wollen, ist, das alles zu kombinieren. Der Routenplaner findet dann selbst heraus, wo es am besten ist zu laufen, mit dem Auto zu fahren, den Bus oder den Flieger zu nehmen. Das nennt sich multimodal.
Wie kann man sich Ihre Arbeit als Laie vorstellen?
Sie haben eine Weltkarte mit sämtlichen Straßen und ich frage Sie, wie ich von A nach B komme. Wenn sie kein Programm haben, müssen sie sich erst einmal eine Methode überlegen – und da gibt es viele Arten: Ich fahre entweder einfach in die Richtung in der mein Ziel liegt oder ich gucke mal, wo die nächste Autobahn ist und dann fahre ich in diese Richtung.
Aber das sind alles Heuristiken, Pi-mal-Daumen-Methoden, die mal klappen und mal nicht. Vielleicht ist gerade keine Autobahn in der Nähe und das ‚in-die-Richtung-fahren-wo-man-hinwill‘ klappt auch nicht immer. Wenn ich zum Beispiel von Freiburg nach Südafrika will, dann werde ich wahrscheinlich erst einmal zum Frankfurter Flughafen, also in die entgegengesetzte Richtung, fahren.
Also stellt sich die Frage, wie man das macht, damit es immer klappt. Wir brauchen eine allgemeine Methode, eine Vorschrift mit der man das löst, und das nennt man in der Informatik einen Algorithmus. Sich einen solchen Algorithmus zu überlegen, ist der erste Schritt. Danach muss man ein Programm schreiben, dass diesen Algorithmus implementiert.
Viele Forscher hören an dieser Stelle auf und sagen, die Programmierung soll jemand anderes machen. Ich mache aber beides gerne, ich entwickle den Algorithmus und schreibe die Software dazu.
Woher stammen die Daten, die Sie für die Routenplanung verwenden?
Zunächst einmal hat Google seine eigenen Daten. Außerdem gibt es Open Source Initiativen, wie zum Beispiel Open Street Maps. Diese funktionieren ähnlich wie Wikipedia, jeder kann mitmachen. Sie könnten jetzt also einfach mit Ihrem Handy mit GPS eine Straße entlanglaufen und diese Information dann bei Open Street Maps hochladen. Für die meisten Länder, auch für Deutschland, ist schon alles da. Sehr viel Kartenmaterial ist mittlerweile öffentlich.
Bei Bus und Bahn ist es natürlich schwieriger an die Daten zu kommen, weil sich die Fahrpläne ständig ändern. Google ist aber im Gespräch mit den Verbänden, wobei es inzwischen auch vereinheitlichte Formate gibt, bei denen Verbände ihre Daten zur Verfügung stellen können. An diese Daten zu kommen ist heutzutage nicht mehr allzu schwer.
Was genau ist der Google Focused Research Award?
Google vergibt seit etwa zehn Jahren Forschungsprreise, da Google an der Forschung partizipieren will und weil es eben ein Unternehmen mit viel Geld ist. Es gibt kleinere Förderungen, das sind so um die 60.000 Euro und dann gibt es verschiedene Preisklassen. Der Focused Research Award ist der höchstdotierteste Preis, der auch nur ab und an vergeben wird – in der Regel für größere Vorhaben, die für das Unternehmen besonders interessant und an dem viele Leute beteiligt sind.
Um diesen Preis zu bekommen, braucht man eine entsprechend starke Verbindung. Ich habe eine Zeitlang bei Google gearbeitet und das, was ich in meiner Forschung mache, ist sehr nah an dem dran, was Google auch macht, zum Beispiel für Google Maps. Es hat sich einfach angeboten, etwas zusammen zu machen.
Ab wann wird das Projekt „Next Generation Route Planning“ dem Internetanwender zur Verfügung gestellt?
Im Antrag haben wir einen Arbeitsplan von drei Jahren beschrieben. Da ich das Projekt gerne im Einsatz sehen möchte, kann es sehr gut sein, dass man in drei Jahren die Routenplanung bereits anwenden kann – auch wenn wir die Forschungsergebnisse natürlich nicht so genau vorhersehen können.
Übrigens ist das, was man jetzt auf Google Maps sieht, auch von uns. Die Algorithmen dahinter sind wenige Jahre alt, das sind alles relativ neue Forschungsarbeiten.
Die ganzen Wegbeschreibungen?
Die Karte ist nicht von mir, aber wenn man den Routenplaner „von A nach B“ klickt, bekommt man den Weg angezeigt. Diese Software basiert auf unseren Algorithmen.
An der Routenplanung für Straßen war ich auch beteiligt, die gibt es ja schon länger, aber die Routenplanung mit Bus und Bahn gibt es erst seit zwei Jahren. Allerdings funktioniert diese in Deutschland bisher nicht, weil die Verhandlungen über die Daten äußerst schwierig sind.
Wenn die Verhandlungen so schwierig sind, ist es dann nicht eher unwahrscheinlich, dass die neue Routenplanung in Deutschland angewendet werden kann?
Solange wir die Daten nicht erhalten, kann dieses Programm in Deutschland nicht eingesetzt werden. Die Software ist für die Routenplanung mit Bus und Bahn ist, wie gesagt, bereits vorhanden. Sie läuft auf der ganzen Welt, außer in Deutschland.
Wenn Sie irgendwo in Peking stehen und ans andere Ende der Stadt möchten, geben Sie das bei Google Maps ein, dann zeigt Ihnen die Routenplanung an, wo Sie in die U-Bahn steigen müssen, wo Sie aussteigen müssen, wie Sie von da aus zur Bushaltestelle kommen, um dann den Bus zu erreichen, der Sie zum Ziel bringt.
Sobald die Daten für die öffentlichen Verkehrsmittel in Deutschland freigegeben werden, gibt es diese Form der Routenplanung auch hier. Mit der Software, die wir gerade entwickeln, die Flugzeuge, Transfers, Taxis und weiteres in die Routenplanung mit einbezieht und auch Staus und Fahrplanänderungen berücksichtigt, wird es sich ebenso verhalten.
Haben Sie sich durch die Auszeichnung Google gegenüber verpflichtet?
Nein, das ist ja auch gerade das, was das Wort Preis beinhaltet. Ein Preis ist immer etwas Ungebundenes. Der Focused Research Award ist mit einer Million US Dollar dotiert, das sind ungefähr 750.000 Euro.
Auch wenn mich einige Leute nach der Preisverleihung gefragt haben, ob ich nun eine Reise in die Karibik plane: Das Geld ist nicht privat, es geht auf das Lehrstuhlkonto, also auf ein Konto an der Uni und davon können drei Leute für drei Jahre eingestellt und Rechner gekauft werden.
Wird die Software nach Abschluss des Projekts an Google verkauft?
Es gibt keine Vereinbarung dieser Art und die darf es auch gar nicht geben, sonst wäre das kein Preis, sondern eine Auftragsarbeit. Das Erstellen von Software gehört aus meiner Sicht zu seriöser Forschung für diese Art von Problemen dazu. Da geht es aber weniger darum, dass diese Software 1-1 von Google übernommen werden kann, sondern dass es einen überzeugenden “proof of concept” gibt. Also Evidenz dafür, dass unsere Ideen nicht nur in der Theorie sondern auch in der Praxis funktionieren.
So oder so ist aber natürlich schon das Ziel, dass das Ganze dann irgendwann bei Google läuft. Aber mehr in dem Sinne, dass sie unsere tollen Ideen und Algorithmen übernehmen und nicht, dass wir denen ein fertiges Produkt auf den Tisch stellen.
Info
Hannah Bast arbeitet seit 2009 an der Albert-Ludwigs Universität Freiburg und ist Inhaberin des Lehrstuhls für Algorithmen und Datenstrukturen am Institut für Informatik.
Foto: screenshot google.maps Hannah Bast: privatVeröffentlicht am 27. Juni 2012
