A novel method for grounding in answer-set programming

Abstract

Answer-set programming (ASP) is a declarative programming paradigm that has gained widespread popularity together with many extensions for solving a variety of problems in artificial intelligence, especially in the field of knowledge representation and reasoning. One of the key challenges in ASP is the process of grounding, which involves transforming a high-level problem specification into a set of low-level logical rules by replacing variables with constants. Grounding is crucial for the overall performance of ASP systems, as it directly affects the size and complexity of the resulting rule set, and for certain problems results in the well-known ASP grounding bottleneck, where the ground program is too huge to be processed by the ASP solver. In this thesis, we present a novel method for grounding in ASP which decouples non-ground atoms in rules in order to delegate the evaluation of rule bodies to the solving process. To this end, we present translations from non-ground, normal (tight) programs to ground, disjunctive programs as well as non-ground, disjunctive to ground epistemic logic programs. In comparison to traditional grounding systems, our translations yield programs that are exponential only in the maximum predicate arity, and thus polynomial if this arity is bounded by a constant. With the implementation of a prototype, we demonstrate technical feasibility of this new method and compare to state-of-the-art ASP technology in terms of grounding size, grounding time and total runtime. It turns out that our approach is competitive with existing systems.