Integrierte Auswertung von Antwortmengenprogrammen und Erweiterungen

Der Aufstieg des World Wide Web und verteilter Systeme führte zur Entwicklung von Formalismen zur Integration von Datenquellen. Gegenstand dieses Projektes ist die Erforschung und Analyse neuartiger Evaluierungsmethoden für HEX-Programme. Dabei handelt es sich um eine Weiterentwicklung von Answer- Set Programmen (ASP), die Zugriff auf extern gelagerte Informationen haben. In HEX-Programmen erlauben sogenannte externe Atome den bidirektionalen Datenfluss zwischen dem logischen Programm und einer externen Datenquelle. Da aktuelle Algorithmen für verschiedene Teilprobleme während der Auswertung Großteils unabhängig voneinander optimiert wurden, ist das Zusammenspiel dieser Komponenten oftmals ein Hindernis für eine effiziente Auswertung. Es können drei zusammenhängende Einschränkungen der aktuellen Algorithmen identifiziert werden. Erstens ist die Zusammenarbeit des Grounders und des Solvers nicht optimal. Die existierenden Algorithmen können durch Konfigurationen entweder den Grounder oder den Solver bevorzugen, eine Gesamtoptimierung erfordert jedoch neue Techniken. Zweitens ist die Anbindung externer Quellen an den Solver unzufriedenstellend. Zwar können externe Atome viele Erweiterungen von ASP (z.B. Constraint-Atome) ausdrücken, die Algorithmen jedoch in der Regel nicht mit nativen Implementierung schritthalten. Dies liegt an einer zu losen Kopplung der externen Quellen und der Kernalgorithmen. Drittens erfordern größere Applikationen das Unterteilen des Programms in mehrere Komponenten. Zwar existieren dafür Techniken, jedoch werden die Komponenten meist auch während der Auswertung unabhängig voneinander betrachtet, was ebenfalls zu Performanceproblemen führt. Zur Überwindung dieser Einschränkungen sollen neuartige Algorithmen entwickelt werden, die eine globale Sichtweise auf das Problem besitzen. Insbesondere soll für eine effiziente Zusammenarbeit von Grounder und Solvers gesorgt werden. Weiters sollen neuartige Interfaces für externe Quellen entwickelt werden, die neue Arten der Abfrage zulassen, etwa partielle und inkrementelle Anfragen; dazu sind die theoretischen Konzepte zu erweitern. Zum Zwecke der Modularität sollen Techniken entwickelt werden, die aus eine saubere Kommunikation zwischen Komponenten über geregelte Interfaces erlauben, bei der Auswertung jedoch sämtliche Komponenten simultan einbezieht um für eine hohe Effizienz zu sorgen. Als Ergebnisse erwarten wir neuartige Algorithmen für ASP mit externen Quellen, neue Methoden für die Anbindung externer Quellen, sowie eine Prototypimplementierung, die als Open-Source Software veröffentlicht werden soll. Die Implementierung soll mittels neu entwickelten Benchmarksuites die Skalierbarkeit des Systems nachweisen; die Benchmarks sollen durch derzeitige und künftige Applikationen motiviert werden. Wir erwarten dass die genannten Ziele erreicht werden können, indem auf Techniken aus dem Bereich des Incremental-ASP-Solving aufgebaut wird. Da existierende Techniken jedoch dem Eingabeprogramm Bedingungen auferlegt, die vom Benutzer beachtet werden müssen, ist dieser Ansatz für durchschnittliche Benutzer oft nicht direkt anwendbar. Wir planen daher, auf diese Techniken aufzubauen, sie jedoch vom Benutzer zu verbergen. Das erfordert die Analyse von Programmklassen und Instanzen, automatisches Umschreiben von Programmen, und neue Interfaces für externe Quellen. Wir erwarten von den resultierenden Algorithmen nicht nur eine bessere Skalierbarkeit, sondern aufgrund leichterer Erweiterbarkeit und Anpassbarkeit auch eine erhöhte Benutzerfreundlichkeit.

Gegenstand dieses Projekts war eine auf Logik basierende Programmiersprache, die für Anwendungen in der künstlichen Intelligenz entwickelt wurde (unter anderem für Logistik, Semantic Web, Planungsaufgaben und Robotik). Ein Kernfeature der Sprache ist dabei die Integration des Logikprogramms mit externen Quellen (Daten- oder Berechnungsquellen), wie zum Beispiel Datenbanken, Webressourcen und Routenplaner. Dies stellt für die Auswertung der Programme jedoch konzeptionell und bezüglich der notwendigen Ressourcen eine besondere Herausforderung dar. Frühere Ansätze erwiesen sich als unzureichend, da zwar das Logikprogramm und externe Quellen eng voneinander abhängen, die Auswertung bisher aber in verschiedene Teilschritte aufgespalten wurden, die nur unzureichend miteinander verzahnt waren. Insbesondere bei bestimmten Arten von Programmen zeigte sich ein nicht zufriedenstellendes Laufzeitverhalten, das in diesem Projekt durch neuartige Methoden optimiert werden sollte. Dazu wurde eine engere Integration des Logikprogramms mit den externen Quellen realisiert. Dies geschieht insbesondere indem bereits während der Auswertung des Logikprogramms intensiv auf die externen Quellen zugegriffen wird, und indem Eigenschaften von deren Entwickler bekanntgegeben und während der Auswertung genutzt werden.