Abstract
Answer Set Programming (ASP) faces a significant challenge known as the "grounding bottleneck," where rules with many variables or large domains lead to an exponential explosion in the size of the propositional program. This paper introduces a hybrid grounding strategy implemented in the tool NaGG (Novel AggreGate Grounder). By combining traditional grounding with Body-Decoupled Grounding (BDG) and a novel aggregate rewriting technique, NaGG allows ASP systems to selectively delegate complex rules to the solver. Experimental results across various benchmarks demonstrate that NaGG can reduce grounding sizes by orders of magnitude and solve instances that are intractable for state-of-the-art grounders like gringo and idlv.
Introduction
ASP is a popular framework for solving hard combinatorial problems, such as scheduling or industrial configuration. Most ASP systems follow a "ground-and-solve" pattern: first, a grounder replaces all variables in a logic program with constant values to create a propositional version; then, a high-performance solver finds solutions.
The "bottleneck" occurs during grounding. Rules with many variables or operations over large domains can cause the number of ground rules to explode, exhausting memory before solving begins. While Body-Decoupled Grounding (BDG) was proposed to mitigate this, it lacked interoperability with standard grounders and did not support essential features like aggregates (e.g., count or sum).
Methods
This research introduces two primary technical contributions to overcome these limitations:
- Hybrid Grounding via a Splitting Theorem: The authors developed a theorem allowing a program to be split into a "dense" part (handled via BDG) and a "cyclic/slim" part (handled via traditional grounding). This hybrid approach uses auxiliary "primed" predicates to ensure interoperability while maintaining founded answer set semantics.
- Aggregate Rewriting: Aggregates often trigger grounding explosions. NaGG rewrites monotonic aggregates (e.g.,
count >= k) into simpler rules with lower arity (fewer arguments). This effectively shifts the combinatorial heavy lifting from the grounder to the solver's search heuristics.
Evaluation and Results
NaGG was evaluated across four benchmark scenarios: Polygamy Stable Matching (S1), Relaxed NPRC (S2), Traffic Connector (S3), and Count Traffic Connectors (S4). These benchmarks varied instance and rule density to stress-test the limits of traditional grounding.
As shown in Table 1, NaGG significantly outperforms standard grounders. In the "Traffic Connector" (S3-T6) benchmark, traditional grounders like gringo and idlv solved only about 200 instances, while NaGG solved over 2,000—a tenfold improvement.
The cactus plot in Figure 1 further illustrates this scalability. While traditional grounders fail exponentially as problems become denser, NaGG's performance remains relatively stable. In some instances, NaGG reduced the grounding size by a factor of 1,000, demonstrating that the real enemy of grounding is arity, not just variable count.
Conclusion
By delegating "dense" rules to the solver and rewriting complex aggregates, NaGG successfully bypasses the ASP grounding bottleneck. This hybrid approach offers the best of both worlds: the speed of traditional grounding for simple rules and the scalability of BDG for complex ones. Future work will focus on deeper integration into core ASP toolchains and automated rule delegation based on structural parameters like treewidth.
Summary updated