Master-Arbeit

Masterarbeit „Algorithmische Ansätze für harte Probleme in abstrakten Argumentationssystemen“

Ansprechperson:
Prof. Dr. Matthias Thimm
Status:
in Bearbeitung

Beschreibung:

Das Forschungsgebiet der “Formalen Argumentation” befasst sich mit der Repräsentation von argumentativen Szenarien und mit der Interaktion zwischen Argumenten und Gegenargumenten. Dabei bilden die abstrakten Argumentationssysteme nach Dung[1] ein allgemeines Rahmenwerk, bei denen Argumentationsszenarien als gerichtete Graphen repräsentiert werden. Hier werden Argumente als Knoten und die Konflikte zwischen ihnen als gerichtete Kanten dargestellt. Genauer stellt eine Kante in einem solchen Graphen einen Angriff eines Arguments auf ein anderes dar. Im Kontext solcher abstrakter Argumentationssysteme ist es üblicherweise von Interesse, sogenannte Extensionen zu identifizieren, d.h. Mengen von Argumenten, die gemeinsam akzeptierbar sind und somit eine kohärente Perspektive auf das Ergebnis der Argumentation bieten. Auch wenn abstrakte Argumentationssysteme einen recht einfachen Formalism darstellen, so ist eine “kohärente Perspektive” ein nicht eindeutig zu definierender Begriff. Aus diesem Grund gibt es eine Reihe verschiedener Semantiken [2] für abstrakte Argumentationssysteme, die verschiedene Interpretationen dieses Begriffs implementieren. Eine recht neue Familie von Semantiken sind die “weak admissibility-based semantics” [3], die eine Menge von Argumenten als akzeptabel betrachten, wenn sie 1.) keine internen Konflikte haben und 2.) es keinen unverteidigten Angriff eines akzeptablen Arguments auf die Menge gibt (für die formale Definition siehe [3]). Ein großer Nachteil dieser neuen Semantiken ist die hohe Komplexität typischer Fragestellungen, so ist beispielsweise das Problem zu entscheiden, ob ein gegebenes Argument akzeptabel ist PSPACE-vollständig [4].

In dieser Masterarbeit sollen algorithmische Ansätze entworfen und evaluiert werden, die Schlussfolgerungsprobleme zu “weak admissibility-based semantics” lösen können. Aufgrund der theoretischen Ergebnisse aus [4] liegen Kodierungen dieser Probleme mit “Quantified Boolean Formulas” (QBF) und Nutzung von QBF-Solvern nahe. Allerdings sollen in dieser Masterarbeit auch andere Paradigmen wie Automatisches Planen, allgemeine Suchalgorithmen oder generall für PSPACE-vollständige Probleme konzipierte Algorithmenparadigmen für ihre Verwendbarkeit exploriert werden.

  • [1] Dung, P. M. (1995). On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial intelligence, 77(2) (pp. 321-357).
  • [2] Baroni, P., Caminada, M., and Giacomin, M. (2018). Abstract Argumentation Frameworks and Their Semantics. In Handbook of Formal Argumentation, Volume 1, College Publications.
  • [3] Baumann, R., Brewka, G., and Ulbricht, M. (2020). Revisiting the Foundations of Abstract Argumentation - Semantics Based on Weak Admissibility and Weak Defense. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI’20).
  • [4] Dvorak, W., Ulbricht, M., and Woltran, S. (2021). Recursion in Abstract Argumentation is Hard - On the Complexity of Semantics Based on Weak Admissibility. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI’21).
07.06.2022