Splitting Assumption-Based Argumentation Frameworks | AI Research

Assumption-Based Argumentation (ABA) is a powerful tool for modeling debates and reasoning under uncertainty, but it often struggles with high computational costs. When these frameworks are converted into graph-based formats to perform reasoning, the resulting graphs can grow exponentially, making them difficult to process. This paper introduces a "splitting" technique—a divide-and-conquer strategy—that allows researchers to break down complex ABA frameworks into smaller, more manageable parts, compute results for each, and then combine them to solve the original problem efficiently.

Moving Beyond Graph Instantiation

Traditionally, splitting has been used in other areas of artificial intelligence, such as answer-set programming and abstract argumentation. While one could theoretically convert an ABA framework into a graph and then apply existing splitting methods, this approach is often inefficient. The conversion process itself can create an overwhelming number of auxiliary arguments, which defeats the purpose of splitting. To solve this, the authors propose a method that performs the splitting directly on the ABA knowledge base, bypassing the need to create massive, intermediate graphs.

Generalizing Collective Attacks

Before tackling the knowledge base directly, the authors first develop a robust splitting scheme for Argumentation Frameworks with Collective Attacks (SETAFs). SETAFs are a more concise way to represent arguments compared to standard graphs because they allow multiple arguments to attack another one simultaneously. By establishing a formal splitting theorem for SETAFs, the authors create a foundation that can be applied to any system that uses this hyper-graph representation.

The Splitting Process

The core of the approach involves three main steps: 1. Reduct: The framework is divided into two parts. The first part is solved, and the second part is "reduced" by removing arguments that are already defeated by the first part’s results. 2. Modification: The authors introduce a way to handle "undecided" links—connections between the two parts where the outcome is not yet clear. They modify the second part of the framework to account for these uncertainties, ensuring that the final combination of results remains logically sound. 3. Combination: Once the sub-frameworks are processed, their results are combined to form a complete solution for the original, larger framework.

Results and Applicability

The authors prove that this splitting method is valid for several key reasoning semantics, including complete, stable, preferred, and grounded semantics. They also extend the work to include "parameterized splitting," which allows for more flexible interactions between the divided parts of the framework. By providing a way to perform these calculations directly on the knowledge base, the research offers a more scalable path for deploying ABA in practical applications like medical decision-making and explainable AI.