From International Center for Computational Logic
Toggle side column


Navigation Approaches for Answer Sets

Due to the continuous development in recent years, a large number of demanding combinatorial search problems of enormous practical relevance can now be efficiently solved by Answer Set Programming (ASP). Depending on the scope of the problem to be solved, a "combinatorial explosion" of the number of solutions can occur very quickly. While modern ASP solvers can easily calculate several million solutions in a short time, this poses a new problem for the user: How should the enormous solution space be handled and made accessible? Typically, the Answer Sets are output in any order. However, many of these solutions are very similar. In practice, however, often only solutions are of interest that are sufficiently different from each other, that have special properties, or that are similar to a given set of solutions. Such features are not yet supported by ASP solvers. To enable an interactive and transparent navigation in ASP solution spaces the project NAVAS will deal with the following topics:

  1. Development of methods for interactive and transparent navigation in the Answer Set solution space;
  2. Implementation of the methods with efficient algorithms;
  3. Evaluation of the prototype on use cases from the areas of configuration and argumentation theory.

We are confident that the knowledge, developments and implementations achieved in NAVAS will make ASP technology more accessible to a wider audience. We see a particular immediate potential in the area of industrial applications, for example product configuration.

Journal Articles

Sarah Alice Gaggl, Sebastian Rudolph, Hannes Strass
On the Decomposition of ADFs and the Complexity of Naive-based Semantics
Journal of Artificial Intelligence Research, 70:1-64, January 2021
Details Download