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.
Key features of the implementation include:
- Uniform Representation: A single interface for rules and loops simplifies the solver architecture.
- Watched Literals:
clasputilizes 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.
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