Overcoming the Grounding Bottleneck Due to Constraints in ASP Solving: Constraints Become Propagators

Bernardo Cuteri, Carmine Dodaro, Francesco Ricca, Peter SchüllerIJCAI 2020 · DOI

TL;DR

This paper introduces a novel method to tackle the "grounding bottleneck" in Answer Set Programming (ASP) by automatically compiling problematic constraints into efficient propagators within the CDCL solver. This approach significantly outperforms existing ASP systems, especially on benchmarks with computationally expensive constraints, by avoiding the massive intermediate propositional programs generated by traditional grounding.

What Problem Does This Paper Address?

Answer Set Programming (ASP) is a powerful declarative language for knowledge representation and reasoning, widely used in AI. Traditional ASP systems rely on a "ground-and-solve" approach: first, a "grounder" translates the input program (potentially with variables) into a propositional equivalent, and then a solver computes stable models. However, this process can hit a "grounding bottleneck" when certain constraints, especially those modeling complex problem conditions, lead to an explosion in the size of the propositional program, making it computationally infeasible. This is particularly problematic for hard combinatorial problems. While some solutions like lazy grounding or hybrid formalisms exist, they have limitations. This paper aims to overcome this bottleneck by integrating constraint propagation directly into the solver's core reasoning mechanism.

Methods

The core innovation is an automatic compilation process that transforms non-ground ASP constraints into specialized C++ procedures, acting as "propagators" within a CDCL-based ASP solver. Unlike previous approaches that might instantiate constraints lazily or require manual implementation, this method compiles constraints into code that operates directly on partial interpretations during the search for stable models.

The process involves:

  1. Constraint Compilation: A compiler (Algorithms 2, 3, and 4) takes a non-ground constraint and generates C++ code for a propagator. This code is designed to infer new literals based on the constraint and the current partial interpretation.
  2. Propagator Integration: The generated C++ code is loaded as a dynamic library into the WASP solver, which uses a CDCL algorithm. These custom propagators are invoked alongside the solver's standard propagation steps.
  3. Partial Interpretation Reasoning: The generated propagators are designed to work efficiently with partial interpretations, meaning they can make inferences even when not all literals are assigned a truth value. This is a key difference from some previous methods.
  4. Automatic Translation: The compilation is automatic, meaning developers don't need to write imperative code for propagators, preserving the declarative nature of ASP.

Datasets

The paper evaluates its approach on several benchmarks commonly used in ASP competitions or found in the literature. These include:

  • Incremental Scheduling
  • Natural Language Processing (NLP) with three different objective functions (cardinality, coherence, weighted abduction)
  • Packing
  • Partner Units

These benchmarks were chosen specifically because they contain at least one constraint whose grounding is computationally expensive. No new benchmarks were introduced.

Key Insights and Ideas

  • Constraints as First-Class Propagators: The most significant insight is treating complex constraints not as something to be fully instantiated, but as a source of inference rules (propagators) that can be dynamically integrated into the solver.
  • Partial Interpretation Propagation is Key: The success hinges on designing propagators that can reason effectively on partial assignments, which is crucial for efficiency during the search process.
  • Automatic Compilation Preserves Declarativity: By automating the translation of constraints into propagators, the paper retains the declarative benefits of ASP while gaining the performance of imperative propagation.
  • Grounding Bottleneck is Constraint-Specific: The paper highlights that the grounding bottleneck is often caused by a few specific, hard-to-ground constraints, making targeted compilation a highly effective strategy.

Key Results

The proposed approach, implemented as WASP-EAGER, significantly outperforms state-of-the-art ASP systems, including CLINGO, WASP, and the lazy-grounding system ALPHA, across various benchmarks.

  • Instance Solved: WASP-EAGER solved 71, 73, and 79 more instances than CLINGO, WASP, and WASP-LAZY, respectively.
  • Benchmark Performance: It outperformed traditional systems (CLINGO, WASP) on all benchmarks. WASP-EAGER was particularly effective on the "Packing" benchmark, where CLINGO and WASP failed to ground any instances due to memory limits.
  • Solving Times: A cactus plot (Figure 1) shows that WASP-EAGER solves the majority of instances much faster than other systems, demonstrating superior scalability.
  • WASP-LAZY Comparison: While WASP-LAZY (another lazy approach) was competitive on NLP, WASP-EAGER generally outperformed it, especially on harder problems where WASP-LAZY's lazy instantiation led to many failed stable model checks.

Limitations and Future Work

  • Aggregates Not Supported: The current implementation does not support the compilation of aggregates, which are a common ASP construct.
  • Future Work: The authors plan to extend their implementation to support other ASP constructs, such as aggregates, and continue to explore optimizations. They also suggest that this approach could be beneficial for other constraint-heavy AI problems.

Summary updated

BibTeX
@inproceedings{cuteri2020overcoming,
  author = {Bernardo Cuteri and Carmine Dodaro and Francesco Ricca and Peter Schüller},
  title = {{Overcoming the Grounding Bottleneck Due to Constraints in ASP Solving: Constraints Become Propagators}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/234},
}
Figure