Uns Studenten interessiert an der Universität in erster Linie meist die Lehre, doch natürlich wird hier in Greifswald auch geforscht. In der Serie „Nachgeforscht“ wollen wir einzelne Forschungsprojekte und die Menschen dahinter vorstellen.
Gemeinsam mit seinem Kollegen Holger Bast vom Max-Plank-Institut für Informatik in Saarbrücken hat der Greifswalder Professor Stefan Funke vor wenigen Wochen den renommierten SaarLB-Wissenschaftspreis erhalten. Die beiden Informatiker entwickelten ein Verfahren, mit dem Routenberechnung deutlich schneller möglich sind als bisher. Professor Funke stand dem webMoritz vor einigen Tagen bereitwillig und geduldig Rede und Antwort. An dieser Stelle: Vielen Dank dafür.
webMoritz: Herr Professor Funke, können Sie kurz erklären, worum es in Ihrer Arbeit zur Routenberechnung geht?
Prof Funke: Die Routenberechnung ist als das sogenannte Kürzeste-Wege-Problem bekannt, ein klassisches Problem in der diskreten Mathematik bzw. Informatik. Ziel ist es, in einem vorliegenden Wegenetz unter allen möglichen Wegen von A nach B die kürzeste bzw. schnellste Alternative zu finden. Bisher brauchte ein typisches Navigationsgerät zur Berechnung einer Route im deutschen Straßennetz einige Sekunden. Das ist vor allem dann lästig, wenn man sich verfahren hat und das Gerät erst mit Verzögerung einen neuen Weg berechnet. Wir haben eine neue Methode entwickelt, mit der das etwa 100 Mal schneller als mit dem bislang besten Verfahren funktioniert.
webMoritz: Sie haben sich mit dem Thema Routenplanung auseinandergesetzt, wie funktioniert die Software in einem Navigationsgerät?
Prof Funke: Traditionelle Verfahren besuchen bei ihrer Suche nach der schnellsten Route z.B. von Saarbrücken nach Greifswald alle Kreuzungen/Orte, welche in kürzerer Zeit von Saarbrücken erreichbar sind als Greifswald selbst. Das dauert natürlich eine ganze Weile, da das im Beispiel praktisch alle Kreuzungen in Deutschland sind. Es gibt Verfahren, die diese Suche etwas optimieren und sich z.B. keine kleinen Dorfstraßen in der Nähe von Kassel anschauen, da es sehr unwahrscheinlich ist, dass diese relevant für die schnellste Route von Saarbrücken nach Greifswald sind. Dennoch bleibt die Suche sehr aufwändig.
webMoritz: Können Sie versuchen einem Nicht-Mathematiker zu erklären, wie ihr neues System funktioniert?
Prof. Funke: Man kann die Grundidee unseres Lösungsansatzes relativ leicht beschreiben. Wenn Sie sich überlegen, auf wieviel verschiedenen Routen Sie Ihre Nachbarschaft verlassen, wenn Sie „weit“ wegfahren, wird Ihnen auffallen, dass es davon nur eine Handvoll gibt. Greifswald ist hier sogar extrem, da man bei weiteren Reisen eigentlich immer auf die A20 fährt; dieselbe Beobachtung trifft aber auch auf größere Städte zu. Unser neues Verfahren identifiziert nun deutschlandweit einige Tausend sogenannter Transitknoten, von denen wir mathematisch beweisen können, dass jeder kürzeste Weg, welcher Städte verbindet, die weiter als sagen wir 100 km Luftline voneinander entfernt liegen, mindestens einen dieser Transitknoten enthält. Desweiteren berechnen wir alle paarweisen Distanzen zwischen diesen Transitknoten in einem Vorverarbeitungsschritt und speichern sie in einer Tabelle ab (ähnlich den Distanztabellen in einem Atlas).
Für jeden Ort bestimmen wir dann die Transitknoten, auf die man als erstes auf den lokalen Ausfallrouten trifft – von denen es wie oben angemerkt jeweils nur eine Handvoll gibt. Bei einer Anfrage von Saarbrücken nach Greifswald sind das etwa 10 Transitknoten für Saarbrücken und 5 für Greifswald. Mithilfe der vorberechneten Distanztabelle müssen wir dann nur 10*5=50 Routen ausprobieren und die beste auswählen. Ist jetzt etwas vereinfacht beschrieben, aber im Prinzip funktioniert es so.
webMoritz: Was passiert nun mit Ihrer Idee? Vermarkten Sie das Ganze?
Prof. Funke: Also am Anfang haben wir gar nicht über Vermarktung nachgedacht. Wenn man im Wissenschaftszirkus steckt, liegt die Priorität eindeutig auf der Publikationstätigkeit. Da wir deshalb zuerst publiziert hatten, konnten wir in Deutschland kein Patent mehr anmelden. Einige Leute haben uns dann gedrängt, die Idee zumindest in den USA zu patentieren; dort ist das bis zu einem Jahr nach der Erstveröffentlichung noch möglich. Danach haben wir uns umgeschaut, wer unser System einsetzten könnte; allerdings sind wir nicht die großen Marketingexperten und arbeiten dehalb diesbezüglich mit einer Firma zusammen. Im Moment sind wir zum Beispiel in Gesprächen mit Blaupunkt, Konkreteres möchte ich aber momentan nicht sagen.
webMoritz: Anfang Oktober haben Sie für Ihre Arbeit den SaarLB-Wissenschaftspreis bekommen. War das überraschend? Was haben Sie mit dem Preisgeld gemacht?
Prof. Funke: Wir haben schon geahnt, dass unser Ergebnis nicht so schlecht ist. Wenn man ein Verfahren entwickelt, welches bisherige Verfahren um den Faktor 100 schlägt, merkt man das ja. Wir hatten vorher auch schon einen Preis der Max-Planck-Gesellschaft dafür bekommen. Insofern kam es für uns jetzt nicht aus heiterem Himmel, aber der SaarLB-Preis ist natürlich allein schon vom Geldbetrag her auch deutschlandweit sehr begehrt und der Wettbewerb entsprechend groß. Sehr attraktiv ist auch die Tatsache, dass das Preisgeld nicht zweckgebunden ist. Im Prinzip können wir das Geld sinnlos auf den Kopf hauen – eigentlich keine schlechte Idee – aber wir stecken dann doch zum Teil in die Weiterentwicklung und Vermarktung des Systems.
webMoritz: Navigationsgeräte betreffen nun nicht unbedingt jeden Menschen, aber Problem und Lösungsansatz sind für jeden nachvollziehbar. Ist ihre Arbeit immer so dicht an der Praxis?
Früher wurde jede Straßenkreuzung einzeln berechnet, Transitknoten beschleunigen das Verfahren – Quelle: adriangonsalves via flickr
Prof. Funke: Nun, Routenberechnung ist nicht mein eigentliches Forschungsgebiet. Mein Spezialgebiet ist die algorithmische Geometrie und die diskrete Optimierung. Erstere ist zumindest auf den ersten Blick noch relativ nahe an dem was man aus der Schule so kennt – Linien, Dreiecke, Kreise – aber insgesamt eher praxisfremd. Um noch ein Beispiel mit Praxisbezug zu geben: Vor einigen Jahren haben wir für einen großen Automobilhersteller ein Verfahren entwickelt, mit dem es möglich ist, relativ einfach das Kofferraumvolumen eines neuen Fahrzeugmodells noch in der Planungsphase zu ermitteln. Früher musste da jemand per Hand am CAD-System so lange Ein-Liter-Blöcke in ein 3-D-Modell einpassen, bis er eine möglichst gute Lösung gefunden hatte. Das konnten wir mit einer Software automatisieren und sparen dadurch viel Zeit und Arbeit.
webMoritz: Bevor es Sie nach Greifswald kamen, haben Sie in Saarbrücken gearbeitet. Was verschlägt einen von dort in die andere Ecke der Republik?
Prof. Funke: Also das eine ist natürlich, dass es Professuren nicht wie Sand am Meer gibt. Ich habe mich etwa zwei Jahre lang an Unis beworben, der Markt ist jedoch relativ eng; man muss sich vorstellen, dass auf eine Stelle etwa 70 Bewerber kommen. Naja und in Greifswald hat es dann vor einem Jahr geklappt. Die Kollegen in Saarbrücken haben schon etwas komisch geschaut, als ich gesagt habe, wo es hingeht. Sie werden beim Reinkommen in das Gebäude schon gemerkt haben: Der Glamourfaktor hier ist nicht der Allergrößte. Mir hat es hier aber eigentlich schon beim Vorstellungsgespräch sehr gut gefallen, und ich fühle mich immer noch sehr wohl. Die Kollegen sind sehr nett, Stadt und Umgebung toll – die Lage am Meer ist ja fast unschlagbar. Auch die Stelle an sich ist reizvoll. Da es nicht allzuviele Informatiker hier gibt, hat man mehr Freiheiten, was z.B. Lehrinhalte betrifft.
webMoritz: War für Sie während des Studiums schon klar, dass Sie einmal Professor werden wollen?
Prof. Funke: Nein eigentlich gar nicht. Als ich 1993 in Saarbrücken anfing, habe ich Informatik aufgrund der Jobaussichten studiert. Mit der Diplomarbeit bin ich dann so ein bisschen in die Forschung reingerutscht und habe promoviert. Danach wollte ich eigentlich zurück in mein Heimatland Baden-Württemberg und dort „normal“ bei einer Firma anfangen – meine Frau arbeitete damals in Stuttgart. Aber sie wollte dann doch nicht in Stuttgart bleiben, und so hat es sich irgendwie ergeben, dass ich in Saarbrücken weitergeforscht habe.
webMoritz: Im Nachhinein, sind Sie zufrieden mit der Entscheidung?
Prof. Funke: Also im Nachhinein, wenn ich all das, was ich heute weiß, damals gewusst hätte, wäre ich gleich nach der Promotion in die freie Wirtschaft gegangen. Verstehen Sie mich nicht falsch – ich bin absolut zufrieden mit meiner aktuellen Stelle aber das war extreme Glückssache. Die Chancen auf eine permanente Uni-Stelle sind so gering, dass ich keinem empfehlen kann, darauf zu setzen. Man forscht nach der Promotion noch einige Jahre rum, und wenn es dann doch nicht klappt, steht sehr man schlecht da. Für die Industrie ist man Mitte/Ende dreißig, ggf. habilitiert, aber mit wenig Praxisbezug nicht unbedingt der Wunschkandidat. Falls es mit der Uni-Stelle klappt, ist das natürlich schon ein super Job. Man ist ein Stück weit sein eigener Chef und darf sich mit vielen interessanten Sachen beschäftigen.
webMoritz: Vielen Dank für das Interview und weiterhin viel Erfolg bei Ihrer Arbeit!
Bildquellen: Navigationsgerät auf der Startseite M Shades via flickr
Foto von Prof. Funke auf der Startseite: Jan Meßerschmidt, Presse- und Informationsstelle der Universität Greifswald
