Solving argumentation frameworks using answer set programming

Abstract

Im Laufe der letzten Jahre hat sich Argumentation zu einem zentralen Gebiet in der Kuenstlichen Intelligenz (KI) etabliert. Dung fuehrte 1995 Argumentation Frameworks (AFs) als ein formales System ein, das es einem ermoeglicht, aus widersprüchlichem Wissen Schluesse zu folgern. Desweiteren hat er mehrere Semantiken definiert, wie zum Beispiel admissible, complete, preferred und grounded, mit deren Hilfe man Mengen von zulaessigen Argumenten berechnen kann.<br />Obwohl das Framework von Dung bereits sehr viele Moeglichkeiten zur Verfuegung stellt um Aussagen ueber Argumente zu treffen, wurde es kontinuierlich erweitert und verfeinert. Bis jetzt wurden viele weitere Semantiken eingefuehrt, wie zum Beispiel s-admissible, c-admissible, semi-stable, prudent und ideal. Zudem wurde auch das Framework durch Praeferenzrelationen (PAFs), Werte (VAFs) und Unterstuezungsrelationen (BAFs) erweitert. All das fuehrt dazu, dass wir mit unterschiedlichen Frameworks und Semantiken geradezu ueberschuettet werden.<br />Ein Bestandteil dieser Arbeit und Voraussetzung fuer eine elegante Implementierung ist das Erkennen der relevanten und vielversprechenden Frameworks und Semantiken, und das Vereinheitlichen der unterschiedlichen Definitionen. Trotz ausgiebiger Forschung auf diesem Gebiet gibt es noch immer kein System, mit dem man alle grundlegenden Semantiken von Dung berechnen kann.<br />Daher war der Hauptbestandteil dieser Masterarbeit, ein System zu entwickeln, mit dessen Hilfe man alle Semantiken fuer Dungs Framework, sowie die wichtigsten fuer PAFs, VAFs und BAFs berechen kann. Unser System ASPARTIX, welches fuer "Answer Set Programming Argumentation Reasoning Tool" steht, zeichnet sich dadurch aus, dass es aus einem fixen disjunktiven logischen Programm besteht, welches vollkommen unabhaengig vom jeweiligen Argumentation Framework ist. Das bedeutet, dass der Benutzer nur das Framework und die gewuenschte Semantik als Eingabedatenbank spezifizieren muss. Daher kann ASPARTIX auf einfache Weise verwendet werden, um die Unterschiede und Zusammenhaenge der verschiedenen Semantiken und Frameworks zu erforschen. Die Modularitaet unseres Systems ermoeglicht eine einfache Erweiterung und Verbesserung.<br />

Within the last years, argumentation has become a very important field in Artificial Intelligence (AI). In 1995, Dung introduced Argumentation Frameworks (AFs) as a formal system to reason over conflicting knowledge. He defined several semantics (i.e., admissible, complete, preferred and grounded) for AFs to compute acceptable sets of arguments. Even though Dung's framework offers many possibilities for reasoning over arguments, it has been extended continuously. Till now, many more semantics (i.e., s-admissible, c-admissible, semi-stable, prudent, ideal) have been introduced. Also the basic framework has been extended by, for example, preference relations (PAFs), values (VAFs) and support relations (BAFs), just to name some of them. All these extensions lead to the fact that we are overwhelmed with different frameworks and semantics. One part of this work is to filter out the most relevant/promising frameworks and semantics and to bring all those definitions into a uniform notation. Such a uniform notation is a prerequisite for an elegant implementation. Despite a constant research effort in this area, there exists neither an implementation for computing all semantics of Dung's original framework nor implementations for the extensions thereof.<br />The main part of this thesis is to develop a system to compute all semantics of Dung's framework, as well as the most relevant ones for PAFs, VAFs and BAFs. Our system ASPARTIX, which stands for Answer Set Programming Argumentation Reasoning Tool, is exceptional due to the fact that it is a fixed disjunctive logic program, totally independent of the concrete AF. This means that the user just needs to set up the framework and the desired semantic as an input database. It is not necessary to make any translation of the framework or to modify the system. This makes it easy for researchers to use ASPARTIX to compare the different semantics and frameworks even if the user is not an expert in answer set programming. Due to the modularity of our system, it is easy to extend and debug.