Author name cluster

Sarah Alice Gaggl

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers

2 author rows

KR Conference 2025 Conference Paper

Grounding Rule-Based Argumentation Using Datalog

Martin Diller
Sarah Alice Gaggl
Philipp Hanisch
Giuseppina Monterosso
Fritz Rauschenbach

ASPIC+ is one of the main general frameworks for rule-based argumentation for AI. Although first-order rules are commonly used in ASPIC+ examples, most existing approaches to reason over rule-based argumentation only support propositional rules. To enable reasoning over first-order instances, a preliminary grounding step is required. As groundings can lead to an exponential increase in the size of the input theories, intelligent procedures are needed. However, there is a lack of dedicated solutions for ASPIC+. Therefore, we propose an intelligent grounding procedure that keeps the size of the grounding manageable while preserving the correctness of the reasoning process. To this end, we translate the first-order ASPIC+ instance into a Datalog program and query a Datalog engine to obtain ground substitutions to perform the grounding of rules and contraries. Additionally, we propose simplifications specific to the ASPIC+ formalism to avoid grounding of rules that have no influence on the reasoning process. Finally, we performed an empirical evaluation of a prototypical implementation to show scalability.

PDF Details DOI

KR Conference 2025 System Paper

Interactive Exploration of Plan Spaces

Daniel Gnad
Markus Hecher
Sarah Alice Gaggl
Dominik Rusovac
David Speck
Johannes K. Fichte

Many planning applications require not only a single solution but benefit substantially from having a set of possible plans from which users can select, for example, when explaining plans. For decades, research in classical AI planning has primarily focused on quickly finding single plans. Only recently researchers have started to investigate preferences, enumerate plans by top-k planning, or count plans to reason about the plan space. Unfortunately, reasoning about the plan space is computationally extremely hard and feeding many similar plans to the user is hardly practical. To circumvent computational shortcomings while still being able to reason about variability in plans, faceted actions have been introduced very recently. These are meaningful actions that can be used by some plan but are not required by all plans. Enforcing or forbidding such facets allows for navigating even large plan spaces while ensuring desired properties quickly and step by step. In this paper, we illustrate an industrial challenge, the Beluga logistics problem of Airbus, where reasoning with facets enables targeted plan space navigation. We present an approach to handle large plan spaces iteratively and interactively and present a tool that we call PlanPilot.

PDF Details DOI

KR Conference 2024 Conference Paper

Navigating and Querying Answer Sets: How Hard Is It Really and Why?

Dominik Rusovac
Markus Hecher
Martin Gebser
Sarah Alice Gaggl
Johannes K. Fichte

Answer set programming is a popular declarative paradigm with countless applications for modeling and solving combinatorial problems. We can view a program as a knowledge database compactly representing conditions for solutions. Often we are interested in reasoning about solutions of filtering answer sets. At the heart of these questions is brave and cautious reasoning. For browsing answer sets, we combine both as restricting atoms of answer sets is only meaningful for atoms called facets that belong to some (brave) but not to all answer sets (cautious). Surprisingly, the precise computational complexity of facet problems remained widely open so far. In this paper, we study the complexity of answer set facets. We establish tight results for reasoning with facets, deciding upper and lower bounds as well as the exact number of facets, and comparing facets. Facet reasoning seems to be a natural problem formalism, residing in complexity families Σᴾ, Πᴾ, Dᴾ, and Θᴾ, up to the third level. Moreover, our study considers quantitative importance questions on facets and generalizing from facets to conjunctions, disjunctions, and arbitrary queries. We complete our results by an experimental evaluation.

PDF Details DOI

NMR Workshop 2024 Invited Paper

Navigating ASP Solution Spaces (Invited Talk, Abstract)

Sarah Alice Gaggl

A wide range of combinatorial search problems can be modelled and solved with Answer Set Programming (ASP). While modern ASP solvers allow to quickly enumerate solutions, the user faces the problem of dealing with a possibly exponential number of solutions, which may easily go into millions and beyond. To still be able to reach an understanding of the answer set space, we propose navigation approaches to reach subspaces that fulfil desirable criteria. With weighted faceted answer set navigation we allow for a quantitative understanding of the answer set space. Weights can be assigned to atoms depending on how much they restrict the remaining solution space, either by counting the number of answer sets (resp. supported models) or counting the number of atoms still available to choose. Then, we show an iterative approach to compute a diverse collection of answer sets that allows to exchange some answer sets to improve the size and diversity of the whole collection. In contrast to diverse collections, representative answer sets do not require to specify a diversity measure. We introduce a notion of representativeness based on entropy, and discuss algorithms to collect representative collections of answer sets. Finally, we will present a visual approach to explore solution spaces and apply it to the domain of abstract argumentation.

