Abstract Argumentation Frameworks - From Theoretical Insights to Practical Implications

Linsbichler, Thomas

Abstract Argumentation Frameworks - From Theoretical Insights to Practical Implications

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Doctoral Consortium. Pages 4377-4377.

Abstract

Abstract argumentation frameworks (AFs) are one of the central formalisms in AI; equipped with a wide range of semantics, they have proven useful in several application domains. In the thesis we want to complete and extend the recent study on expressiveness of argumentation semantics and use these and other theoretical results for implementations of reasoning tasks in AFs. Moreover, we plan to utilize results on realizability in dynamic scenarios of abstract argumentation, such as revision of argumentation frameworks. Hereby, the knowledge of which extensions can occur together is of central interest when trying to achieve a certain outcome. In other words, the ultimate goal of the thesis is to gain theoretical insights on argumentation semantics in order to employ them in practically efficient reasoning systems for both the evaluation and evolution of AFs.

[Alchourrón et al., 1985] Carlos E. Alchourrón, Peter Gärdenfors, and David Makinson. On the logic of theory change: partial meet contraction and revision functions. J. Symb. Log., 50(2):510-530, 1985.
[Baroni and Giacomin, 2007] Pietro Baroni and Massimiliano Gia- comin. On principle-based evaluation of extension-based argu- mentation semantics. Artif. Intell., 171(10-15):675-700, 2007.
[Baroni et al., 2011a] Pietro Baroni, Martin Caminada, and Massi- miliano Giacomin. An introduction to argumentation semantics. Knowledge Eng. Review, 26(4):365-410, 2011.
[Baroni et al., 2011b] Pietro Baroni, Paul E. Dunne, and Massim- iliano Giacomin. On the resolution-based family of abstract ar- gumentation semantics and its grounded instance. Artif. Intell., 175(3-4):791-813, 2011.
[Baroni et al., 2014] Pietro Baroni, Guido Boella, Federico Cerutti, Massimiliano Giacomin, Leendert van der Torre, and Serena Vil- lata. On the Input/Output behaviour of argumentation frameworks. Artif. Intell., 217:144-197, 2014.
[Baumann et al., 2014] Ringo Baumann, Wolfgang Dvořák, Thomas Linsbichler, Hannes Strass, and Stefan Woltran. Compact argumentation frameworks. In Proc. ECAI, pages 69-74, 2014.
[Bench-Capon and Dunne, 2007] Trevor J. M. Bench-Capon and Paul E. Dunne. Argumentation in artificial intelligence. Artif. Intell., 171(10-15):619-641, 2007.
[Booth et al., 2013] Richard Booth, Souhila Kaci, Tjitze Rienstra, and Leendert van der Torre. A logical theory about dynamics in abstract argumentation. In Proc. SUM, pages 148-161, 2013.
[Caminada and Amgoud, 2007] Martin Caminada and Leila Am- goud. On the evaluation of argumentation formalisms. Artif. Intell., 171(5-6):286-310, 2007.
[Charwat et al., 2015] Günther Charwat, Wolfgang Dvořák, Sarah A. Gaggl, Johannes P. Wallner, and Stefan Woltran. Methods for Solv- ing Reasoning Problems in Abstract Argumentation -A Survey. Artif. Intell., 220:28-63, 2015.
[Coste-Marquis et al., 2014] Sylvie Coste-Marquis, Sébastien Konieczny, Jean-Guy Mailly, and Pierre Marquis. On the revision of argumentation systems: minimal change of arguments statuses. In Proc. KR, pages 72-81, 2014.
[Dung, 1995] Phan M. Dung. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic program- ming and n-person games. Artif. Intell., 77(2):321-357, 1995.
[Dunne et al., 2013] Paul E. Dunne, Wolfgang Dvořák, Thomas Linsbichler, and Stefan Woltran. Characteristics of multiple view- points in abstract argumentation. In Proc. DKB, pages 16-30, 2013.
[Dunne et al., 2014] Paul E. Dunne, Wolfgang Dvořák, Thomas Linsbichler, and Stefan Woltran. Characteristics of multiple view- points in abstract argumentation. In Proc. KR, pages 71-82, 2014.
[Dvořák and Spanring, 2012] Wolfgang Dvořák and Christof Span- ring. Comparing the expressiveness of argumentation semantics. In Proc. COMMA, pages 261-272, 2012.
[Dvořák and Woltran, 2011] Wolfgang Dvořák and Stefan Woltran. On the intertranslatability of argumentation semantics. J. Artif. Intell. Res., 41:445-475, 2011.
[Dvořák et al., 2014] Wolfgang Dvořák, Thomas Linsbichler, Emilia Oikarinen, and Stefan Woltran. Resolution-based grounded semantics revisited. In Proc. COMMA, pages 269-280, 2014.
[Dyrkolbotn, 2014] Sjur K. Dyrkolbotn. How to argue for anything: Enforcing arbitrary sets of labellings using AFs. In Proc. KR, pages 626-629, 2014.
[Hunter and Williams, 2012] Anthony Hunter and Matthew Williams. Aggregating evidence about the positive and negative effects of treatments. Artificial Intelligence in Medicine, 56(3):173-190, 2012.
[Katsuno and Mendelzon, 1991] Hirofumi Katsuno and Alberto O. Mendelzon. Propositional knowledge base revision and minimal change. Artif. Intell., 52(3):263-294, 1991.
[Prakken, 2010] Henry Prakken. An abstract framework for argu- mentation with structured arguments. Argument & Computation, 1(2):93-124, 2010.
[Rahwan and Simari, 2009] Iyad Rahwan and Guillermo R. Simari, editors. Argumentation in Artificial Intelligence. Springer, 2009.
[Strass, 2015] Hannes Strass. The relative expressiveness of abstract argumentation and logic programming. In Proc. AAAI, pages 1625-1631, 2015.

