Der universale Problemlöser – „KI made in Potsdam“ auf dem Siegeszug rund um die Welt

Schwierige Probleme beschäftigen die Menschen schon immer. Doch spätestens seitdem wir unaufhörlich mehr und mehr Daten sammeln, kommen neue hinzu, denen wir allein oft nicht mehr gewachsen sind. Diese Herausforderung kommt Clasp gerade recht. Dem Computerprogramm, das ein Team um den Potsdamer Informatiker Torsten Schaub entwickelt hat, können Probleme kaum schwer genug sein. Vom bestmöglichen Stundenplan für eine ganze Uni über die optimale Struktur eines riesigen Warenlagers bis zur autonomen Komposition musikalischer Werke – es gibt wenig, was Clasp nicht kann. Es muss nur knifflig genug sein.

Vom bislang größten Erfolg seines Programms hat Torsten Schaub, der an der Universität Potsdam die Professur für Wissensverarbeitung und Informationssysteme innehat, eher zufällig erfahren. Auf der Jahrestagung zur Erforschung Künstlicher Intelligenz im Sommer 2016 in New York stellten Forscher der kanadischen Universität von British Columbia ein hochkomplexes Problem vor – und auch das Werkzeug, mit dem sie es lösen wollten: Clasp. Die Wissenschaftler hatten von der Federal Communications Commission (FCC) der USA den Auftrag erhalten, die Neuaufteilung und Versteigerung der dortigen Rundfunklizenzen zu organisieren. Was einfach klingt, war eine gewaltige Herausforderung.

So sollten einerseits die bestehenden Frequenzen in neue aufgesplittet, andererseits Interferenzen vermieden werden. Zudem galt es sicherzustellen, dass die vielen Frequenzen nahezu zeitgleich zur Verfügung standen und versteigert werden konnten. Daraus ergab sich eine mathematische Aufgabe, die Millionen von Variablen enthielt. Genau das Richtige für Clasp, wie sich herausstellte.

Die KI sucht den Konflikt

Denn das Programm ist ein Conflict-Driven Answer Set Solver. „Ein universaler Problemlöser“, sagt Torsten Schaub. „Er löst verschiedenste kombinatorische Optimierungsprobleme, solche, die besonders wissensintensiv sind und viele Variablen enthalten.“ Und genau das macht Clasp zur Künstlichen Intelligenz. Denn während eine Software lange nur genau das tat, wozu sie programmiert worden war, entfalten KI-Systeme wie Clasp ihr Potenzial erst, wenn sie mit einem Problem „gefüttert“ werden. „Ein normales Computerprogramm ist nicht intelligent, es trifft keine Entscheidungen, denn der Lösungsweg ist durch seinen Programmcode vorgegeben“, erklärt der Informatiker. Bei Clasp sei dies anders. „Wir geben nur das Problem vor, den Lösungsweg findet es allein.“ Möglich sei dies, weil das System aus mathematischen Algorithmen besteht, die aus Fehlern lernen. Clasp könne diese nicht nur bewältigen, es brauche sie sogar. „Das System versucht, bei einer Aufgabe frühzeitig in Konflikte zu gehen – und aus ihnen Schlussfolgerungen zu ziehen. Tritt ein Konflikt auf, springt es sofort zurück an dessen Ursprung, reichert das Problem mit der neuen Information an und rechnet weiter“, erklärt der Wissenschaftler.

„Ganz am Anfang haben wir stark mit klassischen kombinatorischen Aufgaben gearbeitet, etwa dem Problem des Handlungsreisenden (siehe Kasten).“ Zu den frühen Übungsaufgaben zählte auch das Lösen von Sudokupuzzles. Heute werden mit diesem Beispiel Studierende an das Thema herangeführt. „Es stellt sehr einfach die Verbindung zu ihnen her, denn irgendwie ist doch jeder ein Sudoku-Experte“, sagt Schaub schmunzelnd. Doch schon bald kamen erste echte Anwendungsprobleme hinzu. So kooperierten die Informatiker mit Biologen an der Universität Potsdam bei der Analyse von biologischen Netzwerken. Die Wissenschaftler erstellten mit Clasp Stundenpläne für ganze Universitäten, die Räume, Zeiten und Dozierende für mehrere Tausend Kurse unter einen Hut bringen. Und das derart gut, dass es bis heute kein Programm besser kann. Studierende, Doktoranden und Mitarbeiter des Lehrstuhls wendeten Clasp im Laufe der Jahre auf immer mehr Gebiete und Probleme an: Die Steuerung von Roboterschwärmen, die optimale Bestückung von Lagerregalen oder die Streckenplanung von Logistikunternehmen waren ebenso darunter wie das Design von eingebetteten Systemen in Autos oder die autonome Komposition von Musikstücken. Nach einigen Jahren der Entwicklung machten Schaub und sein Team sich daran, dem System Stabilität zu verleihen. Es war reif für die Praxis.

