Finnish Information Processing Association, based on the proposal of Finnish Society for Computer Science, has awarded the 2021 annual award for the best PhD thesis in computer science to Andreas Niskanen of the Constraint Reasoning and Optimization Group for his thesis "Computational Approaches to Dynamics and Uncertainty in Abstract Argumentation". The thesis was done within Doctoral Programme in Computer Science at University of Helsinki, and supervised by Professor Matti Järvisalo.
Abstract of the thesis:
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 at- tacks, between arguments. For reasoning about arguments, and in partic- ular 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.