[Zurück]

Z. G. Saribatur, T. Eiter, P. Schüller:
"Abstraction for Non-Ground Answer Set Programs";
Berichts-Nr. LOGCOMP RR-1923-19-01, 2019; 98 S.

Abstraction is an important technique utilized by humans in model building and problem
solving, in order to figure out key elements and relevant details of a world of interest. This naturally
has led to investigations of using abstraction in AI and Computer Science to simplify problems,
especially in the design of intelligent agents and automated problem solving. By omitting details,
scenarios are reduced to ones that are easier to deal with and to understand, where further details are
added back only when they matter. Despite the fact that abstraction is a powerful technique, it has not
been considered much in the context of nonmonotonic knowledge representation and reasoning, and
specifically not in Answer Set Programming (ASP), apart from some related simplification methods.
In this work, we introduce a notion for abstracting from the domain of an ASP program such that the
domain size shrinks while the set of answer sets (i.e., models) of the program is over-approximated.
To achieve the latter, the program is transformed into an abstract program over the abstract domain
while preserving the structure of the rules. We show in elaboration how this can be also achieved
for single or multiple sub-domains (sorts) of a domain, and in case of structured domains like grid
environments in which structure should be preserved. Furthermore, we introduce an abstraction-
&-refinement methodology that makes it possible to start with an initial abstraction and to achieve
automatically an abstraction with an associated abstract answer set that matches an answer set of
the original program, provided that the program is satisfiable. Experiments based on prototypical
implementations reveal the potential of the approach for problem analysis, by its ability to focus on
the parts of the program that cause unsatisfiability and by achieving concrete abstract answer sets that
merely reflect relevant details. This makes domain abstraction an interesting topic of research whose
further use in important areas like Explainable AI remains to be explored.

http://www.kr.tuwien.ac.at/research/reports/rr1901.pdf

Projektleitung Peter Schüller:
AI4EU