New stochastic local search approaches for computing preferred extensions of abstract argumentation

Article type: Research Article

Authors: Niu, Dangdang^a | Liu, Lei^a | Lü, Shuai^{a; b; *}

Affiliations: [a] College of Computer Science and Technology, Jilin University, Changchun, China. E-mails: ddniu15@mails.jlu.edu.cn, liulei@jlu.edu.cn, lus@jlu.edu.cn | [b] Key Laboratory of Symbolic Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun, China

Correspondence: [*] Corresponding author. E-mail: lus@jlu.edu.cn.

Abstract: Several efficient SAT-based methods for computing the preferred extensions in (abstract) argumentation frameworks (AF) are proposed lately. However, only complete SAT solvers have been exploited so far. It is a natural question that how the appealing stochastic local search (SLS) approach could advance the performance. In this paper, we developed two SLS algorithms for computing the preferred extensions in AF, and a complete one which combines the strength of the better one with complete SAT solvers. Our first SLS algorithm Ite-CCAEP works by calling an SLS SAT solver Swcca in an iterative manner with adaptive heuristics. Our second SLS algorithm Inc-CCAEP realized an incremental version of Swcca, specially designed for computing the preferred extensions in AF. Though Ite-CCAEP and Inc-CCAEP do not guarantee completeness, they notably outperform a state-of-the-art solver consistently on most benchmarks with non-empty preferred extensions. Experimental results also show that Inc-CCAEP is more efficient than Ite-CCAEP, which inspired the design of a novel complete algorithm called CCASATEP that uses Inc-CCAEP as an efficient preprocessor. Further experiments show that CCASATEP is competitive to the state-of-the-art methods.

Keywords: Abstract argumentation, stochastic local search, preferred semantics

DOI: 10.3233/AIC-180769

Journal: AI Communications, vol. 31, no. 4, pp. 369-382, 2018