CheckMate von der Uni-Klagenfurt löst Industrie-Rechenprobleme

KI-Tool für die Produktion. „CheckMate“ entwickelt eigenständig Algorithmen für Kombinatorik und Optimierungen, so Forschende der Uni Klagenfurt.

Forscher:innen der Universität Klagenfurt (Institut für Artificial Intelligence und Cybersecurity) sei mit „CheckMate“ ein bedeutender Durchbruch in der automatisierten Problemlösung gelungen, so eine Aussendung: Die neue KI-gestützte Technologie entwickelt demnach eigenständig Algorithmen für komplexe Kombinatorik- und Optimierungsprobleme, wie sie beispielsweise bei der optimalen Planung von Industrieanlagen und Produktionsabläufen auftreten – und erzielt dabei deutlich bessere Ergebnisse als bisherige Verfahren für „harte Probleme“ der industriellen Praxis.

Für die Erfindung wurde ein Patent auf „Automated code generation and verification system and method“ beim Europäischen Patentamt (EPA) eingereicht („The present invention generally relates to an automated code evolution and verification system for optimizing a technical system. The invention further relates to a computer-implemented code evolution and verification method for optimizing a technical system (…)“).

Wenn das Sudoku 100.000 Reihen und Spalten hat

Als Beispiel für eine mit herkömmlichen Methoden kaum lösbare Optimierungsaufgabe zieht die Uni Klagenfurt ein Sudoku heran – aber keines, dem Sie schon begegnet sind.

Sudokus mit 9 Reihen und 9 Spalten konnten Rechenprogramme bereits vor mehr als zwanzig Jahren problemlos lösen. „Das Kernproblem liegt aber in der gewaltigen Explosion der Lösungsmöglichkeiten, sobald das Spielbrett erweitert wird“, erklärt Gerhard Friedrich, Professor am Institut für Artificial Intelligence und Cybersecurity der Universität Klagenfurt und Mitglied des Boards of Directors im vom FWF geförderten Cluster of Excellence Bilateral AI. Nimmt die Anzahl an Reihen, Spalten und möglichen Zahleneinträgen zu, z. B. auf 100.000 Reihen, Spalten und Zahlen, was das Problem in seiner Größe mit praktischen Anwendungen in der Industrie vergleichbar macht, so seien aktuelle allgemeine Problemlösungsverfahren überfordert. Der Speicherbedarf sprengt alle physikalischen Möglichkeiten und man würde Tausende von Jahren auf eine Antwort warten müssen.

Wenn nun zusätzliche Restriktionen dazukommen, beispielsweise erforderliche Muster bei den genutzten Zahlen, vergleichbar mit zusätzlichen Anforderungen in industriellen Problemen, verhärtet sich das Problem noch einmal dramatisch.

Die Lösungswege

Gerhard Friedrich arbeitet mit seinen Kolleg:innen schon seit vielen Jahren an Lösungen dieser so genannten „harten Probleme“, bei denen der Mensch mit seinen heuristischen Problemlösungsfähigkeiten gegenüber der Maschine bis dato als überlegen galt. Anwendungsfelder dafür gibt es viele: Von Eisenbahnsicherungssystemen bis hin zur möglichst optimalen Planung von Industrieanlagen oder Optimierungsfragen in der Logistik – in all diesen Feldern gelte es, aus einer oft unüberschaubar großen Menge von potenziellen Lösungen eine möglichst optimale zu finden.

Das Forschungsteam

Einem Team von Forscher:innen an der Universität Klagenfurt – bestehend aus Veronika Semmelrock, Benedetta Strizzolo, Francesco Zuccato, Patrick Rodler, Konstantin Schekotihin und Gerhard Friedrich – sei nun ein wesentlicher Schritt gelungen: Mit CheckMate stellen sie eine automatisierte evolutionäre Codegenerierung für kombinatorische Probleme inklusive Optimierung vor. Die Grundidee: Der Mensch gibt ein Problem vor – die Technik löst es.

Für die Technologie, die auf der „International Joint Conference on Artificial Intelligence 2026“ dem Fachpublikum vorgestellt wird, wurde kürzlich auch ein Patent eingereicht. Veronika Semmelrock und Francesco Zuccato sind Doktoratsstudierende der Universität Klagenfurt und Benedetta Strizzolo ist Masterstudentin der Universität Udine, die im Rahmen einer Projektarbeit in das Team der Universität Klagenfurt integriert wurde.

Das neue Tool

CheckMate ist ein Tool, das sich in das Open-Source-Framework für Code-Evolution OpenEvolve integrieren lässt. Eine strenge Korrektheitsprüfung von Lösungen auf Basis der Logik, systematische Evaluierung der Programmeffizienz sowie kontinuierliches Feedback führen laut den Angaben dazu, dass aus einem initial leeren Programm in einem schrittweisen Verfeinerungsprozess hochqualitative Algorithmen zustande kommen.

CheckMate müsse nicht vorgegeben werden, wie Lösungen berechnet werden sollen — es braucht dafür lediglich das Was, also eine Beschreibung, was eine Lösung ist, und eine kleine Menge von Beispielinstanzen. Anhand von sehr großen und komplexen Sudokus veranschaulicht, würde dies bedeuten, dass man CheckMate lediglich die Spielregeln beschreibt, woraufhin es automatisch einen Lösungsalgorithmus für beliebige vorgegebene Spielbretter generieren kann.