Details

ECAI Conference 2023 Conference Paper

Representative Answer Sets: Collecting Something of Everything

Elisa Böhl
Sarah Alice Gaggl
Dominik Rusovac

Answer set programming (ASP) is a popular problem solving paradigm with applications in planning and configuration. In practice, the number of answer sets can be overwhelmingly high, which naturally causes interest in a concise characterisation of the solution space in terms of representative answer sets. We establish a notion of representativeness that refers to the entropy of specified target atoms within a collection of answer sets. Accordingly, we propose different approaches for collecting such representative answer sets, based on answer set navigation. Finally, we conduct experiments using our prototypical implementation, which reveals promising results.

Details

JAIR Journal 2022 Journal Article

Admissibility in Probabilistic Argumentation

Nikolai Käfer
Christel Baier
Martin Diller
Clemens Dubslaff
Sarah Alice Gaggl
Holger Hermanns

Abstract argumentation is a prominent reasoning framework. It comes with a variety of semantics and has lately been enhanced by probabilities to enable a quantitative treatment of argumentation. While admissibility is a fundamental notion for classical reasoning in abstract argumentation frameworks, it has barely been reflected so far in the probabilistic setting. In this paper, we address the quantitative treatment of abstract argumentation based on probabilistic notions of admissibility. Our approach follows the natural idea of defining probabilistic semantics for abstract argumentation by systematically imposing constraints on the joint probability distribution on the sets of arguments, rather than on probabilities of single arguments. As a result, there might be either a uniquely defined distribution satisfying the constraints, but also none, many, or even an infinite number of satisfying distributions are possible. We provide probabilistic semantics corresponding to the classical complete and stable semantics and show how labeling schemes provide a bridge from distributions back to argument labelings. In relation to existing work on probabilistic argumentation, we present a taxonomy of semantic notions. Enabled by the constraint-based approach, standard reasoning problems for probabilistic semantics can be tackled by SMT solvers, as we demonstrate by a proof-of-concept implementation.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Rushing and Strolling among Answer Sets – Navigation Made Easy

Johannes Klaus Fichte
Sarah Alice Gaggl
Dominik Rusovac

Answer set programming (ASP) is a popular declarative programming paradigm with a wide range of applications in artificial intelligence. Oftentimes, when modeling an AI problem with ASP, and in particular when we are interested beyond simple search for optimal solutions, an actual solution, differences between solutions, or number of solutions of the ASP program matter. For example, when a user aims to identify a specific answer set according to her needs, or requires the total number of diverging solutions to comprehend probabilistic applications such as reasoning in medical domains. Then, there are only certain problem specific and handcrafted encoding techniques available to navigate the solution space of ASP programs, which is oftentimes not enough. In this paper, we propose a formal and general framework for interactive navigation toward desired subsets of answer sets analogous to faceted browsing. Our approach enables the user to explore the solution space by consciously zooming in or out of sub-spaces of solutions at a certain configurable pace. We illustrate that weighted faceted navigation is computationally hard. Finally, we provide an implementation of our approach that demonstrates the feasibility of our framework for incomprehensible solution spaces.

PDF Details

IJCAI Conference 2022 Conference Paper

Simulating Sets in Answer Set Programming

Sarah Alice Gaggl
Philipp Hanisch
Markus Krötzsch

We study the extension of non-monotonic disjunctive logic programs with terms that represent sets of constants, called DLP(S), under the stable model semantics. This strictly increases expressive power, but keeps reasoning decidable, though cautious entailment is coNEXPTIME^NP-complete, even for data complexity. We present two new reasoning methods for DLP(S): a semantics-preserving translation of DLP(S) to logic programming with function symbols, which can take advantage of lazy grounding techniques, and a ground-and-solve approach that uses non-monotonic existential rules in the grounding stage. Our evaluation considers problems of ontological reasoning that are not in scope for traditional ASP (unless EXPTIME =ΠP2 ), and we find that our new existential-rule grounding performs well in comparison with native implementations of set terms in ASP.

PDF Details DOI

KR Conference 2021 Conference Paper

Admissibility in Probabilistic Argumentation

Christel Baier
Martin Diller
Clemens Dubslaff
Sarah Alice Gaggl
Holger Hermanns
Nikolai Käfer

