Solving Advanced Argumentation Problems with Answer-Set Programming

Gerhard Brewka, Martin Diller, Georg Heissenberger, Thomas Linsbichler, Stefan WoltranAAAI 2017 · DOI

Presented at AAAI-17, this research addresses the computational challenges of modern formal argumentation. By employing a "dynamic encoding" strategy within Answer-Set Programming (ASP), the authors demonstrate a method to solve complex reasoning tasks—some reaching the third level of the polynomial hierarchy—using a single call to an ASP solver.

The Challenge of Expressive Argumentation

Formal argumentation models conflict resolution and decision-making. While early models like Dung’s Argumentation Frameworks were simple graphs, modern frameworks such as Abstract Dialectical Frameworks (ADFs) and GRAPPA allow for sophisticated logic (e.g., a statement is accepted only if a specific combination of supporters is active).

However, this expressiveness introduces significant computational costs. Reasoning in these frameworks often reaches the second or third levels of the polynomial hierarchy ($\\Sigma^P_2$ or $\\Pi^P_3$). Existing tools frequently suffer from "complexity mismatch," requiring multiple expensive solver calls or facing exponential blowups during translation.

Methodology: Dynamic Encoding and Saturation

The researchers developed YADF, a tool that utilizes Dynamic Encoding in ASP. Unlike standard static encoding, which uses a general program for all data, dynamic encoding generates a unique ASP program for every specific argumentation instance. By embedding the logic of the problem directly into the ASP rules, the system taps into ASP's "combined complexity," which matches the third level of the polynomial hierarchy.

To handle "preferred semantics"—which require finding maximal sets of compatible arguments—the authors used a technique called Saturation. This ASP pattern allows the solver to verify set maximality within a single search branch, avoiding the need for iterative solver calls.

Experimental Evaluation

The authors evaluated YADF against the ASP-based system DIAMOND and the QBF-based system QADF using three benchmarks:

  1. Grid-based ADFs: Statements arranged in a grid with neighbor dependencies.
  2. Metro ADFs: A new benchmark based on real-world public transport network structures from eight cities.
  3. Dense Random Graphs: Testing limits under high connectivity.

Performance Results

Figure 1: Comparison of solved instances over time for different solvers and semantics.

YADF demonstrated significant dominance in skeptical reasoning under preferred semantics (skept-prf), the most computationally demanding task. As shown in the performance curves, YADF solved substantially more instances within the time limit compared to DIAMOND and QADF.

Figure 3: Detailed benchmark results for Grid (Gri) and Metro instances, showing runtimes and timeouts (in parentheses).

Specific benchmark data reveals that while DIAMOND and QADF timed out on grid instances with more than 30 statements for skeptical reasoning, YADF successfully processed instances with up to 80 statements. Furthermore, YADF showed a clear advantage on the structured "Metro" graphs, suggesting better handling of real-world-like dependency structures.

Insights and Future Work

The core contribution is the realization that the combined complexity of ASP is perfectly suited for high-level argumentation tasks. Furthermore, GRAPPA’s acceptance patterns (sums, counts, minimums) map naturally to ASP’s aggregates, making it a more efficient target than Quantified Boolean Formulas (QBF).

While YADF excels on structured data, the authors noted that on extremely dense random graphs, older systems like DIAMOND occasionally performed better, likely due to the long rule bodies generated by dynamic encoding. Future work will focus on extending this method to other semantics (like grounded or ideal) and optimizing rule generation for high-density frameworks.

Summary updated

BibTeX
@inproceedings{brewka2017solving,
  author = {Gerhard Brewka and Martin Diller and Georg Heissenberger and Thomas Linsbichler and Stefan Woltran},
  title = {{Solving Advanced Argumentation Problems with Answer-Set Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10682},
}
Figure