dynASP : a dynamic programming-based answer set programming solver

Abstract

Answer Set Programming (ASP) is nowadays a well known and well acknowledged paradigm for declarative problem solving as can be seen by many successful applications in the areas of artificial intelligence and knowledge-based reasoning.<br />Evaluating logic programs that follow the ASP paradigm is usually implemented as a two-step procedure: First, the grounding step (i.e. the instantiation of variables occurring in the program) and second, the actual solving process which works on ground logic programs. In this thesis we introduce a novel approach for dealing with the latter.<br />Solving ground logic programs is, in general, still an intractable problem. Therefore most standard ASP solvers rely on techniques originating in SAT solving or constraint satisfaction problem solving. In contrast, the algorithm presented in this thesis was developed with techniques that stem from parameterized complexity theory. The idea here is to consider a certain problem parameter as bounded by a constant and thereby obtain a tractability result for the given problem. One such parameter which has lead to many interesting results is treewidth which represents the "tree- likeness" of a graph. Treewidth is defined in terms of tree decompositions which in turn can be used by dynamic programming algorithms to solve the problem under consideration.<br />We introduce a novel dynamic programming algorithm based on the above approach that is specifically tailored for solving head-cycle free logic programs. Using a purpose-built framework for algorithms on tree decompositions, an actual implementation of the algorithm is presented, carefully evaluated and compared to existing ASP solvers. Experimental results show significant potential for problem instances of low treewidth.<br />

Answer Set Programming (ASP) ist heutzutage ein bekanntes und etabliertes Paradigma für deklarativeWissensverarbeitung und wurde bereits in mehreren Gebieten (z.B. im Bereich der künstliche Intelligenz oder der wissensbasierten Sys- teme) erfolgreich eingesetzt. Grundsätzlich ist die Auswertung von logischen Pro grammen ein zweistufiges Verfahren: In einem ersten Schritt werden alle Regeln des Programmes grundiert (d.h. falls Variablen in diesen Regeln vorhanden sind, werden sie durch konkrete Werte ersetzt). Erst im zweiten Schritt erfolgt dann die eigentliche Auswertung des Programmes, da Algorithmen für diesen Schritt nur auf grundierten Programmen arbeiten. In dieser Arbeit stellen wir einen neuen Ansatz für letzteren Schritt vor.<br />Das Auswerten von Logikprogrammen ist grundsätzlich eine aufwendige Aufgabe. Für ähnlich schwere Probleme im Bereich des SAT-Solvings bzw.<br />im Bereich von Constraint Satisfaction wurden bereits erfolgreich effiziente Algorithmen gefunden, weswegen die meisten modernen Algorithmen für ASP auf Techniken aus diesem Bereich aufbauen. Im Gegensatz dazu setzt der in dieser Arbeit präsentierte Algorithmus auf ein neues Prinzip, das auf Ergebnissen aus der parametrisierten Komplexitätstheorie basiert. Hierbei wird ein bestimmter Problemparameter fixiert, wodurch das Problem im Allgemeinen leichter lösbar wird. Ein solcher Parameter ist die sg. "Treewidth", die, grob gesprochen, die "Baumähnlichkeit" eines Graphen beschreibt. Sie wird mit Hilfe von Tree Decompositions definiert, auf welchen der hier vorgestellte Algorithmus aufbaut.<br />Dieser Algorithmus, der auf obigem Prinzip und dynamischer Programmierung basiert, ist speziell auf die Klasse der sg. "head-cycle-freien" logischen Programme zugeschnitten. Mit Hilfe eines eigens entwickelten Frameworks für Algorithmen und Tree Decompositions wurde der Algorithmus implementiert und anschließend ausführlich getestet. Experimentelle Ergebnisse zeigen großes Potential für Probleme mit kleinen Parameterwerten (d.h. mit kleiner Treewidth).<br />