References were extracted automatically from the PDF and may contain errors.

Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.

1 Motivation

In recent years the research field of argumentation has become a major topic of artificial intelligence [Bench-Capon and Dunne, 2007; Rahwan and Simari, 2009]. This is not only due to the intrinsic interest of this topic and recent applications (e.g. [Hunter and Williams, 2012]), but also because of fundamental connections to other areas of AI. In particular, the formal approach of abstract argumentation [Dung, 1995] has aroused much interest of research. A so-called abstract argumentation framework (AF) is a directed graph where nodes represent arguments and directed edges represent conflicts between arguments, i.e. counter-arguments "attack" arguments by directed edges. The central question, given an AF F , is which sets of arguments can be jointly accepted. This is answered by argumentation semantics σ which give rise to extensions σ(F), i.e. sets of jointly acceptable arguments. A variety of extension-based semantics has been proposed over the years, an overview of these semantics and their properties can be found in [Baroni et al., 2011a].

The problem of solving certain reasoning tasks on AFs is the centerpiece of many advanced higher-level argumentation systems. The fact that problems to be solved are intractable requires efficient and advanced algorithms to be developed in order to deal with real-world-sized data within reasonable performance. This is witnessed by the upcoming first solver competition 1 and an increasing number of proposed algorithms (see [Charwat et al., 2015] for a recent survey).

On the other hand, the last years have seen interest in the systematic analysis of the various argumentation semantics. In particular, we have initiated investigations on the capabilities of semantics in terms of expressiveness, where the question of realizability was studied [Dunne et al., 2013]. That is, given a semantics σ and a set of sets of arguments S, is there an AF F with σ(F) = S, i.e. an AF F realizing S under σ. This was done by characterizing the signatures

Formula not decoded

for some of the main semantics σ. This gives answers to which extensions can, in principle, go together when a framework is evaluated with respect to a semantics of interest. It not only clarifies the "strength" of that semantics but also is a crucial issue in several applications.

∗Supported by FWF under grants I1102 and P25521.

1 http://argumentationcompetition.org

Abstract Argumentation Frameworks - FromTheoretical Insights to Practical Implications∗

Thomas Linsbichler

linsbich@dbai.tuwien.ac.at Institute of Information Systems Vienna University of Technology, Austria

In the thesis we want to complete and extend the study on expressiveness of argumentation semantics and use these and other theoretical results for implementations of reasoning tasks in AFs. For instance, characterizations of signatures can be exploited to limit the search space when enumerating the extensions of a given argumentation framework. Moreover, we plan to utilize results on realizability in dynamic scenarios of abstract argumentation (see e.g. [Booth et al., 2013]), such as revision of argumentation frameworks. Hereby, the knowledge of which extensions can occur together is of central interest when trying to achieve a certain outcome. In other words, the ultimate goal of the thesis is to gain theoretical insights on argumentation semantics in order to employ them in practically efficient reasoning systems for both the evaluation and evolution of AFs.

