Proceedings

Body-Decoupled Grounding via Solving: A Novel Approach on the ASP Bottleneck

Viktor Besin, Markus Hecher, Stefan Woltran

Video #1 Video #2 Download BibTeX Cite

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence. Main Track. Pages 2546-2552.

https://doi.org/10.24963/ijcai.2022/353

Keywords

  • Knowledge Representation and Reasoning: Computational Complexity of Reasoning
  • Knowledge Representation and Reasoning: Logic Programming

Abstract

Answer-Set Programming (ASP) has seen tremendous progress over the last two decades and is nowadays successfully applied in many real-world domains. However, for certain types of problems, the well-known ASP grounding bottleneck still causes severe problems. This becomes virulent when grounding of rules, where the variables have to be replaced by constants, leads to a ground pro- gram that is too huge to be processed by the ASP solver. In this work, we tackle this problem by a novel method that decouples non-ground atoms in rules in order to delegate the evaluation of rule bodies to the solving process. Our procedure translates a non-ground normal program into a ground disjunctive program that is exponential only in the maximum predicate arity, and thus polynomial if this arity is assumed to be bounded by a constant. We demonstrate the feasibility of this new method experimentally by comparing it to standard ASP technology in terms of grounding size, grounding time and total runtime.

Viktor Besin, Markus Hecher, and Stefan Woltran. 2022. Body-Decoupled Grounding via Solving: A Novel Approach on the ASP Bottleneck. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22. IJCAI, 2546–2552. https://doi.org/10.24963/ijcai.2022/353
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards