=Paper=
{{Paper
|id=Vol-1672/woltran
|storemode=property
|title=Towards Advanced Systems for Abstract Argumentation
|pdfUrl=https://ceur-ws.org/Vol-1672/woltran.pdf
|volume=Vol-1672
|authors=Stefan Woltran
|dblpUrl=https://dblp.org/rec/conf/comma/Woltran16
}}
==Towards Advanced Systems for Abstract Argumentation==
https://ceur-ws.org/Vol-1672/woltran.pdf
Towards Advanced Systems for
Abstract Argumentation
Stefan WOLTRAN
Institute of Information Systems, TU Wien, Austria
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
Within Artificial Intelligence, argumentation has become one of the major fields
over the last two decades [1]. In particular, abstract argumentation frameworks (AFs)
introduced by Dung [2] are a simple, yet powerful formalism for modeling and decid-
ing argumentation problems that are integral to many advanced argumentation systems.
Evaluating AFs is done via so-called semantics (cf. [3] for an overview) that deliver sub-
sets of jointly acceptable arguments. In contrast to other communities, the multitude of
semantics is seen as a virtue of formal argumentation rather than a weakness. Conse-
quently, systems for abstract argumentation are expected to deal with, and even exploit,
this particular fact.
In 2015, the first edition of the International Competition on Computational Models
of Argumentation (ICCMA) [4] took place and compared the performance of 18 sub-
mitted solvers1 . For ICCMA’15, four semantics were taken into account. For the next
edition of ICCMA2 , three further semantics will be considered. As it turned out, the top-
ranked systems in ICCMA’15 are based on reductions to other paradigms like proposi-
tional SAT-solving, Answer-Set Programming or Constraint Satisfaction (see [5] for an
overview of such methods).
In this talk, we want to focus on two recent research directions in the field of abstract
argumentation, which seem appropriate to be integrated to existing systems:
First, we review the Explicit Conflict Conjecture, originally proposed in [6] for stable
semantics. In a nutshell, this conjecture states that whenever two arguments are known
1 http://argumentationcompetition.org/2015
2 http://www.dbai.tuwien.ac.at/iccma17/
1
to not occur together in any extension of the given AF, an attack between these argu-
ments 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 ex-
tremely 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 ex-
tension (which is the minimal complete one and thus contained in all preferred and sta-
ble 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 argumenta-
tion 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 SST,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 ex-
tension 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 SST,PR , the search
space for the remaining preferred extension could be pruned. As an example, the actual
characterization of SST,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 grat-
itude to for the fruitful collaborations: Ringo Baumann, Paul Dunne, Wolfgang Dvořák,
Matti Jä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.
2
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 interna-
tional competition on computational models of argumentation. AI Magazine 37 (2016) 102–104
[5] Charwat, G., Dvořák, W., Gaggl, S.A., Wallner, J.P., Woltran, S.: Methods for solving reasoning prob-
lems in abstract argumentation - a survey. Artif. Intell. 220 (2015) 28–63
[6] Baumann, R., Dvořá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] Dvořák, W., Jä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 argu-
mentation 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 argumen-
tation. 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., Dvořák, W., Woltran, S.: Parameterized splitting: A simple modification-
based 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] Dvořák, W., Pichler, R., Woltran, S.: Towards fixed-parameter tractable algorithms for abstract argu-
mentation. Artif. Intell. 186 (2012) 1–37
3