2 Planned Contributions

First, we want to extend the work on expressiveness of argumentation semantics by characterizing the signatures of other prominent semantics. These include the complete [Dung, 1995] as well as resolution-based grounded semantics [Baroni et al., 2011b]. The latter is particularly interesting, since it is, to the best of our knowledge, the only semantics fulfilling all desirable principles of argumentation semantics as proposed in [Baroni and Giacomin, 2007].
Second we plan to investigate how theoretical insights on argumentation semantics can be used in implementations thereof. Exact characterizations of signatures can be exploited in search procedures such as enumerating all extensions under a given semantics. Knowing which results can occur together, the procedure can restrict the search space once it has found extensions based on the knowledge of signatures. Another theoretic aspect which can be used to guide algorithms is the existence of implicit conflicts, i.e. pairs of arguments which do not occur together in an extension but do not attack each other.
Moreover, we want to study revision of AFs when new information is provided. This is of high importance since argumentation is an inherently dynamic process. We want to show that exact characterizations of signatures are indispensable for operations incorporating new knowledge following the AGM approach [Alchourr´on et al., 1985; Katsuno and Mendelzon, 1991; Coste-Marquis et al., 2014].

Recently, interchangeability of input/output equivalent parts of AFs has been studied [Baroni et al., 2014]. We want to extend our considerations on realizability and show which input/output functions can be realized by AFs and how to do this. Translations from other formalisms to AFs, which may be needed since good solvers are only available for AFs, can then make use of these "input/output gadgets".
Finally we plan to study signatures with respect to subclasses of AFs. These can be typical syntactic subclasses such as symmetric or bipartite graphs or "semantic" subclasses such as coherent, compact, or AFs which can be the outcome of a particular instantiation process. The latter is important for considering the issues presented here not only in the abstract setting but also in various approaches of structured argumentation [Caminada and Amgoud, 2007; Prakken, 2010], which is planned as future work.

3 Achieved Results

We have carried out a continuation of the study on expressiveness of argumentation semantics in [Dunne et al., 2014]. Moreover, we have studied realizability issues for the interesting resolution-based grounded semantics in [Dvoˇr´ak et al., 2014]. In [Baumann et al., 2014] we have tackled the question of how rejected arguments, i.e. arguments not occurring in any extension, influence the expressiveness of argumentation semantics, giving rise to the class of compact argumentation frameworks.

4 RelatedWork

The study on expressiveness of argumentation was preceeded by work on intertranslatability between semantics [Dvoˇr´ak and Woltran, 2011; Dvoˇr´ak and Spanring, 2012]. Moreover, [Dyrkolbotn, 2014] studied realizability under labeling-based semantics and [Strass, 2015] related the expressiveness of selected semantics in AFs, ADFs and logic programming. A systematic comparison of argumentation semantics from the point of view of desirable principles has been carried out in [Baroni and Giacomin, 2007].

Thomas Linsbichler. 2015. Abstract Argumentation Frameworks - From Theoretical Insights to Practical Implications. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 4377–4377. https://ijcai.org/proceedings/2015/636

