Bypassing the ASP Bottleneck: Hybrid Grounding by Splitting and Rewriting

Bypassing the ASP Bottleneck: Hybrid Grounding by Splitting and Rewriting

Alexander Beiser, Markus Hecher, Kaan Unalan, Stefan Woltran

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 3250-3258. https://doi.org/10.24963/ijcai.2024/360

Answer Set Programming (ASP) is a key paradigm for problems in artificial intelligence and industrial contexts. In ASP, problems are modeled via a set of rules. Over the time this paradigm grew into a rich language, enabling complex rule types like aggregate expressions. Most practical ASP systems follow a ground-and-solve pattern, where rule schemes are grounded and resulting rules are solved. There, the so-called grounding bottleneck may prevent from solving, due to sheer grounding sizes. Recently body-decoupled grounding (BDG) demonstrated how to reduce grounding sizes by delegating effort to solving. However, BDG provides limited interoperability with traditional grounders and only covers simple rule types. In this work, we establish hybrid grounding — based on a novel splitting theorem that allows us to freely combine BDG with traditional grounders. To mitigate huge groundings in practice, we define rewriting procedures for efficiently deferring grounding effort of aggregates to solving. Our experimental results indicate that this approach is competitive, especially for instances, where traditional grounding fails.
Keywords:
Knowledge Representation and Reasoning: KRR: Logic programming
Knowledge Representation and Reasoning: KRR: Applications
Knowledge Representation and Reasoning: KRR: Computational complexity of reasoning
Knowledge Representation and Reasoning: KRR: Non-monotonic reasoning