Rechenkunst im Straßennetz

Lars Mehnen unterrichtet an der Fachhochschule Technikum Wien. Der gebürtige Münchner, Jahrgang 1967, ist Diplomingenieur, Doktor und außerdem FH-Professor. Er bringt Generationen von zukünftigen Ingenieuren die Grundlagen der Künstlichen Intelligenz näher. Denn um nicht mehr und nicht weniger handelt es sich bei der Software, die in den kleinen Kästen hinter der Windschutzscheibe arbeitet: eine alltägliche Anwendung von Künstlicher Intelligenz.

"Es ist ganz einfach", fügt Lars Mehnen sogleich hinzu. "Jeder, der addieren und subtrahieren kann, kann das verstehen." Gibt es doch wesentlich anspruchsvollere Systeme auf dem Gebiet der Künstlichen Intelligenz, einem Fach, das sich seit einer legendären Versammlung von Wissenschaftern am College von Dartmouth, England, im Jahr 1956 rasant entwickelt. Manche Anwendungen erstellen zum Beispiel mit verblüffender Treffsicherheit medizinische Diagnosen, etwa die Software "Mycin" von der Universität Stanford, San Francisco, die auf Blutinfektionen spezialisiert ist und dabei nicht schlechter abschneidet als erfahrene Spezialisten. Oder ein Programm wie "Dendral", das molekulare Strukturen analysieren kann.

Gut, gemessen an solchen Ansprüchen sind die Anforderungen, die an das Kästchen im Auto gestellt werden, relativ einfach. Gegeben sind eine Position, die aus einem Satellitensignal ermittelt wurde, ferner Kartenmaterial, das mehr oder weniger genau ist, und schließlich das Fahrziel, das der Mensch bestimmt. Ausgehend von diesen drei Faktoren soll also die Software die optimale Route errechnen und verwendet dabei zunächst ein Verfahren, das aus der Betriebswirtschaft kommt. Die Distanzen in Kilometern werden als Kosten angesehen, die es zu minimieren gilt. Wenn jemand an seinem Gerät die Option "schnellste Route", "kürzeste Route" oder "schönste Route" einstellt, dann verändert sich damit die Gewichtungen, das Vorgehen bleibt jedoch unverändert: Es geht immer darum, die Variante mit den geringsten Kosten zu ermitteln. "Solche Verfahren werden ja auch bei vielen Spielen angewendet", ergänzt Lars Mehnen.

Tausend Jahre

Die eigentliche Schwierigkeit, die das Programm bewältigen muss, findet sich an einer anderen Stelle. Eine Straßenkarte besteht - mathematisch gesehen - aus einer großen Zahl von Kreuzungspunkten, die durch mehr oder weniger große Distanzen mit anderen Kreuzungen verbunden sind. Die einfachste Möglichkeit, die beste Route zu ermitteln, wäre nun die, dass das Programm gewissenhaft alle vom Standort aus erreichbaren Kreuzungen und von dort weiter alle jeweils verfügbaren Kreuzungen durchrechnet, und so weiter, bis das gefragte Ziel erreicht wäre. Eine absolut zuverlässige Methode, die Breitensuche genannt wird, "Breadth-first search" im Jargon der Künstlichen Intelligenz, mit der Distanzen und Kosten exakt ermittelt werden können.

"Es gibt nur einen Haken", sagt Mehnen mit feinem Lächeln. Bereits für eine Suchtiefe von 14 Knoten würde man zur Ermittlung aller Routen etwa 3523 Jahre brauchen, den gigantischen Speicherplatz von einem Exabyte vorausgesetzt, eine Dimension jenseits von Gigabyte, Terabyte und Petabyte, mit der der normale Erdenbürger niemals in Berührung kommt. "In Wahrheit", sagt Lars Mehnen, "wollen die Käufer eines Navigationsgeräts maximal fünf bis zehn Sekunden auf eine fertige Route warten."

Zum Glück kennen die Informatiker eine ganz brauchbare Alternative zu der zeitraubenden Breitensuche, nämlich die Tiefensuche (Depth-first search), ein radikales Verfahren, das sich nicht lange mit den nächstliegenden Kreuzungspunkten aufhält, sondern sofort in die Tiefe des Straßennetzes eintaucht, so weit wie möglich, bis es nicht mehr weiter geht. Diese Tiefensuche bringt in kürzester Zeit Ergebnisse und braucht deutlich weniger Speicher. Wirklich befriedigend fände es aber der durchschnittliche Autofahrer wahrscheinlich auch nicht, nur dann exakt am Ziel anzukommen, wenn er zufällig Glück hat.