@inproceedings{ijcai2015p636,
  title     = {Abstract Argumentation Frameworks - From Theoretical Insights to Practical Implications},
  author    = {Linsbichler, Thomas},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {4377--4377},
  year      = {2015},
  month     = {7},
  note      = {Doctoral Consortium},
  url       = {https://ijcai.org/proceedings/2015/636},
}

TY  - CPAPER
TI  - Abstract Argumentation Frameworks - From Theoretical Insights to Practical Implications
AU  - Linsbichler, Thomas
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 4377
EP  - 4377
UR  - https://ijcai.org/proceedings/2015/636
ER  -

[1] [Alchourrón et al., 1985] Carlos E. Alchourrón, Peter Gärdenfors, and David Makinson. On the logic of theory change: partial meet contraction and revision functions. J. Symb. Log., 50(2):510-530, 1985.

[2] [Baroni and Giacomin, 2007] Pietro Baroni and Massimiliano Gia- comin. On principle-based evaluation of extension-based argu- mentation semantics. Artif. Intell., 171(10-15):675-700, 2007.

[3] [Baroni et al., 2011a] Pietro Baroni, Martin Caminada, and Massi- miliano Giacomin. An introduction to argumentation semantics. Knowledge Eng. Review, 26(4):365-410, 2011.

[4] [Baroni et al., 2011b] Pietro Baroni, Paul E. Dunne, and Massim- iliano Giacomin. On the resolution-based family of abstract ar- gumentation semantics and its grounded instance. Artif. Intell., 175(3-4):791-813, 2011.

[5] [Baroni et al., 2014] Pietro Baroni, Guido Boella, Federico Cerutti, Massimiliano Giacomin, Leendert van der Torre, and Serena Vil- lata. On the Input/Output behaviour of argumentation frameworks. Artif. Intell., 217:144-197, 2014.

[6] [Baumann et al., 2014] Ringo Baumann, Wolfgang Dvořák, Thomas Linsbichler, Hannes Strass, and Stefan Woltran. Compact argumentation frameworks. In Proc. ECAI, pages 69-74, 2014.

[7] [Bench-Capon and Dunne, 2007] Trevor J. M. Bench-Capon and Paul E. Dunne. Argumentation in artificial intelligence. Artif. Intell., 171(10-15):619-641, 2007.

[8] [Booth et al., 2013] Richard Booth, Souhila Kaci, Tjitze Rienstra, and Leendert van der Torre. A logical theory about dynamics in abstract argumentation. In Proc. SUM, pages 148-161, 2013.

[9] [Caminada and Amgoud, 2007] Martin Caminada and Leila Am- goud. On the evaluation of argumentation formalisms. Artif. Intell., 171(5-6):286-310, 2007.

[10] [Charwat et al., 2015] Günther Charwat, Wolfgang Dvořák, Sarah A. Gaggl, Johannes P. Wallner, and Stefan Woltran. Methods for Solv- ing Reasoning Problems in Abstract Argumentation -A Survey. Artif. Intell., 220:28-63, 2015.

[11] [Coste-Marquis et al., 2014] Sylvie Coste-Marquis, Sébastien Konieczny, Jean-Guy Mailly, and Pierre Marquis. On the revision of argumentation systems: minimal change of arguments statuses. In Proc. KR, pages 72-81, 2014.

[12] [Dung, 1995] Phan M. Dung. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic program- ming and n-person games. Artif. Intell., 77(2):321-357, 1995.

[13] [Dunne et al., 2013] Paul E. Dunne, Wolfgang Dvořák, Thomas Linsbichler, and Stefan Woltran. Characteristics of multiple view- points in abstract argumentation. In Proc. DKB, pages 16-30, 2013.

[14] [Dunne et al., 2014] Paul E. Dunne, Wolfgang Dvořák, Thomas Linsbichler, and Stefan Woltran. Characteristics of multiple view- points in abstract argumentation. In Proc. KR, pages 71-82, 2014.

[15] [Dvořák and Spanring, 2012] Wolfgang Dvořák and Christof Span- ring. Comparing the expressiveness of argumentation semantics. In Proc. COMMA, pages 261-272, 2012.

[16] [Dvořák and Woltran, 2011] Wolfgang Dvořák and Stefan Woltran. On the intertranslatability of argumentation semantics. J. Artif. Intell. Res., 41:445-475, 2011.

[17] [Dvořák et al., 2014] Wolfgang Dvořák, Thomas Linsbichler, Emilia Oikarinen, and Stefan Woltran. Resolution-based grounded semantics revisited. In Proc. COMMA, pages 269-280, 2014.

[18] [Dyrkolbotn, 2014] Sjur K. Dyrkolbotn. How to argue for anything: Enforcing arbitrary sets of labellings using AFs. In Proc. KR, pages 626-629, 2014.

[19] [Hunter and Williams, 2012] Anthony Hunter and Matthew Williams. Aggregating evidence about the positive and negative effects of treatments. Artificial Intelligence in Medicine, 56(3):173-190, 2012.

[20] [Katsuno and Mendelzon, 1991] Hirofumi Katsuno and Alberto O. Mendelzon. Propositional knowledge base revision and minimal change. Artif. Intell., 52(3):263-294, 1991.

[21] [Prakken, 2010] Henry Prakken. An abstract framework for argu- mentation with structured arguments. Argument & Computation, 1(2):93-124, 2010.

[22] [Rahwan and Simari, 2009] Iyad Rahwan and Guillermo R. Simari, editors. Argumentation in Artificial Intelligence. Springer, 2009.

[23] [Strass, 2015] Hannes Strass. The relative expressiveness of abstract argumentation and logic programming. In Proc. AAAI, pages 1625-1631, 2015.