Computational Approaches to Dynamics and Uncertainty in Abstract Argumentation

Show full item record



Permalink

http://urn.fi/URN:ISBN:978-951-51-6617-3
Title: Computational Approaches to Dynamics and Uncertainty in Abstract Argumentation
Author: Niskanen, Andreas
Other contributor: Helsingin yliopisto, matemaattis-luonnontieteellinen tiedekunta
Helsingfors universitet, matematisk-naturvetenskapliga fakulteten
University of Helsinki, Faculty of Science, Department of Computer Science
Tietojenkäsittelytieteen tohtoriohjelma
Doktorandprogrammet i datavetenskap
Doctoral Programme in Computer Science
Publisher: Helsingin yliopisto
Date: 2020-10-13
Language: en
Belongs to series: Series of publications A / Department of Computer Science, University of Helsinki - URN:ISSN:1238-8645
URI: http://urn.fi/URN:ISBN:978-951-51-6617-3
http://hdl.handle.net/10138/319458
Thesis level: Doctoral dissertation (article-based)
Abstract: Argumentation in artificial intelligence (AI) is a prominent research area situated in the field of knowledge representation and reasoning. Abstract argumentation frameworks (AFs) constitute a central formalism to argumentation in AI. AFs model argumentative scenarios as directed graphs, with nodes representing arguments and edges representing conflicts, or attacks, between arguments. For reasoning about arguments, and in particular about the acceptability of arguments, several different argumentation semantics identify jointly acceptable subsets of arguments called extensions. Argumentation is inherently a dynamic process involving changes with respect to both arguments and attacks between them. Dynamics give rise to various representational and computational challenges. In this thesis, we study three related themes involving dynamics and uncertainty in AFs from a computational perspective: extension and status enforcement in AFs, the AF synthesis problem, and two formalisms specifically designed to accommodate uncertainty arising from dynamics, namely, incomplete AFs and control AFs. Extension enforcement is the problem of finding the smallest possible change to a given AF in such a way that a given subset of arguments is (included in) an extension, while in status enforcement the goal is to make given arguments accepted or rejected. The AF synthesis problem, proposed in this thesis, seeks to construct an optimal AF in terms of representing given examples of extensions and non-extensions. AF synthesis generalizes the fundamental concept of realizability in AFs, and is more applicable in dynamic settings involving incomplete or inconsistent information. Incomplete AFs generalize standard AFs by distinguishing between definite and uncertain arguments and attacks, allowing to reason about acceptance of arguments by quantifying over the uncertain part. Control AFs also include control arguments, allowing an agent to choose which arguments to put forward in order to reach their goal regardless of the state of the uncertain part, giving rise to the problem of controllability. We provide complexity results and practical algorithms for each of the three problem settings. We show that the computational complexity of these problems varies from polynomial-time solvability to completeness for the second or third level of the polynomial hierarchy, depending largely on the problem variant, restrictions to the input instance, and the choice of semantics. Motivated by the success of Boolean satisfiability (SAT) based declarative methods for NP-complete problems and SAT-based counterexample-guided abstraction refinement (CEGAR) algorithms for problems beyond NP, we develop algorithms that are based on employing SAT and maximum satisfiability solvers both directly and in an iterative CEGAR loop. For the CEGAR algorithms, we develop so-called strong refinement steps that allow for reducing the number of redundant CEGAR iterations, and show that these are essential to solving the problems in practice. All of the proposed algorithms are implemented, made available in open source, and subjected to extensive empirical evaluation.Argumentaatio on merkittävä modernin tekoälytutkimuksen haara. Niin kutsuttujen abstraktien argumentaatiokehysten avulla voidaan mallintaa argumentointiin liittyviä tilanteita suunnattuina verkkoina, joissa solmut esittävät argumentteja ja kaaret hyökkäyksiä eli ristiriitoja argumenttien välillä. Erilaiset argumentaatiosemantiikat määrittelevät yhdessä hyväksyttäviä, keskenään ristiriidattomia argumenttijoukkoja. Useissa käytännön tilanteissa argumentaatiokehysten rakenne ei ole ennalta määrätty; sekä argumentit että niiden vasta-argumentit ovat muutoksille alttiita ja siten myös epävarmoja. Tämä aiheuttaa useita sekä esityksellisiä että laskennallisia haasteita. Tässä väitöskirjassa tutkitaan kolmea argumentaatiokehysten dynamiikkaan ja epävarmuuteen liittyvää teemaa laskennallisesta näkökulmasta: pakotusongelmia, argumentaatiokehysten synteesiä sekä epävarmuuden esittämiseen tarkoitettuja argumentaatiokehysten laajennoksia. Työssä esitetään laskennalliseen vaativuuteen liittyviä tuloksia sekä käytännön algoritmeja edellä mainittujen aihealueiden kontekstissa. Vaativuuden kannalta näytetään, että useat ongelmien muunnelmat ovat NP-vaikeita monille keskeisille argumentaatiosemantiikoille. Näiden ongelmien ratkaisemiseksi työssä suunnitellaan algoritmeja pohjautuen lauselogiikan toteutuvuustarkastimien sekä niiden optimointilaajennosten käyttöön. Esitetyt algoritmit kehitetään avoimen lähdekoodin implementaatioina ja niiden käytännön sovellettavuutta osoitetaan kattavien empiiristen evaluaatioiden kautta.
Subject: tietojenkäsittelytiede
Rights: Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.


Files in this item

Total number of downloads: Loading...

Files Size Format View
niskanen_andreas_dissertation_2020.pdf 938.3Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record