Conflict-Driven Answer Set Solving

Martin Gebser, Benjamin Kaufmann, André Neumann, Torsten SchaubIJCAI 2007

Abstract

This paper presents a uniform constraint-based framework for Answer Set Programming (ASP) that leverages advanced Boolean Satisfiability (SAT) techniques. By representing logic program rules and loop formulas as "nogoods," the authors introduce Conflict-Driven Nogood Learning (CDNL), an algorithm that integrates conflict-driven learning and backjumping into ASP solving. The resulting solver, clasp, demonstrates performance improvements of several orders of magnitude over previous state-of-the-art ASP solvers.

Introduction

Answer Set Programming (ASP) has emerged as a powerful paradigm for modeling complex combinatorial problems. However, a significant performance gap historically existed between ASP solvers and Boolean Satisfiability (SAT) solvers. While SAT solvers evolved rapidly through the adoption of "look-back" techniques—such as conflict-driven clause learning (CDCL) and non-chronological backtracking—ASP solvers primarily relied on "look-ahead" strategies.

The primary challenge in bridging this gap lies in the unique semantics of ASP, specifically the requirement for models to be "stable." This involves handling unfounded sets and cycles in rules (loops), which are not present in standard SAT problems. Previous attempts to utilize SAT power either involved full translation to SAT (potentially losing program structure) or implementation-specific modifications lacking a unified theoretical foundation.

Methods: The Nogood Framework

The authors propose a computational approach centered on the concept of a nogood. In the context of Constraint Satisfaction Problems (CSP), a nogood is a set of variable assignments known to be impossible. This research demonstrates that inferences from logic program rules, Clark’s completion, and complex loop formulas can all be expressed uniformly as nogoods.

The CDNL-ASP Algorithm

At the heart of the clasp solver is the Conflict-Driven Nogood Learning (CDNL) algorithm. This algorithm mirrors the CDCL approach in SAT but is tailored for ASP semantics. When the solver encounters a conflict (a dead end in the search space), it performs a conflict analysis to determine the "reason" for the failure. This reason is recorded as a new nogood, which prunes the search space and allows the solver to "backjump" to an earlier decision level.

The CDNL-ASP algorithm, illustrating the integration of nogood propagation, conflict analysis, and decision making.

Key features of the implementation include:

  • Uniform Representation: A single interface for rules and loops simplifies the solver architecture.
  • Watched Literals: clasp utilizes efficient SAT-style data structures for fast unit propagation.
  • Integrated Unfounded Set Detection: The solver interleaves standard propagation with dedicated algorithms to identify unfounded sets, ensuring that the final models satisfy ASP's stability requirements.

Experimental Evaluation

The authors evaluated clasp against contemporary solvers, including assat, cmodels, smodels, and smodels_cc. The benchmark suite covered a diverse range of domains:

  • Hardware Verification: Bounded Model Checking instances.
  • Cryptanalysis: Breaking simplified Data Encryption Standard (DES) versions.
  • Planning and Graph Problems: Blocksworld and Hamiltonian cycles in "clumpy" graphs.
  • Puzzles and Optimization: Sokoban, "Gryzzles," and machine code superoptimization.

Key Results and Insights

The empirical results highlight the effectiveness of the native conflict-driven approach. On hard, non-tight programs—where loop formulas are critical—clasp outperformed traditional solvers like smodels by multiple orders of magnitude. Furthermore, on "tight" programs (where ASP and SAT semantics coincide), clasp remained competitive with or superior to solvers that translate ASP directly into SAT.

Comparative performance of clasp against state-of-the-art solvers on benchmarks 1-30.

A critical insight from the study is the efficiency of favoring local propagation (rules) over expensive global checks (unfounded sets). clasp only triggers complex loop-checking logic when local propagation is exhausted. Additionally, by learning new nogoods from loop violations, the solver effectively prunes similar parts of the search space in future iterations.

Conclusion and Future Work

This work successfully brings the power of modern SAT solving to the ASP domain through a unified nogood-based framework. The clasp solver demonstrates that a native ASP approach incorporating conflict-driven learning is both viable and highly efficient. Future research directions include extending the framework to disjunctive logic programs, exploring ASP-specific heuristics, and improving undirected inference for unfounded sets.

Summary updated

BibTeX
@inproceedings{gebser2007conflict,
  author = {Martin Gebser and Benjamin Kaufmann and André Neumann and Torsten Schaub},
  title = {{Conflict-Driven Answer Set Solving}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
}
Figure