Towards Advanced Systems for Abstract Argumentation

Abstract

Within the last years, and in particular due to the first edition of the International Competition on Computational Models of Argumentation (ICCMA) in 2015, the field of formal argumentation has seen an increasing number of systems for Dung's abstract argumentation framework. However, the majority of the current approaches rely on reductions to other solving paradigms like SAT-solving and Answer-Set Programming, thus leaving genuine features of abstract argumentation rather unexploited. In this talk, we present a few directions for the development of next-generation argumentation systems that take recent theoretical advances into account and discuss challenges as well as potential pitfalls in this endeavor.

Keywords

• Abstract argumentation Computational models Argumentation systems

-

to not occur together in any extension of the given AF, an attack between these arguments can be added to the AF without changing its extensions. Such a behavior would mimic the well-known concept of conflict-driven clause learning [ 7 ] which proved extremely successful in SAT-solvers. We will show that the conjecture does not hold for several semantics, following the presentation in [ 8 ]. Hence, conflict learning in abstract argumentation needs additional care, but it is open under which situations such a form of optimization (which explicitly tells the solver that an observed conflict between two arguments is given) can be faithfully applied.

Second, we will discuss certain ways how the mentioned multitude of semantics can be exploited in practice. Indeed, a folklore approach is to first compute the grounded extension (which is the minimal complete one and thus contained in all preferred and stable extensions), reduce the AF accordingly, and finally compute the required extensions, see, e.g., [ 9 ]. Another approach is to try to make smart use of the fact that, e.g., preferred extensions are the subset-maximal admissible (and complete) ones. Cegartix [ 10 ] and ArgSemSAT [ 11 ] are examples of systems that use this fact and try to navigate towards preferred extensions using several calls to SAT or ASP solvers. Therefore these systems can be seen as a combination of the reduction-based method with genuine argumentation methodology. However, a more fine-grained picture about the relationship between semantics is given by so-called two-dimensional signatures [ 12 ], which we shall focus on here. For instance, such a signature for stable and preferred semantics is just defined as S ST,PR = {(ST(F ), PR(F )) | F is an AF }, where ST(F ) (resp. PR(F )) denotes the stable, resp. preferred, extensionsof F . Knowing the exact shape of this signature might yield shortcuts in systems for computing preferred extensions (recall that each stable extension is also preferred): Since stable extensions are known to be easier to compute, one could start with enumerating stable extensions and then, by looking up S ST,PR, the search space for the remaining preferred extension could be pruned. As an example, the actual characterization of S ST,PR shows that in case one has found {a, b} and some S [ {a} as stable (and therefore also preferred) extensions of a given AF, one can safely exclude any S0 [ {b} with S \ S0 6= 0/ as candidates for possible preferred extensions. In the talk, we will review results concerning two-dimensional signatures for several semantics and discuss their possible implications in practice.

Finally, we shall also briefly review other methods that have been studied. On the one hand, dialogues (see, e.g., [ 13,14,15 ]) and advanced labeling algorithms (see, e.g., [ 16 ]) have been explored as a tool to derive extensions. On the other hand, there are several approaches that take the topology of the AF into account (see, e.g., [ 17,9,18 ] for SCC-based techniques; [ 19 ] for splitting; [ 20 ] for partial evaluation; [ 21 ] for a dedicated algorithm on bipartite AFs; or [ 22 ] for dynamic programming on tree decompositions of AFs).

Acknowledgments. The results that will be discussed in the talk originated from joint work with several co-authors, whom I would like to mention here and express my gratitude to for the fruitful collaborations: Ringo Baumann, Paul Dunne, Wolfgang Dvorˇa´k, Matti Ja¨rvisalo, Thomas Linsbichler, Christof Spanring, Hannes Straß and Johannes Wallner.

This work has been supported by the Austrian Science Fund (FWF) through projects Y698, I1102 and I2854.

References

[1] Bench-Capon , T.J.M. , Dunne , P.E. : Argumentation in Artificial Intelligence. Artif. Intell . 171 ( 2007 ) 619 - 641

[2] Dung , P.M. : On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games . Artif. Intell . 77 ( 1995 ) 321 - 358

[3] Baroni , P. , Caminada , M. , Giacomin , M.: An introduction to argumentation semantics . The Knowledge Engineering Review 26 ( 2011 ) 365 - 410

[4] Thimm , M. , Villata , S. , Cerutti , F. , Oren , N. , Strass , H. , Vallati , M. : Summary report of the first international competition on computational models of argumentation . AI Magazine 37 ( 2016 ) 102 - 104

[5] Charwat , G. , Dvorˇa´ k, W., Gaggl , S.A. , Wallner , J.P. , Woltran , S. : Methods for solving reasoning problems in abstract argumentation - a survey . Artif. Intell . 220 ( 2015 ) 28 - 63

[6] Baumann , R. , Dvorˇa´ k, W., Linsbichler , T. , Strass , H. , Woltran , S. : Compact argumentation frameworks . In Schaub, T., Friedrich , G. , O 'Sullivan , B., eds. : Proc. ECAI. Volume 263 of Frontiers in Artificial Intelligence and Applications ., IOS Press ( 2014 ) 69 - 74

[7] Silva , J.P.M. , Lynce , I. , Malik , S. : Conflict-driven clause learning SAT solvers . In Biere, A. , Heule , M., van Maaren, H. , Walsh , T., eds.: Handbook of Satisfiability. Volume 185 of Frontiers in Artificial Intelligence and Applications . IOS Press ( 2009 ) 131 - 153

[8] Linsbichler , T. , Spanring , C. , Woltran , S.: The hidden power of abstract argumentation semantics . In Black, E., Modgil , S. , Oren , N., eds. : Proc. TAFA . Volume 9524 of Lecture Notes in Computer Science., Springer ( 2015 ) 146 - 162

[9] Cerutti , F. , Giacomin , M. , Vallati , M. , Zanella , M.: An SCC recursive meta-algorithm for computing preferred labellings in abstract argumentation . In Baral, C. , Giacomo , G.D. , Eiter , T., eds. : Proc. KR , AAAI Press ( 2014 ) 42 - 51

[10] Dvorˇa´k, W., Ja¨rvisalo, M. , Wallner , J.P. , Woltran , S. : Complexity-sensitive decision procedures for abstract argumentation . Artif. Intell . 206 ( 2014 ) 53 - 78

[11] Cerutti , F. , Giacomin , M. , Vallati , M.: ArgSemSAT: Solving argumentation problems using SAT . In Parsons, S., Oren , N. , Reed , C. , Cerutti , F., eds. : Proc. COMMA. Volume 266 of Frontiers in Artificial Intelligence and Applications ., IOS Press ( 2014 ) 455 - 456

[12] Dunne , P.E. , Spanring , C. , Linsbichler , T. , Woltran , S. : Investigating the relationship between argumentation semantics via signatures . In Kambhampati, S., ed. : Proc. IJCAI , IJCAI/AAAI Press ( 2016 ) 1051 - 1057

[13] Modgil , S. , Caminada , M. : Proof theories and algorithms for abstract argumentation frameworks . In Rahwan, I., Simari , G .R., eds. : Argumentation in Artificial Intelligence . Springer ( 2009 ) 105 - 132

[14] Thang , P.M. , Dung , P.M. , Hung , N.D. : Towards a common framework for dialectical proof procedures in abstract argumentation . J. Log. Comput . 19 ( 2009 ) 1071 - 1109

[15] Verheij , B. : A labeling approach to the computation of credulous acceptance in argumentation . In Veloso, M.M., ed. : Proc. IJCAI . ( 2007 ) 623 - 628

[16] Nofal , S. , Atkinson , K. , Dunne , P.E. : Looking-ahead in backtracking algorithms for abstract argumentation . Int. J. Approx. Reasoning 78 ( 2016 ) 265 - 282

[17] Baroni , P. , Giacomin , M. , Liao , B. : On topology-related properties of abstract argumentation semantics. A correction and extension to dynamics of argumentation systems: A division-based method . Artif. Intell . 212 ( 2014 ) 104 - 115

[18] Cerutti , F. , Tachmazidis , I. , Vallati , M. , Batsakis , S. , Giacomin , M. , Antoniou , G.: Exploiting parallelism for hard problems in abstract argumentation . In Bonet, B. , Koenig , S., eds. : Proc. AAAI , AAAI Press ( 2015 ) 1475 - 1481

[19] Baumann , R. , Brewka , G. , Dvorˇa´ k, W., Woltran , S. : Parameterized splitting: A simple modificationbased approach . In Erdem, E., Lee , J. , Lierler , Y. , Pearce , D., eds.: Correct Reasoning - Essays on Logic-Based AI in Honour of Vladimir Lifschitz . Volume 7265 of Lecture Notes in Computer Science., Springer ( 2012 ) 57 - 71

[20] Liao , B. , Huang , H.: Partial semantics of argumentation: basic properties and empirical results . J. Log. Comput . 23 ( 2013 ) 541 - 562

[21] Dunne , P.E. : Computational properties of argument systems satisfying graph-theoretic constraints . Artif. Intell . 171 ( 2007 ) 701 - 729

[22] Dvorˇa´k, W., Pichler , R. , Woltran , S. : Towards fixed-parameter tractable algorithms for abstract argumentation . Artif. Intell . 186 ( 2012 ) 1 - 37