M.Sc. Andreas Niskanen succesfully defended his doctoral dissertation Computational Approaches to Dynamics and Uncertainty in Abstract Argumentation on October 13, 2020. The thesis work was conducted in the Constraint Reasoning and Optimization group of the Department of Computer Science at the University of Helsinki, with Associate Professor Matti Järvisalo as the main PhD supervisor. Professor Gerhard Brewka (University of Leipzig, Germany) acted as the opponent. Congratulations Andreas!
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.
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.