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

摘要

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-CCA(EP) works by calling an SLS SAT solver Swcca in an iterative manner with adaptive heuristics. Our second SLS algorithm Inc-CCA(EP) realized an incremental version of Swcca, specially designed for computing the preferred extensions in AF. Though Ite-CCA(EP) and Inc-CCA(EP) 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-CCA(EP) is more efficient than Ite-CCAEP, which inspired the design of a novel complete algorithm called CCASAT(EP) that uses Inc-CCA(EP) as an efficient preprocessor. Further experiments show that CCASAT(EP) is competitive to the state-of-the-art methods.