Enforcement in Abstract Argumentation via Boolean Optimization

Show full item record

Permalink

http://urn.fi/URN:NBN:fi-fe2017112251305
Title: Enforcement in Abstract Argumentation via Boolean Optimization
Author: Niskanen, Andreas
Contributor: Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta, Tietojenkäsittelytieteen laitos
Thesis level:
Abstract: Computational aspects of argumentation are a central research topic of modern artificial intelligence. A core formal model for argumentation, where the inner structure of arguments is abstracted away, was provided by Dung in the form of abstract argumentation frameworks (AFs). AFs are syntactically directed graphs with the nodes representing arguments and edges representing attacks between them. Given the AF, sets of jointly acceptable arguments or extensions are defined via different semantics. The computational complexity and algorithmic solutions to so-called static problems, such as the enumeration of extensions, is a well-studied topic. Since argumentation is a dynamic process, understanding the dynamic aspects of AFs is also important. However, computational aspects of dynamic problems have not been studied thoroughly. This work concentrates on different forms of enforcement, which is a core dynamic problem in the area of abstract argumentation. In this case, given an AF, one wants to modify it by adding and removing attacks in a way that a given set of arguments becomes an extension (extension enforcement) or that given arguments are credulously or skeptically accepted (status enforcement). In this thesis, the enforcement problem is viewed as a constrained optimization task where the change to the attack structure is minimized. The computational complexity of the extension and status enforcement problems is analyzed, showing that they are in the general case NP-hard optimization problems. Motivated by this, algorithms are presented based on the Boolean optimization paradigm of maximum satisfiability (MaxSAT) for the NP-complete variants, and counterexample-guided abstraction refinement (CEGAR) procedures, where an interplay between MaxSAT and Boolean satisfiability (SAT) solvers is utilized, for problems beyond NP. The algorithms are implemented in the open source software system Pakota, which is empirically evaluated on randomly generated enforcement instances.
URI: http://hdl.handle.net/10138/205643
URN:NBN:fi-fe2017112251305
Date: 2017-04-11
Subject: abstract argumentation
argumentation dynamics
computational complexity
maximum satisfiability
Discipline: Tietojenkäsittelytiede


Files in this item

Total number of downloads: Loading...

Files Size Format View Description
gradu.pdf 1.500Mb PDF View/Open pro gradu

This item appears in the following Collection(s)

Show full item record