Evaluierung von ASP Programming mit Externen Zugriffen

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 nichtmonotone logische Programme unter Einbeziehung externer Datenquellen. Insbesondere sollen fortgeschrittene Modellfindungs-Algorithmen für HEX-Programme entwickelt werden. 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. Derzeit werden HEX-Programme ausgewertet, indem sie in gewöhnliche Answer-Set Programme übersetzt und durch bestehende Systeme ausgewertet werden. Die Wahrheitswerte externer Atome werden dabei im Allgemeinen nichtdeterministisch generiert, um Modellkandidaten zu erzeugen. Daraufhin werden mittels Filterung jene Kandidaten eliminiert, die mit dem tatsächlichen Verhalten externer Quellen nicht übereinstimmen. Diese Strategie hat jedoch bezüglich Skalierbarkeit und Ausdruckskraft erhebliche Defizite. Zum einen werden ASP-Solver als Black Boxes verwendet, wodurch ein direktes Eingreifen in den Modellfindungsprozess verhindert wird. Das verunmöglicht eine frühzeitige Einschränkung des Suchraumes und führt zur Erzeugung vieler oft sehr ähnlicher Modell-kandidaten, die jedoch scheitern. Zum anderen erfordert die Grounding-Prozedur gängiger ASP-Solver, dass alle zu betrachtenden Grundinstanzen von Regeln im Voraus bekannt sind, wodurch die Einführung neuer Konstanten in das Programm (Value Invention) oft unmöglich ist, obwohl gerade das ein angestrebter Aspekt von HEX-Programmen ist. Zur Überwindung dieser Probleme ist ein Eingreifen in den Modellfindungssprozess unerlässlich, was wiederum nur durch die Entwicklung genuiner Algorithmen möglich ist. Auch die Entwicklung neuartiger, wesentlich aufwändigerer Grounding-Strategien ist für einen adäquaten Umgang mit Value Invention erforderlich. Es bedarf beider Entwicklungen, um die Auswertung von HEX-Programmen und deren praktischen Anwendbarkeit zu verbessern und somit das übergeordnete Ziel dieses Projektes zu erreichen. Für einige relevante Programmklassen erwarten wir bis zu exponentieller Beschleunigung der Evaluierung. Im allgemeinen Fall ist eine Vorhersage schwierig, unser Ziel ist aber eine mit gängigren ASP-Solvern vergleichbare Effizienz (modulo der Komplexität externer Quellen). Die wesentlichen Ergebnisse dieses Projekts sind neue, effiziente Modellfindungsalgorithmen für Answer-Set Programme mit externen Quellen, neuartige Methoden zur Verarbeitung von non-ground Programmen, sowie eine Prototyp-Implementierung zur Verifizierung der Skalierbarkeit basierend auf existierenden realen Anwendungen als auch neu entwickelten Benchmark-Tests. Das Projektziel soll durch eine deutliche Einschränkung des Suchraumes erreicht werden, wozu wir beispielsweise Lerntechniken aus dem SAT-Solving einsetzen wollen. Grob gesprochen lernen diese Algorithmen die Ursachen von Widersprüchen und vermeiden später die erneute Erzeugung derselben Konflikte. Derartige Strategien wurden bereits für gewöhnliche Answer-Set Programme eingesetzt. Ihre Erweiterung auf HEX-Programme ist aufgrund der Value Invention jedoch schwierig und erfordert eine detaillierte Auseinandersetzung mit dem Problem. Da praktische Programme oft nicht die volle Problemkomplexität ausschöpfen, sollen darüberhinaus theoretische Untersuchungen von Programmstrukturen vorgenommen werden, um Programmklassen zu identifizieren, die eine vereinfachte Evaluierung zulassen. Eine modulare Struktur der Evaluierungsalgorithmen soll es ermöglichen, verschiedene Algorithmen für unterschiedliche Programmklassen bereitzustellen. Ein übergeordneter Steuerungsmechanismus soll basierend auf der Struktur des Eingabeprogramms eine geeignete Algorithmenauswahl treffen. Die Prototypimplementierung wird am Ende des Projektes als öffentlich verfügbare Open-Source-Software bereit gestellt.

Dieses Projekt beschäftigte sich mit einer neueren logikorientierten Programmiersprache als Basis für Anwendungen aus dem Bereich der künstlichen Intelligenz, unter anderem intelligente Routenplanung, Linguistik-Anwendungen, Robotik und Web-Agenten. Die Anforderungen solcher Anwendungen erforderten die Integration der Programmieraprache mit anderen, möglicherweise verteilten Systemen und Datenquellen. Dies stellt für die Auswertung der Programme jedoch konzeptionell und bezüglich der notwendigen Ressourcen eine besondere Herausforderung dar.Existierende Ansätze stellten sich als unzureichend heraus, da diese nicht auf Anwendungen realistischer Größe skalieren. Weiters wurden zum Zwecke der Auswertung auch Einschränkungen der Programmiersprache in Kauf genommen, die jedoch die Benutzerfreundlichkeit reduzierten. Das Hauptziel dieses Projektes war daher die Entwicklung neuartiger Auswertungsmethoden, durch die einerseits eine höhere Effizienz und andererseits mehr Flexibilität durch eine Reduktion der Einschränkungen erreicht werden sollte.Das Ergebnis dieses Projekts ist eine Reihe neuartiger Auswertungsstrategien, die auch in einem frei verfügbaren Prototypensystem umgesetzt wurden. Eine experimentelle Analyse bestätigte das Erreichen der vorgesehenen Projektziele. Weiters wurde das System auch für reale Anwendungen herangezogen, unter anderem für die oben genannten, wodurch auch der praktische Nutzen nachgewiesen wurde.