Heureka: A General Heuristic Backtracking Solver for Abstract Argumentation

Abstract

The heureka solver is a general-purpose solver for various problems in abstract argumentation frameworks pertaining to complete, grounded, preferred and stable semantics. It is based on a backtracking approach and makes use of various heuristics to optimize the search.

– I have found it! I have found it!

– Archimedes of Syracuse (287–212 BC)

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

An abstract argumentation framework (AAF) as defined by Dung [3] is a tuple $\varGamma =(\mathcal {A},\mathcal {R})$ where $\mathcal {A}$ is a set of arguments and $\mathcal {R}\subseteq \mathcal {A}^2$ an attack relation between arguments. An attack $a\rightarrow b\in \mathcal {R}$ models that argument a defeats argument b. For any argument set $E\subseteq \mathcal {A}$, let $E^+$ be the set of arguments which are attacked by an element of E and let $E^-$ be the set of arguments which attack an element of E. An AAF $\varGamma$ is interpreted through the use of extensions, i.e., sets of arguments that provide a coherent view on the argumentation represented by $\varGamma$. An extension $E\subseteq \mathcal {A}$ is conflict-free iff there are no $a,b\in E$ with $a\rightarrow b$. An extension E is stable iff it is conflict-free and for every $b\in \mathcal {A}\setminus E$ there is $a\in E$ with $a\rightarrow b$. Other notions of extensions include complete, grounded, and preferred extensions, see [3] for the formal definitions.

heureka is a software system that implements a direct backtracking approach for solving reasoning problems with respect to stable, complete, grounded, and preferred semantics. The backtracking approach makes use of a variety of heuristics to dynamically (re-)order the arguments to minimize the backtracking steps. heureka is able to solve the problems of

• enumerating all extensions (EE),

• determining a single extension (SE),

• checking whether an argument is part of at least one extension, i.e., whether it is creduously justifiable (DC), and

• checking whether an argument is part of every extension, i.e., whether it is sceptically justifiable (DS)

with respect to the four mentioned semantics. heureka is written in C++ and available under the LGPL v3.0 licence on GitHub¹.

In the remainder of this paper, we describe the architecture of heureka as it has been submitted to the Second International Competition on Computational Models of Argumentation (ICCMA’17) ². Note that a slightly shorter version of this paper has also been submitted as a system description to the competition.

2 Backtracking Algorithm

heureka consists of a family of backtracking algorithms, one for each complete, preferred, and stable semantics which are similar to the algorithm defined in [5] but use dynamic heuristics to (re-)order how arguments are processed. The concrete algorithms differ only slightly so we focus our presentation here on the stable semantics and, in particular, on the task of computing all stable extensions.

At any time during the execution, a labelling function $\mathcal {L}ab$, which assigns to each argument either the value $\mathrm {IN}$ if it should be contained in the extension, $\mathrm {OUT}$ if it should be ruled out, or $\mathrm {UNDEC}$ if it is undecided, is maintained by the algorithm that keeps track of the current (partial) extension. A fourth label ($\mathrm {BLANK}$) is used to indicated that an argument is not labelled yet. Let further $\mathrm {IN}(\mathcal {L}ab)$ be the set of all arguments labelled $\mathrm {IN}$ by $\mathcal {L}ab$, and therefore the current solution. In a first step, the grounded extension $E_\mathrm {GR}$ is computed using a purely iterative algorithm which does not require backtracking [4] and an intial labelling is constructed. For an AAF $\varGamma =(\mathcal {A},\mathcal {R})$ with the grounded extension $E_\mathrm {GR}$ let the initial labelling $\mathcal {L}ab_\mathrm {init}:\mathcal {A}\rightarrow \{\mathrm {IN}, \mathrm {OUT},\mathrm {UNDEC},\mathrm {BLANK}\}$ be defined as

