Enumerating semantics extensions in abstract argumentation is generally an intractable problem. For preferred semantics four implementations have been recently proposed, CONArg2, AspartixM, PrefSATand NAD-Alg, with significant runtime variations. This work is a first empirical evaluation of the performance of these implementations with the hypothesis that NAD-Alg, as representative of a family of ad-hoc approaches, will overcome in sequence PrefSAT - a SAT-based approach -, CONArg2- a CSP-based approach -, and the ASP-based approach AspartixM. The results shows that this is not always the case, as PrefSAT has been often the best approach both in terms of numbers of enumeration problems solved, and CPU-time. Moreover, we identify situations where AspartixM has been proved to be significantly faster than CONArg2.
Dung’s theory of abstract argumentation frameworks [
The introduction of preferred semantics is one of the main contribution of Dung’s paper. The semantics’ name, in fact, reflects a sort of preference w.r.t. other traditional semantics, as it allows multiple extensions (differently from grounded semantics), the existence of extensions is always guaranteed (differently from stable semantics), and no extension is a proper subset of another extension (differently from complete semantics).
The main computational problems in abstract argumentation are naturally related to extensions and can be partitioned into two classes: decision problems and construction problems. Decision problems pose yes/no questions like “Does this argument belong to one (all) extensions?” or “Is this set an extension?”, while construction problems require to explicitly produce some of the extensions prescribed by a semantics. In particular, extension enumeration is the problem of constructing all the extensions prescribed by a given semantics for a given AF .
Theoretical analysis of worst-case computational issues in abstract argumentation
is in a state of maturity with the available complexity results covering all Dung’s
traditional semantics and several subsequent prominent approaches in the literature (for
a summary see [
This paper contributes to fill this gap by comparing the two families of approaches considered in the literature. On one hand, one may develop a dedicated algorithm to obtain the problem solution, on the other hand, one may reduce the problem instance into an equivalent instance of a different class of problems for which solvers are already available. The results produced by the solver have then to be translated back to the original problem.
In our experiment, we compare the state-of-the-art approaches which reduce the preferred extension enumeration problem into a CSP (CONArg2), ASP (AspartixM) and SAT (PrefSAT) with the best ad-hoc approach [18] in its latest version — NAD-Alg [19]. Our experimental hypothesis is that there will be a strict ordering — under any configuration — regarding the performance of the software measured in (1) CPU-time needed to enumerate all the preferred extensions given an AF and in (2) percentage of successful enumeration. Such an ordering should see the ad-hoc approach NAD-Alg as the best one, followed by PrefSAT, CONArg2, and finally AspartixM. As discussed later on the paper, our hypothesis has been proved true only partially: we identified several cases where (1) PrefSAT has been the best implementation — and it is also the only one implementation that solved all the AF s considered in the experiment — and (2) AspartixM performed significantly — according to the Friedman statistic test confirmed by a post-hoc analysis with the Wilcoxon signed rank with a Bonferroni correction applied [22] — better than CONArg2.
The paper is organized as follows. Section 2 recalls the necessary basic theoretical concepts of Dung’s argumentation frameworks, Constraint Satisfaction Programming, Answer Set Programming, and Propositional Satisfiability Problems. Section 3 summarises the current state-of-the-art of the approaches for enumerating preferred extensions, namely NAD-Alg, CONArg2, AspartixM, and PrefSAT. Section 4 describes the test setting and comments the experimental results and then Section 5 concludes the paper.
An argumentation framework [
An argument a1 without attackers, i.e. such that a1 = ;, is said initial. The neighbour of an argument a1 is a1 [ a1+. Moreover, each argumentation framework can be represented as a directed graph where the vertices are the arguments, and the edges are the attacks.
The basic properties of conflict–freeness, acceptability, and admissibility of a set of arguments are fundamental for the definition of argumentation semantics. Definition 2. Given an AF
= hA; Ri: – a set S A is a conflict–free set of if @ a1; a2 2 S s.t. a1 ! a2; – an argument a1 2 A is acceptable with respect to a set S A of
a2 ! a1, 9 a3 2 S s.t. a3 ! a2; – a set S A is an admissible set of if S is a conflict–free set of element of S is acceptable with respect to S of .
An argumentation semantics prescribes for any AF a set of extensions, denoted as E ( ), namely a set of sets of arguments satisfying the conditions dictated by . Here we need to recall the definitions of complete (denoted as CO), and preferred (denoted as PR) semantics only.
= hA; Ri: – a set S A is a complete extension of , i.e. S 2 ECO( ), iff S is admissible and 8a1 2 A s.t. a1 is acceptable w.r.t. S, a1 2 S; – a set S A is a preferred extension of , i.e. S 2 EPR( ), iff S is a maximal (w.r.t. set inclusion) complete extension of .
It can be noted that each extension S implicitly defines a three-valued labelling of
arguments, as follows: an argument a1 is labelled in iff a1 2 S, is labelled out iff
9 a2 2 S s.t. a2 ! a1, is labelled undec if neither of the above conditions holds. In
the light of this correspondence, argumentation semantics can equivalently be defined
in terms of labellings rather than of extensions (see [
Definition 4. Let hA; Ri be an argumentation framework. A total function Lab : A 7! fin; out; undecg is a complete labelling iff it satisfies the following conditions for any a1 2 A: – Lab(a1) = in , 8a2 2 a1 Lab(a2) = out; – Lab(a1) = out , 9a2 2 a1 : Lab(a2) = in; – Lab(a1) = undec , 8a2 2 a1 Lab(a2) 6= in ^ 9a3 2 a1 : Lab(a3) = undec;
It is proved in [
Constraint programming is a powerful paradigm for solving combinatorial search problems that draws on a wide range of techniques from artificial intelligence (AI), operations research, algorithms, and graph theory [21].
Following [
A solution to the CSP P is A = ha1; : : : ; ani where 8i; ai 2 Di and 8j; RSj holds on the projection of A onto the scope Sj . If the set of solutions is empty, the CSP is unsatisfiable. 2.3
Over the the last years, Answer Set Programming (ASP) [15] has emerged as a declarative problem solving paradigm. It evolved from various fields such as Logic Programming, Deductive Databases, Knowledge Representation, and Nonmonotonic Reasoning, and serves as a flexible language for declarative problem solving. There are two main tasks in problem solving, representation and reasoning, which are clearly separated in the declarative paradigm. In ASP, representation is done using a rule-based language, while reasoning is performed using implementations of general-purpose algorithms, referred to as ASP solvers.
Rules in ASP are interpreted according to common sense principles, including a variant of the closed-world-assumption (CWA) and the unique-name-assumption (UNA). Collections of ASP rules are referred to as ASP programs, which represent the modelled knowledge. To each ASP program a collection of answer sets, or intended models, is associated, which stand for the solutions to the modelled problem; this collection can also be empty, meaning that the modelled problem does not admit a solution. Several reasoning tasks exist: the classical ASP task is enumerating all answer sets or determining whether an answer set exists, but ASP also allows for query answering in brave or cautious modes [16]. 2.4
In the propositional satisfiability problem (SAT) the goal is to determine whether a given Boolean formula is satisfiable. A variable assignment that satisfies a formula is a solution. In SAT, formulae are commonly expressed in Conjunctive Normal Form (CNF). A formula in CNF is a conjunction of clauses, where clauses are disjunctions of literals, and a literal is either positive (a variable) or negative (the negation of a variable). If at least one of the literals in a clause is true, then the clause is satisfied, and if all clauses in the formula are satisfied then the formula is satisfied and a solution has been found.
A wide range of decision and optimisation problems can be reduced as SAT
instances. A few examples are logical circuit design [
In this section we summarise the main idea behind the most competitive ad-hoc approach for solving the enumeration problem for preferred semantics, viz. NAD-Alg, and the three champions for transforming such a problem into a (resp.) CSP (CONArg2), ASP (AspartixM), and SAT (PrefSAT) problem. 3.1
NAD-Alg
The algorithm proposed in [18, 19] has been shown to outperform the other ad-hoc
approaches [
NAD-Alg [19] is a depth-first backtracking procedure that traverses a binary search tree. The root considers the case where all the arguments in the AF are blank, i.e. not yet visited. At each step of the search process, a blank node is selected and assumed to belong to the preferred extension, and a local evaluation on its neighbour is performed. Then the procedure recursively call itself on the assumption that the above arguments are respectively in or out the extension. Any inconsistency leads to a backtrack.6 3.2
In [
Subsequently, they describe constraints associated to different definitions of Dung’s argumentation framework: for instance fa1; a2g A is conflict–free iff :(x1 = 1 ^ x2 = 1). The other constraints are imposed following the same reasoning line.
In this paper, we consider the most recent advancement of the Conarg project, viz. CONArg2, which is the command line version that is implemented by Gecode 4.0 (C++). This version is faster and it is able to compute credulous/skeptical acceptance of an argument for stable, complete and admissible AF semantics too. 3.3
AspartixM [
Given an AF hA; Ri, Aspartix encodes the requirements for a “semantics” (e.g. the conflict–free requirements) in an ASP program whose database considers:
farg(a) j a 2 Ag [ fdefeat(a1; a2) j ha1; a2i 2 Rg
The following program fragment is thus used to check the conflict–freeness [
in(X); in(Y ); defeat(X; Y )g: 3.4
PrefSAT [
Differently from Aspartix and Conarg, PrefSAT encodes the Caminada labelling requirements in a CNF. To do so, for each argument ai 2 A, three propositional variables are considered: Ii (which is true iff Lab(ai) = in), Oi (which is true iff Lab(ai) = out), Ui (which is true iff Lab(ai) = undec).
Given jAj = k and : f1; : : : ; kg 7! A, the conjunction of the formulae listed below is a CNF representing the requirements for a complete labelling (the last formula filters out the trivial case of the empty set):
^ i2f1;:::;kg (Ii _ Oi _ Ui) ^ (:Ii _ :Oi)^(:Ii _ :Ui) ^ (:Oi _ :Ui) (1) 7 AspartixM has been executed with gringo version 3.0.3 and claspD version 1.1.4.
^ fij (i) 6=;g 0 fjj (j)! (i)g @ fij (i) 6=;g fjj (j)! (i)g 0 0 ^ ^ 0
:Ij _ OiA ^ fij (i) 6=;g 0 fjj (j)! (i)g
11
Ij AA 0 0
_ fjj (j)! (i)g
111
Ij AAA ^ ^ ^ ^ 00 (3) (4) (5) (6) (7) (9) ^ fij (i) 6=;g fjj (j)! (i)g 1 0
0
_ fjj (j)! (i)g
111
Uj AAA (8) _ i2f1;:::kg
Ii
As noticed in [
In this section we present the results of an experimental study examining CONArg2,
The experimental analysis has been conducted on 720 AF s that were divided in different classes, according to two dimensions: the number of arguments, jAj and the criterion of random generation of the attack relation, jRj. As to jAj we considered 8 different values, ranging from 25 to 225 with a step of 25. As to the generation of the attack relation we used two alternative methods. The first method consists in fixing the probability patt that there is an attack for each ordered pair of arguments (self-attacks are included): for each pair a pseudo-random number uniformly distributed between 0 and 1 is generated and if it is lesser or equal to patt the pair is added to the attack relation. We considered three values for patt, namely 0.25, 0.5 and 0.75. Combining the 9 values of jAj with the 3 values of patt gives rise to 27 test classes, each of which has been populated with 20 AF s. 10 of them included auto-attacks, the other do not.
The second method consists in generating randomly, for each AF , the number natt of attacks it contains (extracted with uniform probability between 0 and jAj2). Then the natt distinct pairs of arguments constituting the attack relation are selected randomly. Applying the second method with the 9 values of jAj gives rise to 9 further test classes, each of which has been populated with 20 AF s.
The solvers and the feature extraction algorithms have been run on a cluster with computing nodes equipped with 2.5 Ghz Intel Core 2 Quad ProcessorsTM, 8 GB of RAM and Linux operating system. As in the International Planning Competition (IPC), a cutoff of 900 seconds was imposed to compute the preferred extensions for each AF .8 The systems under evaluation have been compared with respect to the ability to produce solutions within the time limit and to the execution time. As to the latter comparison, we adopted the IPC speed score, also borrowed from the planning community, which is defined as follows: – For each test case (in our case, each test AF ) let T be the best execution time among the compared systems (if no system produces the solution within the time limit, the test case is not considered valid and ignored). – For each valid case, each system gets a score of 1=(1 + log10(T =T )), where T is its execution time, or a score of 0 if it fails in that case. Runtimes below 1 sec get by default the maximal score of 1. – The (non normalised) IP C score for a system is the sum of its scores over all the valid test cases. The normalised IPC score ranges from 0 to 100 and is defined as (IP C=# of valid cases) 100.
Therefore, the higher the IP C score, the better the performance.
Figure 1 presents the values of normalised IPC score considering all test cases grouped w.r.t. jAj, while Table 1 shows the average time needed by the four systems for computing the preferred extensions. Cutoff runtime is considered for unsolved AF s. Both PrefSAT and NAD-Alg performed significantly better (note that the IPC score is logarithmic) than AspartixM and CONArg2 for all values of jAj > 75, and the performance gap increases with increasing jAj. Interestingly, it is possible to clusterise the approaches according to their IPC performance. In one cluster there are AspartixM and CONArg2, and the other includes PrefSAT and NAD-Alg. It is a surprising result, in the light of the very different approaches they exploit in order to enumerate preferred 8 http://helios.hud.ac.uk/scommv/IPC-14/
CONArg2 AspartixM PrefSAT
NAD-Alg 25 50 75 100 125 150 175 200 225 extensions. While the good performance of NAD-Alg are expected, given the fact that this system does not encode the AF into a CSP problem, we would have expected all the others to perform somehow similarly. The behaviour observed in Figure 1 is confirmed by the results shown in Table 1. While the average runtime of AspartixM and CONArg2 rapidly increases, NAD-Alg and PrefSAT have similar performance, even though NAD-Alg run out of time in some of the largest considered AF s.
Figure 2 presents the values of normalised IPC considering all test cases grouped w.r.t. jRj. Again, as in the previous analysis, it is possible to clearly distinguish between two clusters of solvers, and the composition of clusters is the same as before. On the other hand, it is worth noticing that relatives performance change significantly with the probability of attacks between arguments. Systems that perform well with a high probability (50 to 75 %), are slow with small (25%) probabilities. Performance of solvers within the same cluster tend to be the same on AF s with a random probability of attacks. Intuitively, in highly constrained AF s, i.e. with a large number of attacks, it is easier to enumerate preferred extensions; their number is low. If the number of attacks
CONArg2 AspartixM PrefSAT
NAD-Alg 25 50 75
RAND Fig. 2. Normalised IPC score (y axis) w.r.t. the probability of attacks (x axis) of each considered system. decrease, the number of extensions increases, thus a bigger number of search steps is required to enumerate all the possible extensions.
Table 2 shows the percentages of AF s in which each solver was able to provide a solution, and the average time w.r.t. to the probability of attacks. Concerning the ability to produce solutions, CONArg2 is the solver that is mostly affected by the probability of attacks, and PrefSAT is the only one that solves all the considered instances. The average times trend confirms the observation made with regards to the IPC score: solvers are either quick on AF s with small or high probabilities of attacks between arguments, but not on both of them.
In order to better understand the performance of the considered solvers, we performed the Friedman test, and post-hoc analysis with Wilcoxon tests. The level of confidence we used has been modified to p = 0:0125 due to the usage of the Bonferroni’s correction. The results of this analysis are shown in Table 3. We considered the performance of solvers w.r.t. the probabilities of attacks between arguments. Interestingly, the Friedman indicates that there is always a statistically significant difference between the performance of the solvers, regardless to the probability of attacks. On the other hand, the post-hoc analysis performed with the Wilcoxon on solvers with similar runtime median, indicates that the performance difference is always significant but in the RAND set. This supports what we observed in Figure 2, i.e. in the RAND set similarperforming solvers show analogous behaviours. Thus, the Wilcoxon test also suggests that the “clusters” identified by the IPC score include solvers with significantly different performance. Recently, a number of high-performance algorithms have been proposed for computing preferred extensions. They exploit two approaches: (i) using a dedicated algorithm to obtain the problem solution, or (ii) translating the problem instance at hand into an equivalent instance of a different class of problems, for which solvers are already available, an then translate the solution back to the original problem.
This paper provided the first comparison of state-of-the-art approaches which transform the preferred enumeration problem into a CSP (CONArg2), ASP (AspartixM) and SAT (PrefSAT) with the best argumentation-dedicated approach NAD-Alg. Our experimental hypothesis was that there would be a strict ordering regarding the performance, in term of CPU-time required for enumerating the preferred extensions of given AF s, of the solvers. The experimental analysis, conducted on more than 700 AF s with increasing number of arguments and attacks, proved that the hypothesis was only partially true. While in most of the cases an order is respected, i.e. NAD-Alg, PrefSAT, CONArg2 and AspartixM, we identified several cases in which: (1) PrefSAT has been the best implementation — and it is also the only one implementation that solved all the AF s considered in the experiment — and (2) AspartixM performed significantly — according to the Friedman statistic test confirmed by a post-hoc analysis with the Wilcoxon signed rank with a Bonferroni correction applied — better than CONArg2.
The take-home message of this work is that non-dedicated approaches can achieve similar (and sometimes better) performance than ad-hoc ones and, moreover, SAT-based algorithms experimentally demonstrated to be the fastest among the non-dedicated ones. While NAD-Alg performs well in “constrained” AF s, w.r.t. the percentage of attacks, PrefSAT is faster and more reliable in instances with a low number of attacks. Clearly, there are many aspects that affect algorithms’ performance, like data structures, procedures implementations, etc., thus it is hard to give definitive conclusions.
Future work include a larger experimental evaluation and, whether possible, the exploitation of a white-box approach. Looking at the design of the solvers can give further information on their performance, in particular can provide hints on procedures / design decisions that should be refined, and, potentially, drive to significant performance improvements for both CSP and not CSP-based systems.
Acknowledgements. The authors would like to acknowledge the use of the University of Huddersfield Queensgate Grid in carrying out this work. 15. Faber, W.: Answer set programming. In: Reasoning Web. Semantic Technologies for Intelligent Data Access, Lecture Notes in Computer Science, vol. 8067, pp. 162–193. Springer Berlin Heidelberg (2013) 16. Leone, N., Faber, W.: The dlv project: A tour from theory and research to applications and market. In: de la Banda, M.G., Pontelli, E. (eds.) Logic Programming, 24th International Conference, ICLP 2008, Udine, Italy, December 9-13 2008, Proceedings. Lecture Notes in Computer Science, vol. 5366, pp. 53–68. Springer (2008) 17. Modgil, S., Caminada, M.: Proof theories and algorithms for abstract argumentation frameworks. In: Argumentation in Artificial Intelligence, pp. 105–129. Springer (2009) 18. Nofal, S., Dunne, P.E., Atkinson, K.: On preferred extension enumeration in abstract argumentation. In: Proceedings of COMMA 2012. pp. 205–216 (2012) 19. Nofal, S., Atkinson, K., Dunne, P.E.: Algorithms for decision problems in argument systems under preferred semantics. Artificial Intelligence 207, 23–51 (2014) 20. Rintanen, J.: Engineering efficient planners with sat. In: the 20th European Conference on
Artificial Intelligence (ECAI). pp. 684–689 (2012) 21. Rossi, F., van Beek, P., Walsh, T.: Chapter 4 constraint programming. In: Frank van Harmelen, V.L., Porter, B. (eds.) Handbook of Knowledge Representation, Foundations of Artificial Intelligence, vol. 3, pp. 181 – 211. Elsevier (2008), http://www.sciencedirect. com/science/article/pii/S1574652607030040 22. Shaffer, J., P.: Multiple hypothesis testing. Annual Review of Psych 46, 561–584 (1995) 23. Weber, T.: A sat-based sudoku solver. In: 12th International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR). pp. 11–15 (2005)