Aus Erfahrung kluge Maschinen

So genannte „Harte Probleme“ können vom Menschen effizienter gelöst werden als von Computern. Forscher versuchen nun, Aspekte menschlicher Problemlösungsstrategien auf die Maschinen zu übertragen.

Ein großer Halbleiterproduzent erhält jede Woche neue Aufträge und muss seine Produktionsabläufe so umstellen, dass diese möglichst effizient abgearbeitet werden. Das Unternehmen muss sich also fragen: In welcher Reihenfolge belegt man Maschinen? Welche Maschinen baut man um? Ein Herausforderung für die Informatik: Es gilt eine Software zu entwickeln, die eigenständig eine möglichst optimale Lösung für das sich verändernde Problem errechnet. An diesem Punkt kommt die Arbeit von Gerhard Friedrich und Erich Teppan (Institut für Angewandte Informatik) ins Spiel. Im Rahmen des Projekts „HINT – Heuristic Intelligence“ versuchen sie, die Stärken menschlicher Problemlösungsstrategien für die Künstliche Intelligenz stärker nutzbar zu machen.

„Der Mensch wird immer besser, wenn er wiederholt vor ähnlichen Problemen steht. Ein Beispiel ist Sudoku. Man sieht eine Menge von Probleminstanzen und legt sich Suchstrategien zu, sodass man die nächsten Instanzen leichter lösen kann“, erläutert Gerhard Friedrich. Damit könne die Technik – noch – nicht mithalten. Eine besondere Herausforderung sind die so genannten „harten“ Probleme, die sich auch mit den Sudokus erklären lassen: Für ein Feld, das aus 4 Spalten und 4 Reihen besteht, könnten alle zulässigen Lösungen fast augenblicklich durch einen gängigen Computer ermittelt werden. „Das Kernproblem liegt aber in der gewaltigen Explosion der Lösungsmöglichkeiten, sobald das Spielbrett etwas erweitert wird“, erklärt Friedrich. Bei einem 9×9-Spielfeld würde die Generierung aller Lösungen mehr als 100.000 Jahre dauern. Und bei einem 16×16-Spielfeld wäre die Anzahl an Jahren eine 1 mit 82 Nullen dahinter. Der Aufwand für die Problemlösung geht bei allen bekannten Lösungsmethoden im schlechtesten Fall exponentiell nach oben, selbst wenn nur wenige Felder hinzukommen. Das mehr oder weniger blinde Durchprobieren aller Möglichkeiten stellt unsere Computer also vor unmögliche Aufgaben, wobei bei den maximalen Lösungsdauern immer vom schlechtesten aller denkbaren Fälle ausgegangen wird: „Die meisten Probleme folgen ja bestimmten Mustern, daher gibt es oft ‚Abkürzungen‘ gegenüber dem blinden Durchprobieren aller Varianten“, so Erich Teppan.

Interessanterweise kommen Menschen mit solch riesigen oder gar unendlichen Suchräumen sehr viel besser zurecht, da der Suchraum mit Intuition reduziert wird. „Der Mensch hätte auch gar nicht die intellektuellen Kapazitäten, um blind zu durchsuchen“, erklärt Teppan. „Ihm helfen die Erfahrungen mit der Lösung von ähnlichen Problemen dabei, für neue Herausforderungen schneller und effizienter Resultate zu finden“, so Friedrich.

Solch intuitive Lösungsstrategien – in der Fachsprache „Heuristiken“ genannt – sind mittlerweile auch in der Künstlichen Intelligenz mit großem Erfolg im Einsatz. Jedoch sind die Definition und der Einbau von Heuristiken nur mit erheblichem menschlichen Aufwand möglich, da effektive Heuristiken bisher fast immer durch Expertinnen und Experten definiert werden. Ein Beispiel ist die Schach-Software: Mit einem enormen Einsatz ist es in den letzten Jahren gelungen, ein Programm zu entwickeln, das relativ verlässlich auch gegen die menschlichen Schach-Großmeister gewinnt. Ändert man aber die Spielregeln, funktioniert die Software nicht mehr. Friedrich und Teppan geht es nun darum, dem Computer das automatische Finden und Adaptieren von Heuristiken für neue Probleme zu ermöglichen.

Das Programm sollte also in der Lage sein, aus Erfahrungen aus der Vergangenheit klüger zu werden, um in der Zukunft Lösungen für neue Problemstellungen zu errechnen. „Der Algorithmus sollte sich weiterentwickeln“, fasst Friedrich zusammen. Übertragen auf das Beispiel des Halbleiterproduzenten, dessen Auftragslage und Produktionsplanung sich häufig ändern, bedeutet dies, dass das Programm aus bisherigen Konfigurationen und den entsprechenden Lösungen Strategien ableiten können soll, wie neue, ähnliche Problemstellungen zu bewältigen sind.

Das vollständige Absuchen aller Problemlösungswege, das bei den Sudokus im schlimmsten Fall so enorm viel Zeit beansprucht, ist dabei nicht mehr vorgesehen. Bei diesem Ansatz kann daher auch nicht immer bewiesen werden, dass man das eigentliche Optimum kennt und sich dem bis zu einem bestimmten Prozentsatz annähert, sondern man muss damit zufrieden sein, dass der Lösungsweg möglichst effizient funktioniert und in der Folge auch Basis für weiteres Lernen ist. Friedrich erklärt dazu: „Bei den so genannten ‚harten‘ Problemen müssen wir auf Vollständigkeit sowieso verzichten. Sie sind so etwas wie der heilige Gral der Informatik/Mathematik, weil man von dieser Klasse derzeit gar nicht weiß, ob es überhaupt einen effizienten Algorithmus zur Lösung geben kann oder ob die exponentielle Steigerung der Rechenzeit inhärent zum Problem gehört. Würde es uns gelingen, eine Antwort dafür zu finden, würden wir in einer Reihe mit den berühmtesten Mathematikern der Welt stehen.“

Bei der Suche nach einem „möglichst generellen Problemlöser“ ist es den Forschern gelungen, die technische Basis dafür zu bauen, dass das System menschen-ähnliche Heuristiken verarbeiten kann. „Wir mussten zum Beginn beispielsweise eine Sprache entwickeln, um dieses heuristische Wissen technisch ausdrückbar zu machen. Grundlage dafür waren auch Erkenntnisse aus der Psychologie, wie sich menschliche Heuristiken zusammensetzen“, so Teppan. „Dieser Problemlöser ist gebaut, nun geht es darum, dass er Heuristiken ‚erlernt‘“, fasst Teppan den aktuellen Stand zusammen.

Erich Teppan und Gerhard Friedrich arbeiten gemeinsam mit Infineon Technologies Austria, Siemens Österreich, dem Institut für Psychologie der AAU und einem Kollegen der TU Wien/Universität Oxford am Projekt „HINT – Heuristic Intelligence“, das von der Forschungsförderungsgesellschaft (FFG) unterstützt wird.

für ad astra: Romy Müller