$$\begin{aligned} \mathcal {L}ab_\mathrm {init}(a) = {\left\{ \begin{array}{ll} \mathrm {IN} &{} \text {if } a\in E_{\mathrm {GR}} \\ \mathrm {OUT} &{}\text {if } a\in E_{\mathrm {GR}}^+\\ \mathrm {UNDEC} &{}\text {if } a\rightarrow a \\ \mathrm {BLANK} &{} \text {otherwise} \end{array}\right. } \end{aligned}$$

Using a specific heuristic (see next section) a new argument a is selected and set to $\mathrm {IN}$ in $\mathcal {L}ab$. Setting this argument to $\mathrm {IN}$ may require that other arguments have to be rejected (because they are attacked by a) or need to be set to $\mathrm {IN}$ as well (because all attackers of them are now attacked by some $\mathrm {IN}$-labelled argument), and so on, see [5] for the corresponding lookahead strategies. Those arguments are then marked correspondingly in $\mathcal {L}ab$. This step is repeated until either a stable extension has been determined or a contradiction occurs (an argument is labelled with two different labels). In the latter case, the algorithm backtracks and rejects an argument previously accepted. Algorithm 1 shows a shortened version of this procedure. The functions Set_In and Set_Undec set the labelling of the current argument to $\mathrm {IN}$ or $\mathrm {undec}$, respectively, and propagate the changes following the mentioned lookahead strategies. For example all arguments attacked ba an argument labelled $\mathrm {IN}$ are set to $\mathrm {OUT}$. At the end of Set_In, the algorithm checks whether the current extension, i.e., the set of $\mathrm {IN}$-labelled arguments in $\mathcal {L}ab$, is stable, then it is reported as a stable extension and the algorithm backtracks as the current branch cannot contain any more extensions.

Fig. 1.

AAF $\varGamma$ (left) and algorithm steps (right) from Example 1; arguments not present in any set are $\mathrm {BLANK}$

Example 1

Consider the AAF $\varGamma =(\mathcal {A},\mathcal {R})$ depicted in Fig. 1 (left). Assume our heuristic function determines the following order of arguments: (a, b, c, d, e). In the first step, we determine that the grounded extension is empty and that there is no self-attacking argument, so we start with an empty labelling (all arguments are blank).

• 1. decision: a is picked by the heuristic and set to IN

• 2. as a consequence of step 1, all attackers/attackees of a are set to UNDEC/OUT respectively, $\{a\}$ is not stable

• 3. decision: c is picked by the heuristic and set to IN

• 4. as a consequence of step 3, all attackers/attackees of c are set to UNDEC/OUT respectively, $\{a, c\}$ is not stable

• 5. there are no more arguments which are still undecided, so the algorithm backtracks to the last decision in step 3 and sets c to OUT

• 6. decision: d is picked by the heuristic and set IN

• 7. as a consequence of step 6, all attackers/attackees of d are set to UNDEC/OUT respectively, $\{a, d\}$ is stable $\Rightarrow$ stop

The backtracking algorithms for preferred and complete semantics are similar to the one for stable semantics. Reasoning problems pertaining to credulous/sceptical justification are solved by the same algorithms but with different termination criteria and slightly different initial steps.

3 Heuristics

While it is clear that the backtracking approach outlined before is a sound and complete procedure to enumerate extensions, its performance is highly dependent on the order in which arguments are processed. Observe that if this order is perfect, i.e., all arguments within the final extension are processed first, then no backtracking is needed and the algorithm has polynomial runtime. However, this runtime performance cannot, of course, be guaranteed but the choice of the heuristic used in ordering the arguments can deeply influence the runtime in general. heureka comes with a series of different heuristics for this purpose.

In general, a heuristic h is a function $h:2^{\mathcal {A}}\times \mathcal {A}\rightarrow \mathbb {R}$ that maps the current partial extension $E\subseteq \mathcal {A}$, i.e., the set of $\mathrm {IN}$-labelled arguments in $\mathcal {L}ab$, and an argument $a\in \mathcal {A}$ to a real number h(E, a). A large value h(E, a) indicates that a should be likely included in the extension E and should be processed earlier than arguments with lower score. Some of our heuristics are defined independently of E and therefore need not to be recomputed after every modification of E. In general, however, heureka allows for dynamic heuristics that are updated after every step.

A simple example of such a heuristic is the number of undefeated aggressors, i.e., the number of arguments which attack a but are not defeated by E. The number of undefeated aggressors $h_\mathrm {UA}(E,a)$ should be used as a negatively weighted component in a compound heuristic as every aggressor increases the vulnerability of an argument.

$$\begin{aligned} h_\mathrm {UA}(E,a)=\left| \{a\}^-\backslash E^+\right| \end{aligned}$$

Another example which is independent of E is the ratio of an argument’s in-degree and out-degree:

$$\begin{aligned} h_{\mathrm {deg}}^{\mathrm {\div }}(E,a) = \frac{|\{a\}^+|+\epsilon }{|\{a\}^-|+\epsilon } \text {with} \;\epsilon \in \mathbb {R}\end{aligned}$$

Path-based heuristics have proven useful in many cases. Let $d^+_i(a)$ be the number of paths of length i originating in a and let $d^-_i(a)$ be the number of paths of length i ending in a. The path-based components $h_{\mathrm {path}}^{\mathrm {+}}$ and $h_{\mathrm {path}}^{\mathrm {-}}$ map an argument to a combination of its outgoing paths or ingoing paths respectively.

$$\begin{aligned} h_{\mathrm {path}}^{\mathrm {+}}(E,a)&= \sum \limits _{i=1}^k\alpha ^i d^+_i(a) \\ h_{\mathrm {path}}^{\mathrm {-}}(E,a)&= \sum \limits _{i=1}^k\beta ^i d^-_i(a) \end{aligned}$$

These heuristics can be combined into more complex path-based heuristics like $h_{\mathrm {path}}^{\mathrm {\Sigma }}=h_{\mathrm {path}}^{\mathrm {-}}+h_{\mathrm {path}}^{\mathrm {+}}$ or $h_{\mathrm {path}}^{\mathrm {\Pi }}= (-1)\cdot (h_{\mathrm {path}}^{\mathrm {-}}+\epsilon )\cdot (h_{\mathrm {path}}^{\mathrm {+}}+\epsilon )$.

Further heuristics have been implemented on top of well-known graph metrics such as betweenness centrality, eigenvector centrality, and matrix exponential. Another approach are SCC-based heuristics, which order arguments according to the ordering number of the strongly connected component, which they are part of, thus implementing ideas on SCC-recursiveness [1]. On top of the individual heuristics, heureka also allows heuristics to be combined arithmetically.

For ICCMA’17, we fixed a heuristic for every problem based on a small experimental evaluation. For all tasks except SE-ST (enumerating some stable extension) we used the heuristic $h_1$, i.e., $h_{\mathrm {path}}^{\mathrm {+}}$ with fixed parameters $\alpha =0.5$ and $k=3$, defined as

$$\begin{aligned} h_1(E,a) = \sum \limits _{i=1}^3 \frac{d^+_i(a)}{2^i} \end{aligned}$$

This heuristic shows the power of an argument to defend and defeat arguments. For the task SE-ST we used the heuristic $h_2$, which combines $h_{\mathrm {path}}^{\mathrm {+}}$ with $h_{\mathrm {path}}^{\mathrm {-}}$ and $h_\mathrm {{UA}}$.

$$\begin{aligned} h_2(E,a)=h_1(E,a) + \sum \limits _{i=1}^3 \frac{d^-_i(a)}{(-2)^{i}}-\frac{\left| \{a\}^-\backslash E^+\right| }{2} \end{aligned}$$

This heuristic is influenced by the matrix exponential which has been suggested for this use in [2].

Later a systematic evaluation of the implemented heuristics has been conducted. During this evaluation $h_{\mathrm {deg}}^{\mathrm {\div }}$ has proven most useful for solving problems under stable semantics while $h_{\mathrm {path}}^{\mathrm {\Pi }}$ worked best when solving problems under complete or preferred semantics. For some graphs the performance could be substantially increased by adding an SCC-based component to the heuristic. In future work, heuristics could be explored, which also discriminate between OUT and UNDEC arguments intead of only analysing the partial extension.

4 Summary

We presented heureka, a general-purpose argumentation solver based on the backtracking paradigm. The solver is backed by a number of heuristics that (dynamically) order the arguments of an abstract argumentation framework to minimize the number of necessary backtracking steps. During ICCMA’17, all results returned by heureka have been correct. It landed in the center field for most tasks, while it was the fastest to find the grounded extension. Current and future work comprises analytical and empirical evaluation of the solver and its heuristics, as well as the development of new heuristics and combinations thereof.