Abstract argumentation and answer-set programming : modelling the resolution-based grounded semantics

Abstract

Seit seiner Entstehung im 20. Jahrhundert hat das Feld der Argumentation innerhalb der KI ein deutliches Wachstum erlebt. Ein zentrales Thema ist die Akzeptanz von Argumenten für die P. M. Dung [19] eine neue Theorie, welche auf dem Begriff der Abstract Argumentation Fra- meworks beruht, entwickelt hat. Diese Frameworks bestehen aus zwei Mengen: einer Menge von Argumenten und einer binären Relation, welche die Angriffe - auch Attacks gennant - dar- stellt. Diese Argumente besitzen jedoch keine innere Struktur, daher auch der Name Abstract Argumentation. Da sich Argumente gegenseitig attackieren können, sind nicht alle Argumente gemeinsam haltbar. Aus diesem Grund wendet man auf die Argumente eine Evaluierungsme- thode an, welche auch als Semantik bezeichnet wird. Diese Methode kann entweder deklara- tiv oder prozedural sein. Um diese Semantiken vergleichen zu können, wurden einige formale Prinzipien definiert [6], die von einer einzelnen Extension oder der ganzen Menge von Exten- sionen einer Semantik erfüllt werden können. In ihrer Arbeit On the resolution-based family of abstract argumentation semantics and its grounded instance [5] haben P.<br />Baroni, P. E. Dun- ne, und M. Giacomin eine neue Familie von Semantiken für Abstract Argumentation Systeme eingeführt. Unter diesen Semantiken befindet sich die Resolution-Based Grounded Semantics, welche die einzigartige Eigenschaft hat, alle formalen Prinzipien zu erfüllen, die in ihrer bereits erwähnten Arbeit [6] präsentiert wurden. Im Bereich der Answer Set Programmierung wurden bereits Kodierungen dieser neuen Semantik entwickelt. Answer Set Programming (ASP) [39], ist eine deklarative Programmiersprache, welche für komplexe Suchprobleme entwickelt wur- de. Diese Programmiersprache basiert auf der Stable Model Semantics, welche von M. Gelfond und V. Lifschitz [36] eingeführt wurde. Die existierenden Kodierungen leiden jedoch noch unter Performance Problemen, weshalb wir es uns zur Aufgabe gemacht haben ein eigenes ASP Pro- gramm mit besserer Leistung zu entwickeln. Unsere Kodierung basiert auf einem Algorithmus, der von P. Baroni und M.<br />Giacomin [6] präsentiert wurde. Diese Kodierungen sollen dann im ASPARTIX System einbindbar sein, welches von U. Egly et al. [25] entwickelt wurde. Des wei- teren versuchen wir jene Code-Segmente und Optimierungen zu identifizieren, welche zu einer Leistungssteigerung bei der Berechnung der Extensionen führen.<br />

Since its emergence in the 20th century, the field of argumentation in Artificial Intelligence (AI) has experienced significant growth. One central topic within this field is the acceptability of arguments for which P. M. Dung [19] introduced a theory based on the notion of abstract ar- gumentation frameworks. These frameworks are simply consisting of a set of arguments and a binary relation constituting attacks, without any inner structure. Since arguments may at- tack each other, it is the case that not all of them might be able to stand together. Therefore, arguments are subject to an evaluation method, of which the formal definition is called an argu- mentation semantics . This method can either be declarative or procedural. In order to be able to compare those semantics, several formal principles have been defined [6] which should be fulfilled by a single extension or the whole set of extensions of a semantics. In their paper On the resolution-based family of abstract argumentation semantics and its grounded instance [5] P. Baroni, P. E. Dunne and M. Giacomin introduced a new family of semantics for abstract argu- mentation systems, among them the resolution-based grounded semantics, which has the unique property of satisfying all principles. There have already been encodings developed within the realm of answer-set programming (ASP) [39], a form of declarative programming oriented to- wards difficult search problems and based on the stable model semantics as presented by M. Gel- fond and V. Lifschitz [36]. Yet there are still performance problems with the encodings of this particular semantics.<br />Our task is to develop ASP encodings, based on an algorithm presented by P. Baroni and M. Giacomin [6] that compute the extensions of this semantics and provide performance gains compared to existing approaches.<br />These encodings shall then be incorpo- rated in the ASPARTIX system, introduced by U. Egly et al. [25]. Furthermore, we keep track of any optimizations which result in a performance gain since they might be applicable on other semantics as well.