Abstract argumentation is a prominent reasoning framework. It comes with a variety of semantics, and has lately been enhanced by probabilities to enable a quantitative treatment of argumentation. While admissibility is a fundamental notion in the classical setting, it has been merely reflected so far in the probabilistic setting. In this paper, we address the quantitative treatment of argumentation based on probabilistic notions of admissibility in a way that they form fully conservative extensions of classical notions. In particular, our building blocks are not the beliefs regarding single arguments. Instead we start from the fairly natural idea that whatever argumentation semantics is to be considered, semantics systematically induces constraints on the joint probability distribution on the sets of arguments. In some cases there might be many such distributions, even infinitely many ones, in other cases there may be one or none. Standard semantic notions are shown to induce such sets of constraints, and so do their probabilistic extensions. This allows them to be tackled by SMT solvers, as we demonstrate by a proof-of-concept implementation. We present a taxonomy of semantic notions, also in relation to published work, together with a running example illustrating our achievements.

PDF Details DOI

JAIR Journal 2021 Journal Article

On the Decomposition of Abstract Dialectical Frameworks and the Complexity of Naive-based Semantics

Sarah Alice Gaggl
Sebastian Rudolph
Hannes Straß

Abstract dialectical frameworks (ADFs) are a recently introduced powerful generalization of Dung’s popular abstract argumentation frameworks (AFs). Inspired by similar work for AFs, we introduce a decomposition scheme for ADFs, which proceeds along the ADF’s strongly connected components. We find that, for several semantics, the decomposition-based version coincides with the original semantics, whereas for others, it gives rise to a new semantics. These new semantics allow us to deal with pertinent problems such as odd-length negative cycles in a more general setting, that for instance also encompasses logic programs. We perform an exhaustive analysis of the computational complexity of these new, so-called naive-based semantics. The results are quite interesting, for some of them involve little-known classes of the so-called Boolean hierarchy (another hierarchy in between classes of the polynomial hierarchy). Furthermore, in credulous and sceptical entailment, the complexity can be different depending on whether we check for truth or falsity of a specific statement.

PDF Details DOI

FLAP Journal 2017 Journal Article

Foundations of Implementations for Formal Argumentation.

Federico Cerutti
Sarah Alice Gaggl
Matthias Thimm
Johannes P. Wallner

We survey the current state of the art of general techniques, as well as specific software systems for solving tasks in abstract argumentation frameworks, structured argumentation frameworks, and approaches for visualizing and analysing argumentation. Furthermore, we discuss challenges and promising techniques such as parallel processing and approximation approaches. Finally, we address the issue of evaluating software systems empirically with links to the International Competition on Computational Models of Argumentation.

PDF Details

ECAI Conference 2016 Conference Paper

Fixed-Domain Reasoning for Description Logics

Sarah Alice Gaggl
Sebastian Rudolph
Lukas Schweizer

After decades of fruitful research, description logics (DLs) have evolved into a de facto standard in logic-based knowledge representation. In particular, they serve as the formal basis of the standardized and very popular web ontology language (OWL), which also comes with the advantage of readily available user-friendly modeling tools and optimized reasoning engines. In the course of the wide-spread adoption of OWL and DLs, situations have been observed where logically less skilled practitioners are (ab)using these formalisms as constraint languages adopting a closed-world assumption, contrary to the open-world semantics imposed by the classical definitions and the standards. To provide a clear theoretical basis and inferencing support for this often practically reasonable "off-label use" we propose an alternative formal semantics reflecting the intuitive understanding of such scenarios. To that end, we introduce the fixed-domain semantics and argue that this semantics gives rise to an interesting new inferencing task: model enumeration. We describe how the new semantics can be axiomatized in very expressive DLs. We thoroughly investigate the complexities for standard reasoning as well as query answering under the fixed-domain semantics for a wide range of DLs. Further, we present an implementation of a fixed-domain DL reasoner based on a translation into answer set programming (ASP) which is competitive with alternative approaches for standard reasoning tasks and provides the added functionality of model enumeration.

Details

IJCAI Conference 2015 Conference Paper

On the Computational Complexity of Naive-Based Semantics for Abstract Dialectical Frameworks

Sarah Alice Gaggl
Sebastian Rudolph
Hannes Strass

Abstract dialectical frameworks (ADFs) are a powerful generalization of Dung’s abstract argumentation frameworks. ADFs allow to model argumentation scenarios such that ADF semantics then provide interpretations of the scenarios. Among the considerable number of ADF semantics, the naivebased ones are built upon the fundamental concept of conflict-freeness. Intuitively, a three-valued interpretation of an ADF’s statements is conflict-free iff all true statements can possibly be accepted, and all false statements cannot possibly be accepted. In this paper, we perform an exhaustive analysis of the computational complexity of naive-based semantics. The results are quite interesting, for some of them involve little-known classes of the so-called Boolean hierarchy (another hierarchy in between classes of the polynomial hierarchy). Furthermore in credulous and sceptical entailment, the complexity can be different depending on whether we check for truth or falsity of a specific statement.

PDF Details