Kombinatorische Probleme effizient lösen

In vier Wettbewerbskategorien konkurrierten zehn Systeme aus sieben Ländern. Das vom Informatikstudenten Benjamin Kaufmann im Rahmen seiner Diplomarbeit am Institut für Informatik entwickelte System „clasp“ nahm in drei Kategorien teil. In zwei Kategorien erzielte clasp den ersten und in einer Kategorie den dritten Platz. Insgesamt war clasp damit das erfolgreichste System im Wettbewerb.

Der Erfolg der so genannten Antwortmengenprogrammierung beruht zum großen Teil auf der Verfügbarkeit leistungsfähiger Softwaresysteme für die Antwortmengenberechnung. Zum Zwecke des Leistungsvergleichs zwischen existierenden Systemen und um zukünftige Entwicklungen anzuregen, wurde deshalb dieser internationale Wettbewerb ins Leben gerufen. Die Ergebnisse des Wettbewerbs wurden im Rahmen der Internationalen Konferenz für Logisches Programmieren und nichtmonotones Schließen in Phoenix (Arizona, USA) präsentiert.

Die Antwortmengenprogrammierung ist mit ihrer rund 20-jährigen Geschichte ein recht junges Gebiet der Repräsentation und des Lösens kombinatorischer Probleme. Ein Problem wird durch eine Menge logischer Regeln modelliert. Die aus den Regeln ableitbaren Antwortmengen entsprechen dann den Lösungen des Problems.

Gegenüber herkömmlichen Formalismen besteht der Vorteil der Antwortmengenprogrammierung darin, dass falsche Sachverhalte nicht explizit angegeben werden müssen. Dies entspricht der menschlichen Denkweise und erlaubt daher eine natürlichere Repräsentation von Wissen. Ein alltägliches Beispiel hierfür sind Fahrpläne. In der Regel wird nicht angegeben, wann kein Bus oder Zug verkehrt, sondern nur, wann tatsächlich ein Verkehrsmittel erwartet wird.

Heutzutage stehe die Antwortmengenprogrammierung an der Schwelle zum industriellen Einsatz, so die Uni Potsdam. Prototypische Anwendungen gibt es zum Beispiel in der Bioinformatik, der Produktkonfiguration und der Kontrolle des Space Shuttles. (dsc)