Answer-Set Programming Erweiterungen für Problemlösungen auf Zerlegungen

Das Formalisieren und Implementieren von komplexen Problemen des logischen Schießens erfordert nicht nur ausdrucksstarke deklarative Sprachen sondern auch spezielle dem jeweiligen Problem angepasste Algorithmen. Insbesondere sollen letztere dazu geeignet sein, Ergebnisse auch für große Instanzen von Problemstellungen aus der Praxis schnell zu liefern. Solche Instanzen haben oftmals eine spezielle Struktur, welche ausgenutzt werden kann, um sogar NP-schwere Probleme effizient zu lösen. Ein weit verbreiteter Ansatz zur Strukturausnutzung sind sogenannte Baumzerlegungen. Hier können mithilfe von dynamischer Programmierung Lösungen effizient berechnet werden, solange der strukturelle Parameter Baumweite beschränkt ist. Grob gesagt beschreibt die Baumweite, inwiefern die der Probleminstanz zugrundeliegende Graphstruktur einem Baum ähnelt. Empirische Studien zeigen, dass bei vielen praktischen Anwendungen (zum Beispiel in der Bio-Informatik oder Sozialen Netzwerken) die Baumweite tatsächlich klein ist. Allerdings werden die entsprechenden auf dynamischer Programmierung basierenden Algorithmen normalerweise für jedes Problem von Grund auf neu entwickelt, da deklarative Sprachen im Allgemeinen nicht auf Zerlegungen ausgelegt sind. Momentan fehlt es an einer brauchbaren Kombination von deklarativen Sprachen und strukturellen Methoden. In diesem Projekt beschäftigen wir uns mit der Kombination beider Paradigmen, wobei Answer-Set Programming (ASP) zur Lösung von Problemen auf Baumzerlegungen verwendet wird. Innerhalb der KI ist ASP ein etablierter Formalismus, für den technisch ausgereifte Systeme zur Verfügung stehen. Insbesondere unterstützt ASP die Methodik des Guess & Check, welche auch NP-harten Problemen zugrundeliegt. Dies erlaubt es, solche Probleme kurz und prägnant in ASP zu spezifizieren. Unser Ziel ist es, ein neues Paradigma namens Decompose, Guess & Check zu etablieren, wo Algorithmen, basierend auf dynamischer Programmierung, deklarativ in ASP spezifiziert und effizient auf Baumzerlegungen gelöst werden können. Zu diesem Zweck werden wir im Rahmen des Projekts (i) zeigen, dass jedes Problem, welches auf Basis von Courcelles Theorem effizient bezüglich Strukturen mit beschränkter Baumweite gelöst werden kann, auch von uns effizient gelöst werden kann; (ii) eine Software entwickeln, die sowohl existierende Tools zur Erzeugung von Baumzerlegungen als auch ASP-Systeme kombiniert, sodass sich AnwenderInnen allein auf die Algorithmusentwicklung fokussieren können; (iii) Fallstudien durchführen, welche die Verwendbarkeit und Nützlichkeit des neuen Paradigmas bezüglich realer Probleme belegen.

Das Formalisieren und Implementieren von komplexen Problemen des logischen Schließens erfordert nicht nur ausdrucksstarke deklarative Sprachen, sondern auch spezielle dem jeweiligen Problem angepasste Algorithmen. Insbesondere sollen letztere dazu geeignet sein, Ergebnisse auch für große Instanzen von Problemstellungen aus der Praxis schnell zu liefern. Solche Instanzen haben oftmals eine spezielle Struktur, welche ausgenutzt werden kann, um sogar NP-schwere Probleme effizient zu lösen. Ein weit verbreiteter Ansatz zur Strukturausnutzung sind sogenannte Baumzerlegungen. Hier können mithilfe von dynamischer Programmierung Lösungen effizient berechnet werden, solange der strukturelle Parameter Baumweite beschränkt ist. Grob gesagt beschreibt die Baumweite, inwiefern die der Probleminstanz zugrundeliegende Graphstruktur einem Baum ähnelt. Empirische Studien zeigen, dass bei vielen praktischen Anwendungen (zum Beispiel in der Bio-Informatik oder bei Sozialen Netzwerken) die Baumweite tatsächlich klein ist. Allerdings werden die entsprechenden auf dynamischer Programmierung basierenden Algorithmen normalerweise für jedes Problem von Grund auf neu entwickelt, da deklarative Sprachen im Allgemeinen nicht auf Zerlegungen ausgelegt sind.Ziel des Projekts war die Entwicklung eines Systems das die Vorteile von deklarativen Sprachen und strukturellen Methoden verbindet, also eine Kombination beider Paradigmen, wobei Answer-Set Programming (ASP) zur Lösung von Problemen auf Baumzerlegungen verwendet wird. Innerhalb der KI ist ASP ein etablierter Formalismus, für den technisch ausgereifte Systeme zur Verfügung stehen. Insbesondere unterstützt ASP die Methodik des Guess & Check, welche auch NP-harten Problemen zugrundeliegt. Dies erlaubt es, solche Probleme kurz und prägnant in ASP zu spezifizieren.Dies führte uns zu einem neuen Paradigma namens Decompose, Guess & Check, wo Algorithmen, basierend auf dynamischer Programmierung, deklarativ in ASP spezifiziert und effizient auf Baumzerlegungen gelöst werden können. Mit dem D-FLAT System haben wir ein System entwickelt, welches diese Methode implementiert. Die BenutzerInnen müssen sich hier lediglich um die Beschreibung des dynamischen Algorithmus kümmern, während das System notwendige Aufgaben, wie das Berechnen der Baumzerlegung sowie die Kombination von partiellen Lösungen der Subprobleme, selbstständig erledigt. Im Zuge des Projekts wurde sowohl die theoretische Ausdrucksstärke dieses Ansatzes, als auch seine praktische Effizienz in diversen Problemdomänen untersucht. Die Erkenntnisse, die wir im Rahmen des Projekts gewinnen konnten, sind in der Zwischenzeit in die Entwicklung weiterer, spezialisierterer Systeme, die dynamische Programmierung zur Lösung berechnungsintensiver Probleme wie z.B. quantifizierte Aussagenlogik, eingeflossen. Projektseite: http://dbai.tuwien.ac.at/research/project/dflat/