Clasp ist inzwischen weltweit im Einsatz

Entwickelt innerhalb eines von der Deutschen Forschungsgemeinschaft (DFG) geförderten Projektes, waren Clasp und einige andere „verwandte“ Solver-Systeme von Beginn an Open Source und frei verfügbar. Im Laufe der Jahre seien sie weit über 160.000 Mal heruntergeladen worden. „Mittlerweile ist unsere Software so weit verbreitet, dass ich gar nicht mehr weiß, wer sie alles nutzt“, sagt der Forscher. Bekannt ist sie auf jeden Fall für ihren Einsatz bei der Konfiguration des offenen Betriebssystems Linux. Welche Bestandteile in welchen Versionen auf welchen Computern aufgespielt werden können, damit der Rechner stabil läuft, bestimmt Clasp. Doch es dauerte nicht lange, bis auch die Wirtschaft das Potenzial des Systems für sich entdeckte. Bei der Neuverteilung der Netzfrequenzen in den USA im Sommer 2016 hat es seine Sache gut gemacht und am Ende mehrere Milliarden Dollar gespart.

Der Erfolg von Clasp beruht auf zwei wichtigen Eigenschaften: Zum einen sei das System eines der effizientesten weltweit, sagt Schaub. Inzwischen könne es Probleme mit mehreren Millionen Bedingungen und Variablen lösen. Zum anderen verfüge es über eine Modellierungssprache, die dem eigentlichen Programm vorgeschaltet sei. Sie ermögliche dem Anwender, die Aufgabe für die KI relativ kurz und verständlich zu formulieren. Die Aufgabenstellung, mit deren Hilfe Clasp Sudokus lösen kann, ist nur sieben Zeilen lang. „Erst wenn das Problem, auf welches das System angewendet werden soll, gut formuliert ist, wird aus diesem ein mächtiges Werkzeug“, erklärt der Forscher. „Clasp ist dafür besonders gut geeignet, weil es die Repräsentation und die Verarbeitung von Wissen miteinander verbindet.“

Ein intelligenter Taschenrechner

Was die KI intelligent macht? Für Torsten Schaub eine Frage der Perspektive. „Als ich vier oder fünf Jahre alt war, brachte mein Vater einen Taschenrechner mit. Der war für mich hochintelligent“, sagt der Informatiker und lacht. „Letztlich funktioniert die Künstliche Intelligenz, die wir machen, wie ein Taschenrechner. Nur eben ein sehr guter.“

Dem, was heute unter dem Schlagwort Künstliche Intelligenz Furore macht, begegnete Schaub im ersten Semester seines Informatikstudiums in den 1980er Jahren an der TU Darmstadt. Ein Ferienkurs in Logischer Programmierung habe ihn angefixt, sagt er. Dass er dabei geblieben ist, zahlt sich heute aus. „Für mich ist es höchst befriedigend, dass wir von elementaren Ideen bis zur Industriefertigung gekommen sind. Als ich 1997 in Potsdam anfing, diskutierten wir noch über Grundlagen, etwa die Frage, wie man mit unvollständigen Informationen umgehen kann. Heute arbeiten wir an Systemen, die praktisch eingesetzt werden“, sagt Schaub nicht ohne Stolz. „In 20 Jahren von purer Theorie zur Praxis. Das ist ein gewaltiger Sprung.“ Dennoch befinde sich die Forschung zu Künstlicher Intelligenz erst am Anfang. So seien KI-Systeme in der Industrie noch gar nicht richtig angekommen. Daher stünden Entwickler immer wieder vor großen Herausforderungen, wenn es darum geht, die in der Theorie entwickelten Systeme für die Praxis fit zu machen. Aus diesem Grund ist für das Team um Schaub der Kontakt zu jenen, die Clasp in der Wirtschaft bereits einsetzen, so wichtig. „Unsere Forschung wird durch die Anwendung gesteuert, weil dort immer neue Grundlagenfragen entstehen“, so der Informatiker. „Und schließlich ist es unsere Aufgabe, diese Technologie für den breiten Markt tauglich zu machen – vom Großkonzern bis zum Kleinunternehmen.“

Eine eigene Firma für den Sprung in die Praxis

Im Frühjahr 2018 ist deshalb aus der Arbeitsgruppe von Torsten Schaub heraus mit „Potassco Solutions“ ein eigenes Unternehmen entstanden, das genau daran arbeitet. „Als wir gesehen haben, dass Clasp von immer mehr Unternehmen eingesetzt wird, haben wir uns gesagt, wir sollten – als Entwickler des Systems – daran mitwirken“, sagt der Wissenschaftler. Für ihn sei das Vorhaben aus zwei Gründen eine Herzensangelegenheit: Zum einen biete die Firma für ehemalige Studierende, Doktoranden und Mitarbeiter der Professur eine berufliche Perspektive. Vor allem aber gebe es auf diesem Weg die Chance, Clasp weiterzuentwickeln und die dazugehörige Grundlagenforschung fortzusetzen – auch nach dem Ende des DFG-Projektes. „Die Synergie mit der Forschungsgruppe beflügelt die Arbeit bei ‚Potassco Solutions‘ und umgekehrt.“