Die Lösung liefert ein Verfahren, das im Jahr 1968 entwickelt wurde. Ausgedacht haben es sich damals Professoren der Stanford Universität, Nils John Nilsson, Peter Hart und Bertram Raphael. Diese Herren waren damit beschäftigt, einen der ersten modernen Roboter zu entwickeln, genannt "Shakey". Es sollte der kleinen Maschine, für die sich auch das US-Militär interessierte, eine vernünftige Orientierung im Raum ermöglichen und wurde der A*-Algorithmus genannt, manchmal auch ausgeschrieben: A-Stern-Algorithmus.

Dabei ist es nicht notwendig, vor dem Wort "Algorithmus" zu erschrecken, das einfach ein Rechenverfahren bezeichnet, wie man es seit Jahrtausenden kennt. Bereits der Grieche Euklid, 300 Jahre vor Christus, gab beispielsweise detaillierte Anweisungen, wie der größte gemeinsame Teiler eines Bruchs zu ermitteln sei und jedes Volksschulkind lernt einfache Rechenverfahren. Der majestätische Begriff "Algorithmus", der seit dem Mittelalter für solche Verfahren in Gebrauch ist, soll sich vom Namen des arabischen Gelehrten Al-Khowarazmi herleiten, der im neunten Jahrhundert im Haus der Weisheit in Bagdad lehrte und von dem Europa das indische Zahlensystem übernahm, das heute in Gebrauch ist.

Luftlinien

Der A-Stern-Algorithmus, der mittlerweile nicht nur experimentelle Roboter sondern alltägliche Autofahrer durch Raum und Zeit leitet, ist ein solches Rechenverfahren, wenn auch deutlich komplexer, und zeichnet sich dadurch aus, dass es Breiten- und Tiefensuche kombinieren kann. Möglich wird das durch die Einführung einer sogenannten heuristischen Funktion, benannt nach dem griechischen Wort "heurisko", zu Deutsch "finden". In diesem Fall handelt es sich um ein genial einfaches Manöver, nämlich die Einführung der Luftliniendistanz. Bei der Berechnung der Route berücksichtigt der Algorithmus die Distanz jedes Kreuzungspunktes in Luftlinie zum Ziel und kann damit schnell und effizient unergiebige Abzweigungen ausscheiden. Damit wird es möglich, in vertretbarer Zeit und vor allem mit realistischem Speichervermögen eine brauchbare Route zu berechnen.

"Überall funktioniert das allerdings nicht", ergänzt Lars Mehnen. Denn das Umschalten zwischen Breiten- und Tiefensuche bewältigen die Geräte mit normalem Speicher nur in normal dicht besiedeltem Gebiet. "In der Mongolei zum Beispiel oder in wenig besiedelten Gebieten der USA könnte auch die Tiefensuche an ihre Grenzen stoßen." Dann würde das Gerät keine Route mehr berechnen. In diesem Fall allerdings würde der Autofahrer wohl auch an sein Ziel kommen, wenn er in die richtige Richtung fährt, bis das Zielgebiet in die Reichweite der Tiefensuche käme und sich das Navigationsgerät wieder zurechtfände.

Wie der A-Stern-Algorithmus in einzelnen Versionen der Navigationssoftware von verschiedenen Herstellern im Detail arbeitet, ist allerdings ein streng gehütetes Firmengeheimnis. Es gibt Varianten, die lernen können, und andere, die speziell für den Online-Einsatz gedacht sind. Moderne eingebaute Navigationsgeräte sind oftmals auch mit der Lenkung des Wagens verbunden und können auch, wenn in Tunnels der Satellitenempfang ausfällt, über Geschwindigkeit und Lenkbewegungen genaue Positionen ermitteln und für die Routenberechnung verwenden.

Fürs Lars Mehnen persönlich ist die Arbeit mit dem A-Stern-Algorithmus ja nur ein winziges Teilproblem der Künstlichen Intelligenz. Er ist derzeit von ganz anderen Bereichen fasziniert, etwa von Projekten der Medizininformatik, bei denen es darum geht, mithilfe von genau dosiertem elektrischen Strom Querschnittgelähmten die Benützung ihrer Gliedmaßen zu ermöglichen, eine Aufgabe, die sehr sorgfältige Programmierung erfordert. "Wenn man da Fortschritte sieht, dann gibt einem das eine ganz besondere Befriedigung", sagt er, "viel mehr, als wenn es dauernd um Märkte und Umsätze geht". Außerdem hat er noch eine weitere Leidenschaft: Wieder einmal einen Satelliten zu bauen, wie er es schon vor Jahren im Rahmen eines studentischen Projekts getan hat. "Aber in Österreich ist es sehr schwer", seufzt er, "dafür das Geld aufzutreiben", und so liegen die einschlägigen Projekte vorläufig in der Schublade.

In solche Sphären können wir natürlich nicht folgen. Wir verlassen das Gebäude der Fachhochschule und steigen ins Auto. Das kleine Kästchen, das da an der Windschutzscheibe klebt, betrachten wir in Hinkunft mit ganz neuer Ehrfurcht. Künstliche Intelligenz, hier bei uns im Auto, das ist schon was.

www.technikum-wien.at