A comprehensive analysis of the cf2 argumentation semantics : from characterization to implementation

Abstract

Argumentation ist ein wichtiges Forschungsfeld der Künstlichen Intelligenz. Zahlreiche Anwendungen in den Bereichen Legal Reasoning, Multi-Agenten Systeme, Soziale Netzwerke, E-Government, Decision Support und viele weitere machen dieses Gebiet sehr interdisziplinär und führen zu einer Vielzahl von Formalisierungen. Dabei hat sich das Konzept der Abstract Argumentation Frameworks (AFs) zu einem der beliebtesten Ansätze entwickelt. Dieses relativ einfache aber sehr ausdrucksstarke Model wurde im Jahre 1995 von Phan Minh Dung eingeführt. Dabei stellen Argumente und eine binäre Relation zwischen den Argumenten, genannt Attacken, die einzigen Komponenten dar um eine große Anzahl von Problemstellungen zu behandeln.<br />Mittlerweile existieren sehr viele Semantiken um die Konflikte zwischen den Argumenten zu lösen und zulässige Mengen von Argumenten auszuwählen.<br />Abhängig von der jeweiligen Anwendung genügen diese Semantiken unterschiedlichen Anforderungen. Einige basieren auf dem Konzept, dass Argumente gegen Attacken verteidigt werden, wohingegen bei anderen die Lösungen durch konsistente Mengen von Argumenten gegeben sind. Eine systematische Analyse dieser Semantiken, sowohl auf theoretischer als auch auf praktischer Ebene, ist unabdingbar um wettbewerbsfähige Systeme zu entwickeln. Dazu gehören die Komplexitätsanalyse um geeignete Algorithmen zu designen, die Untersuchung des Verhaltens an konkreten Instanzen und auch die Identifizierung von möglichen Redundanzen zur Vereinfachung der Frameworks.<br />In dieser Arbeit werden wir eine solche Analyse anhand der cf2 Semantik durchführen. Diese Semantik basiert auf einer Zerlegung des Frameworks entlang seiner stark zusammenhängenden Komponenten, wobei das Konzept der Verteidigung der Argumente gegen Attacken vernachlässigt wird. Die cf2 Semantik hat den speziellen Vorteil, dass sie mit Zyklen ungerader Länge sensibler umgehen kann als andere Semantiken. Dadurch kann die cf2 Semantik auch für AFs eingesetzt werden, die sowohl Zyklen gerader als auch ungerader Länge aufweisen.<br />Da jedoch die Definition dieser Semantik relativ kompliziert ist wurde sie bis jetzt noch nicht besonders ausführlich in der Literatur behandelt.<br />Um die weitere Untersuchung zu erleichtern führen wir eine alternative Charakterisierung der cf2 Semantik ein. Dann stellen wir eine geringfügige Abänderung vor, um ein gewisses problematisches Verhalten an speziellen Instanzen zu beheben, welche zu der verwandten stage2 Semantik führt. Nach einer umfassenden Komplexitätsanalyse und der Untersuchung von Äquivalenzen für diese beiden Semantiken, wenden wir die erlangten Resultate für zwei unterschiedlichen Implementierungsmethoden an, nämlich in Form von Answer-Set Programming und von Algorithmen die auf der Berechnung von Labelings basieren.<br />

Argumentation is one of the major fields in Artificial Intelligence (AI). Numerous applications in diverse domains like legal reasoning, multi-agent systems, social networks, e-government, decision support and many more make this topic very interdisciplinary and lead to a wide range of different formalizations. Out of them the concept of abstract Argumentation Frameworks (AFs) is one of the most popular approaches to capture certain aspects of argumentation. This very simple yet expressive model has been introduced by Phan Minh Dung in 1995. Arguments and a binary attack relation between them, denoting conflicts, are the only components one needs for the representation of a wide range of problems and the reasoning therein.<br />Nowadays numerous semantics exist to solve the inherent conflicts between the arguments by selecting sets of "acceptable" arguments.<br />Depending on the application, acceptability is defined in different ways. Some semantics are based on the idea to defend arguments against attacks, while others treat arguments like different choices and the solutions stand for consistent sets of arguments. A systematic analysis of these semantics on a theoretical and practical level is indispensable for the development of competitive systems. This includes a complete complexity analysis to develop appropriate algorithms and systems, the verification of the behavior on concrete instances as well as the identification of possible redundancies for specific semantics to simplify the frameworks.<br />In this thesis we exemplify such an analysis on the cf2 semantics which does not require to defend arguments against attacks but is based on a decomposition of the framework along its strongly connected components (SCCs). This allows to treat cycles in a more sensitive way than others and to overcome some problems which arise with odd- and even-length cycles. Due to the quite complicated definition of this semantics it has not been studied very intensively.<br />To facilitate further investigation steps we first introduce an alternative characterization of the cf2 semantics. Then we propose a small modification of this semantics to overcome a particular problematic behavior on specific instances which results in the sibling semantics stage2. After a complete complexity analysis and the investigation of equivalences for these two semantics, we apply the obtained results on two different implementation methods, namely the reduction-based approach of answer-set programming and the direct implementation in terms of labeling-based algorithms.<br />