Computational Approaches to Dynamics and Uncertainty in Abstract Argumentation

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