In einem der ersten Projekte ging es darum, für ein großes Bahnunternehmen einen Schichtplan zu erstellen – für 6.000 Beschäftigte, in Früh-, Mittel- und Spätschicht. Dabei hatte Clasp zahlreiche Parameter zu berücksichtigen: Vollzeit, Teilzeit, Urlaub, Auslastung zu verschiedenen Tageszeiten und vieles mehr. Nach rund einem Monat waren alle Bedingungen zusammengetragen und das Problem formuliert. Dann war Clasp am Zug. Woran bislang ein Mitarbeiter eine Woche gearbeitet hatte, bewältigte das System in einer halben Stunde. „Der fertige Plan war vollkommen korrekt, bis zur Beachtung der Arbeitsrichtlinien“, sagt Schaub. Aber die Möglichkeiten gingen darüber weit hinaus. So konnte es Vorschläge entwickeln, wie sich das Schichtsystem noch verbessern lässt, um etwa Überstunden abzubauen.

Von Beginn an wurde „Potassco Solutions“ als weltweit agierende Firma konzipiert und hat gegenwärtig acht Niederlassungen auf drei Kontinenten. „Wir wollen unser Wissen ja nach außen tragen – so wie wir Clasp immer schon in die Welt hinaus geschickt haben“, sagt der Forscher. Früher oder später sollen aber auch regionale Kooperationen folgen, betont der Informatiker. Immerhin ist Potassco, die Plattform, auf der KI-Systeme wie Clasp bereitgestellt werden und die der Firma den Namen gegeben hat, die Abkürzung für „Potsdam Answer Set Solving Collection“.

Die Firma

Im Frühjahr 2018 gründete Torsten Schaub gemeinsam mit Kollegen und ehemaligen Mitarbeitern das Unternehmen „Potassco Solutions“. Dessen Aufgabe ist einerseits die Vermarktung von Clasp, andererseits aber auch die Weiterentwicklung des KI-Systems an konkreten Anwendungsproblemen.

Zur Firma: https://potassco.com

Das Projekt

Clasp wird seit 2007 im Rahmen zweier DFG-Projekte als Solver für die Antwortmengenprogrammierung ASP (engl. Answer Set Programming) entwickelt. ASP ist ein Paradigma zum beschreibenden Problemlösen, bei dem das Hauptaugenmerk auf der kompakten Repräsentation von Wissen liegt. Über Jahre hinweg wurde es zum universalen Problemlöser entwickelt. Für eine der zentralen Veröffentlichungen über Clasp in der Fachzeitschrift „Artificial Intelligence“ im Jahr 2012 erhielten Torsten Schaub und seine zwei Co-Autoren Martin Gebser und Benjamin Kaufmann den „Prominent Paper Award 2018“. Damit zeichnet die Zeitschrift Veröffentlichungen aus, die in den vergangenen sieben Jahren eine herausragende Wirkung entfaltet haben.

Entwicklung hocheffizienter sequentieller und paralleler Systeme zum modellbasierten Problemlösen mittels Antwortmengenprogrammierung (2008–2012)

Advanced Solving Technology for Dynamic and Reactive Applications (2012–2018)

Die Systeme sind frei zugänglich unter: https://potassco.org

Das Problem des Handlungsreisenden ist eines der bekanntesten kombinatorischen Orientierungsprobleme. Es besteht aus der Aufgabe, die Reihenfolge für den Besuch von mehreren Orten nacheinander so festzulegen, dass sich die kürzeste mögliche Strecke ergibt, kein Ort zweimal besucht wird und der Ausgangsort zugleich Ziel ist. Wenn man die Begriffe „Ort“ und „Strecke“ nicht wörtlich, sondern mathematisch begreift, beschreibt es ein mathematisches Problem, das weit verbreitet ist und in vielen Zusammenhängen eine Rolle spielt, bei der Tourenplanung ebenso wie im Design von Mikrochips und der Genomsequenzierung. Je mehr Zusatzbedingungen zur „Route“ hinzukommen, desto komplexer wird das Problem. Übrigens gibt es beispielsweise für die Fahrt eines Handlungsreisenden durch die 15 größten Städte Deutschlands insgesamt 43.589.145.600 Möglichkeiten, von denen nur eine das Problem löst.

Der Wissenschaftler

Prof. Dr. Torsten Schaub studierte Informatik an der TU Darmstadt, wo er auch promovierte. Seit 1997 ist er Professor für Wissensverarbeitung und Informationssysteme an der Universität Potsdam.

E-Mail: torstenuuni-potsdampde

Text: Matthias Zimmermann
Online gestellt: Alina Grünky
Kontakt zur Online-Redaktion: onlineredaktionuuni-potsdampde