M.Sc. Andreas Niskanen defends his doctoral thesis Computational Approaches to Dynamics and Uncertainty in Abstract Argumentation on Tuesday the 13th of October 2020 at 12 o'clock through remote access. His opponent is Professor Gerhard Brewka (Leipzig University, Germany) and custos Associate Professor Matti Järvisalo (University of Helsinki). The defence will be held in English. It is possible to follow the defence as a live stream at https://helsinki.zoom.us/j/64923647356?pwd=TmFrRFhOS0ljcHNjNUVFUGhoTU85QT09.
The thesis of Andreas Niskanen is a part of research done in the Department of Computer Science and in the Constraint Reasoning and Optimization research group at the University of Helsinki. His supervisors have been Associate Professor Matti Järvisalo and Professor Petri Myllymäki (University of Helsinki).
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.
Availability of the dissertation
An electronic version of the doctoral dissertation is available on the e-thesis site of the University of Helsinki at http://urn.fi/URN:ISBN:978-951-51-6617-3.
Printed copies will be available on request from Andreas Niskanen: firstname.lastname@example.org.