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

Viktor Besin, Markus Hecher, Stefan WoltranIJCAI 2022 · DOI

TL;DR

This paper introduces "body-decoupled grounding," a novel technique for Answer-Set Programming (ASP) that tackles the "grounding bottleneck." By intelligently deferring the evaluation of complex rule bodies to the solving phase, this approach significantly reduces the size of intermediate programs, leading to faster overall computation, especially for large and dense problem instances.

What Problem Does This Paper Address?

Answer-Set Programming (ASP) is a powerful declarative programming paradigm used for knowledge representation and reasoning. A crucial step in ASP is "grounding," where variables in rules are replaced by constants to create a propositional program that a solver can process. However, for certain problems, this grounding process can lead to an exponential explosion in program size, making it computationally intractable – this is known as the "grounding bottleneck." This bottleneck severely limits the applicability of ASP to real-world problems with complex rule structures.

Methods

The core contribution is a novel reduction technique that "decouples" the evaluation of rule bodies from the initial grounding process. Instead of fully instantiating all parts of a rule, the proposed method translates non-ground rules into a ground disjunctive program where the evaluation of rule bodies is delegated to the ASP solver.

Specifically, the approach involves:

  • Tight Programs: For tight (cycle-free) non-ground programs, the method translates them into ground disjunctive programs. This translation uses auxiliary atoms to manage satisfiability and prevent unfoundedness, effectively encoding the grounding process within the solver's search. The complexity of this translation is polynomial in the program size and the maximum predicate arity.
  • Normal Programs: The technique is extended to normal (non-disjunctive) programs by incorporating ordering or level mappings into the reduction. This ensures that the foundedness condition for answer sets is correctly handled.
  • Partial Reducibility: The system allows users to select specific parts of a program for this body-decoupled grounding, while other parts can be grounded traditionally. This flexibility is crucial for integrating the approach into existing ASP workflows.
  • Variable Independencies: The method leverages variable independencies within rule bodies to further optimize the grounding process, making it less sensitive to instance density.

Datasets

The paper does not introduce new datasets. Instead, it uses a series of crafted (random) and application-based ASP competition instances for evaluation. These scenarios include:

  • S1 (coloring): Edge coloring problems.
  • S2 (paths): Finding reachable paths in graphs.
  • S3 (clique): Identifying cliques in directed subgraphs.
  • S4 (nprc): Non-partition-removal colorings.
  • S5 (stable marriage): A standard ASP competition problem.

The randomly generated instances for S1-S4 range from 100 to 1500 vertices with varying edge probabilities (densities).

Key Insights and Ideas

  • Decoupling as a Solution: The fundamental insight is that not all parts of a rule need to be fully grounded upfront. By deferring complex body evaluations, we can avoid the exponential blow-up.
  • Solver as Grounder: The reduction cleverly uses the ASP solver itself to perform the "grounding" of rule bodies, transforming the problem from a grounding bottleneck to a potentially more manageable solving problem.
  • Arity Matters: The approach's polynomial complexity is tied to the maximum predicate arity, suggesting that it's particularly effective for problems where predicates, while potentially having many variables, don't have an excessively high arity.
  • Practical Applicability: The partial reducibility and integration with existing grounders (like gringo and idlv) make this a practical technique rather than a purely theoretical one.

Key Results

The experimental evaluation demonstrates significant advantages of the body-decoupled grounding approach:

  • Reduced Grounding Size: The newground system consistently and massively reduces grounding sizes compared to traditional grounders like gringo and idlv, especially for large instances. In some cases, newground solves instances where gringo and idlv produce groundings exceeding 30GB.
  • Improved Grounding Times: Body-decoupled grounding leads to substantial speed-ups in grounding times, making it less sensitive to instance density.
  • Overall Performance Gains: While the primary focus is on grounding, the improvements often translate to better overall (grounding + solving) performance, particularly for instances that would otherwise be intractable due to large groundings.
  • Hypothesis Confirmation: The results largely confirm the hypotheses H1-H4, indicating that newground suffers less from increased instance density and size, can massively reduce grounding artifacts, improves overall performance, and can effectively interoperate with other approaches.

Limitations and Future Work

  • Disjunctive Programs: The current reduction is primarily for tight (and normal) programs. Extending it to general disjunctive non-ground programs, which is inherently more complex (Π₂ᶜ-complete for bounded arity), is a significant future challenge. The authors suggest that "almost tightness" notions might help.
  • Heuristics for Integration: The authors plan to integrate their approach into intelligent grounders by developing heuristics to automatically identify program parts where body-decoupled grounding is most beneficial.
  • Solver Optimization: Further optimization of the ASP solver's internal handling of large programs could enhance the benefits of body-decoupled grounding.

Summary updated

BibTeX
@inproceedings{besin2022body,
  author = {Viktor Besin and Markus Hecher and Stefan Woltran},
  title = {{Body-Decoupled Grounding via Solving: A Novel Approach on the ASP Bottleneck}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/353},
}
Figure