Exploiting Justifications for Lazy Grounding of Answer Set Programs

Bart Bogaerts, Antonius WeinzierlIJCAI 2018 · DOI

TL;DR

This paper introduces a novel technique for Answer Set Programming (ASP) that significantly speeds up solving by analyzing "justifications" for why certain program parts are evaluated. By understanding why a program state is reached, the system can intelligently backtrack and avoid redundant computations, leading to exponential speedups on specific problem classes.

What Problem Does This Paper Address?

Answer Set Programming (ASP) is a powerful knowledge representation and reasoning paradigm. A key bottleneck in ASP is "grounding," the process of translating a general logic program with variables into a ground program with specific instances. "Lazy grounding" techniques aim to mitigate this by interleaving grounding with the solving process. However, a common issue with lazy grounding, particularly in systems like ALPHA that use conflict-driven clause learning (CDCL), is that the solver can reach a state where an atom is true but "unjustified." This means there are no rules in the current grounding that derive this atom. When this happens, the system often falls back to chronological backtracking, which can be extremely inefficient, potentially wasting exponential time. This paper addresses this weakness by providing a mechanism to analyze these unjustified states and enable more intelligent, "backjumping" behavior.

Methods

The core contribution is the development of a justification-based analysis for lazy grounding ASP. The authors formalize the concept of justifications within the context of ASP and propose algorithms to construct these justifications without needing to fully ground the program.

Here's a breakdown of the key methods:

  • Justifications: The paper defines justifications as a way to explain why a literal is true (or false) in a given program state. For a positive literal, a justification is a rule that derives it. For a negative literal, it's a set of rules that could derive the underlying atom, but none of them are satisfied.
  • Top-Down Justification Analysis: Instead of relying on the full grounding, the authors propose a top-down approach. This analysis starts from an atom that is true but unjustified and recursively explores the reasons why it's not justified. This involves identifying missing rules and the literals in their bodies that are responsible for the lack of derivation.
  • Litsets: To avoid full grounding, the algorithms use "litsets," which are first-order representations of sets of ground literals. This allows for symbolic manipulation of justifications.
  • Learning Clauses and Backjumping: The analysis identifies a specific set of literals that, if made false, explain why the target atom is unjustified. This information is then used to learn a new clause. When this clause is violated, the system can perform a more targeted "backjump" to a relevant decision level, rather than a simple chronological backtrack.
  • ALPHA Algorithm Extension: The proposed techniques are integrated into the ALPHA lazy grounding ASP solver. The core ALPHA algorithm is described with a new "justification-conflict" step that triggers the analysis.

Datasets

The paper does not introduce new datasets. Instead, it uses several benchmark problem classes for evaluation:

  • Two-way-derivation: A synthetic problem designed to trigger justification-conflict by providing two ways to derive an atom.
  • Variable-projection: Another synthetic problem where a binary predicate is projected to a unary one, creating ambiguity.
  • Graph-5-coloring: A standard graph coloring problem, specifically using an encoding prone to justification-conflict.
  • Non-partition-removal-coloring: A more complex benchmark inspired by configuration problems, where grounding is a significant issue.

Key Insights and Ideas

  • Unjustifiedness as a Signal: The core insight is that an unjustified true atom is not just a failure, but a valuable signal. It indicates a problem with the current assignment and provides a direct path to understanding why a solution might not be reachable.
  • Justifications Without Grounding: The ability to construct meaningful justifications without fully grounding the program is crucial. This directly addresses the bottleneck that lazy grounding aims to solve, but in a more intelligent way.
  • Backjumping from Justifications: Learning clauses based on these justifications allows for significantly more effective backjumping. Instead of just undoing recent decisions, the system can jump back to the root cause of the unjustifiedness.
  • Exponential Speedups are Possible: The experiments demonstrate that for problems where justification-conflict is a significant issue, this new approach can lead to exponential improvements in solving time.

Key Results

The paper presents experimental results comparing their enhanced ALPHA system (ALPHA J) against the original ALPHA and the ground-and-solve solver CLINGO.

  • Two-way-derivation: ALPHA J achieved dramatic speedups, solving problems with domain sizes up to 1000 in seconds, while ALPHA timed out at domain size 30. CLINGO solved these trivially due to easy grounding.
  • Variable-projection: Similar to the above, ALPHA J significantly outperformed ALPHA, with ALPHA J's runtime growing much slower.
  • Graph-5-coloring: For the original competition setting (prone to justification-conflict), ALPHA J handled graphs with 100 vertices in seconds and even 1000 vertices within the time limit, whereas ALPHA struggled with larger graphs. When a constraint was added to prevent justification-conflict, ALPHA and ALPHA J performed comparably, indicating minimal overhead for the justification analysis itself.
  • Non-partition-removal-coloring: This benchmark, where grounding is a major issue, showed ALPHA J significantly reducing timeouts compared to ALPHA, solving instances that ALPHA could not. CLINGO struggled with memory on larger instances.

Limitations and Future Work

  • Overhead on Easy-to-Ground Problems: The authors acknowledge that for problems where grounding is not a bottleneck and CLINGO performs well, their approach might not offer significant advantages and could even introduce some overhead.
  • Propagation Power: Lazy grounding, by its nature, provides less information to the solver initially, potentially reducing propagation power compared to ground-and-solve systems. The justification analysis helps compensate for this, but it's an ongoing area of research.
  • Implementation Effort: The paper notes that CLINGO benefits from years of optimization, while ALPHA is a younger system. Further engineering effort on ALPHA could yield even better performance.
  • Future Work: The authors suggest exploring how justifications can be used in other contexts, such as goal-driven lazy grounding and relevance analysis. They also plan to investigate how their techniques can be applied to other lazy grounding ASP systems like Omiga and ASPeRiX.

Summary updated

BibTeX
@inproceedings{bogaerts2018exploiting,
  author = {Bart Bogaerts and Antonius Weinzierl},
  title = {{Exploiting Justifications for Lazy Grounding of Answer Set Programs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/240},
}
Figure