Computing Preferred Extensions in Abstract Argumentation: A SAT-Based Approach

Federico Cerutti, Paul E. Dunne, Massimiliano Giacomin, Mauro Vallati

Abstract

Abstract Argumentation Frameworks (AFs) provide a formal structure for reasoning about conflicting information. A central challenge in this field is the computation of preferred extensions—maximal sets of arguments that are both conflict-free and self-defending. This paper presents PrefSat, an approach that reduces the search for preferred extensions to a series of Boolean Satisfiability (SAT) queries. By employing an iterative depth-first search strategy and optimized logical encodings, PrefSat significantly outperforms traditional Answer Set Programming (ASP) and dedicated solvers in terms of speed, memory efficiency, and robustness.

Introduction

In Artificial Intelligence, Abstract Argumentation Frameworks (AFs) represent arguments as nodes in a directed graph, where edges signify "attacks" between arguments. Determining which arguments can be collectively accepted requires identifying "extensions" under specific semantics.

Examples of Abstract Argumentation Frameworks (AF1-AF4) showing various attack relations.

The preferred semantics is particularly important as it identifies maximal sets of arguments that can defend themselves against any attacker. However, finding these extensions is computationally demanding, often exceeding the complexity of NP-complete problems. While theoretical properties are well-documented, practical tools for large-scale AFs have historically struggled with scalability and memory constraints.

The PrefSat Methodology

The authors propose PrefSat, which frames the problem as a search through the space of "complete labellings." In this model, every argument is assigned one of three states: in (accepted), out (rejected), or undec (undecided).

SAT Encoding and Search Strategy

The core of PrefSat involves translating the constraints of a complete extension into a Boolean formula in Conjunctive Normal Form (CNF). The algorithm then follows an iterative process:

  1. Initial Query: A SAT solver identifies a valid complete extension.
  2. Superset Search: The algorithm adds constraints to the solver to check for the existence of a larger set (a superset) that also constitutes a complete extension.
  3. Maximality: This process repeats until no larger set is found, at which point a preferred extension is identified.
  4. Enumeration: The found extension and its subsets are blocked, and the search continues to find all unique preferred extensions.

Optimizing Logical Encodings

The performance of SAT solvers is highly sensitive to how constraints are logically represented. The authors evaluated six distinct encodings ($C_1$ through $C_3$), each offering a different logical perspective on the attack relations.

Empirical results showed that the $C_2$ encoding, which utilizes directional constraints of the attack relation, was the most efficient, particularly when dealing with dense graphs.

Experimental Results

The approach was benchmarked using 2,816 randomly generated AFs with varying sizes (up to 200 arguments) and attack densities. PrefSat was implemented using the Glucose and PrecoSAT solvers and compared against state-of-the-art ASP-based systems like ASPARTIX.

Performance and Robustness

  • Success Rate: PrefSat (using the Glucose solver) solved 100% of the test cases within a 15-minute limit. In contrast, competing ASP and dedicated algorithms saw success rates drop as the number of arguments increased, failing on up to 40% of the largest cases.
  • Computational Speed: PrefSat demonstrated significant speedups, often performing 10 to 100 times faster than the next best system on frameworks with 200 arguments.
  • Resource Efficiency: Unlike dedicated algorithms that frequently failed due to memory exhaustion, the SAT-based approach maintained a stable and manageable memory footprint.

Conclusion

PrefSat demonstrates that modern, highly optimized SAT solvers can effectively tackle the high-level complexity of preferred extension enumeration. By treating the problem as an iterative search over optimized logical encodings, the authors provide a tool that is both faster and more reliable than previous state-of-the-art solutions. Future work includes exploring MaxSAT formulations and extending the framework to handle infinite argumentation sets.

Reference: Cerutti, F., Dunne, P. E., Giacomin, M., & Vallati, M. (2013). Computing Preferred Extensions in Abstract Argumentation: a SAT-based Approach. Technical Report. arXiv:1310.4986v2 [cs.AI].

Summary updated

BibTeX
@inproceedings{cerutti2013computing,
  author = {Federico Cerutti and Paul E. Dunne and Massimiliano Giacomin and Mauro Vallati},
  title = {{Computing Preferred Extensions in Abstract Argumentation: A SAT-Based Approach}},
  booktitle = {TAFA},
  year = {2013},
  doi = {10.1007/978-3-642-54373-9\_12},
}
Figure