Advanced Conflict-Driven Disjunctive Answer Set Solving
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 912-917.
© 2013 International Joint Conferences on Artificial Intelligence
Abstract
We introduce a new approach to disjunctive ASP solving that aims at an equitable interplay between generating and testing solver units. To this end, we develop novel characterizations of answer sets and unfounded sets allowing for a bidirectional dynamic information exchange between solver units for orthogonal tasks. This results in the new multi-threaded disjunctive ASP solver claspD-2, greatly improving the performance of existing systems.
- [Alviano et al., 2011] M. Alviano, F. Calimeri, W. Faber, N. Leone, and S. Perri. Unfounded sets and well-founded semantics of answer set programs with aggregates. Jour- nal of Artificial Intelligence Research, 42:487-527, 2011.
- [Baral, 2003] C. Baral. Knowledge Representation, Reason- ing and Declarative Problem Solving. Cambridge, 2003.
- [Ben-Eliyahu and Dechter, 1994] R. Ben-Eliyahu and R. Dechter. Propositional semantics for disjunctive logic programs. Annals of Mathematics and Artificial Intelligence, 12(1-2):53-87, 1994.
- [Calimeri et al., 2013] F. Calimeri, G. Ianni, and F. Ricca. The third open answer set programming competition. The- ory and Practice of Logic Programming, 2013. To appear.
- [Drescher et al., 2008] C. Drescher, M. Gebser, T. Grote, B. Kaufmann, A. König, M. Ostrowski, and T. Schaub. Conflict-driven disjunctive answer set solving. In Proc. In- ternational Conference on Principles of Knowledge Repre- sentation and Reasoning (KR'08), pages 422-432. AAAI Press, 2008.
- [Eén and Sörensson, 2003] N. Eén and N. Sörensson. Tem- poral induction by incremental SAT solving. Electronic Notes in Theoretical Computer Science, 89(4), 2003.
- [Eiter and Gottlob, 1995] T. Eiter and G. Gottlob. On the computational cost of disjunctive logic programming: Propositional case. Annals of Mathematics and Artificial Intelligence, 15(3-4):289-323, 1995.
- [Gebser et al., 2008] M. Gebser, R. Kaminski, B. Kaufmann, M. Ostrowski, T. Schaub, and S. Thiele. Engineering an incremental ASP solver. In Proc. International Confer- ence on Logic Programming (ICLP'08), pages 190-205. Springer, 2008.
- [Gebser et al., 2010] M. Gebser, C. Guziolowski, M. Ivanchev, T. Schaub, A. Siegel, S. Thiele, and P. Veber. Repair and prediction (under inconsistency) in large biological networks with answer set program- ming. In Proc. International Conference on Principles of Knowledge Representation and Reasoning (KR'10), pages 497-507. AAAI Press, 2010.
- [Gebser et al., 2011a] M. Gebser, R. Kaminski, and T. Schaub. Complex optimization in answer set pro- gramming. Theory and Practice of Logic Programming, 11(4-5):821-839, 2011.
- [Gebser et al., 2011b] M. Gebser, T. Schaub, S. Thiele, and P. Veber. Detecting inconsistencies in large biological net- works with answer set programming. Theory and Practice of Logic Programming, 11(2-3):323-360, 2011.
- [Gebser et al., 2012a] M. Gebser, B. Kaufmann, and T. Schaub. Conflict-driven answer set solving: From theory to practice. AI Journal, 187-188:52-89, 2012.
- [Gebser et al., 2012b] M. Gebser, B. Kaufmann, and T. Schaub. Multi-threaded ASP solving with clasp. Theory and Practice of Logic Programming, 12(4-5):525- 545, 2012.
- [Janhunen et al., 2006] T. Janhunen, I. Niemelä, D. Seipel, P. Simons, and J. You. Unfolding partiality and disjunc- tions in stable model semantics. ACM Transactions on Computational Logic, 7(1):1-37, 2006.
- [Janota and Marques-Silva, 2011] M. Janota and J. Marques-Silva. On deciding MUS membership with QBF. In Proc. International Conference on Princi- ples and Practice of Constraint Programming (CP'11), pages 414-428. Springer, 2011.
- [Koch et al., 2003] C. Koch, N. Leone, and G. Pfeifer. En- hancing disjunctive logic programming systems by SAT checkers. AI Journal, 151(1-2):177-212, 2003.
- [Lee and Lifschitz, 2003] J. Lee and V. Lifschitz. Loop for- mulas for disjunctive logic programs. In Proc. Inter- national Conference on Logic Programming (ICLP'03), pages 451-465. Springer, 2003.
- [Leone et al., 1997] N. Leone, P. Rullo, and F. Scarcello. Disjunctive stable models: Unfounded sets, fixpoint se- mantics, and computation. Information and Computation, 135(2):69-112, 1997.
- [Leone et al., 2006] N. Leone, G. Pfeifer, W. Faber, T. Eiter, G. Gottlob, S. Perri, and F. Scarcello. The DLV system for knowledge representation and reasoning. ACM Transac- tions on Computational Logic, 7(3):499-562, 2006.
- [Lierler, 2005] Y. Lierler. Cmodels: SAT-based disjunctive answer set solver. In Proc. International Conference on Logic Programming and Nonmonotonic Reasoning (LP- NMR'05), pages 447-451. Springer, 2005.
- [Maratea et al., 2010] M. Maratea, F. Ricca, and P. Veltri. DLV MC : Enhanced model checking in DLV. In Proc. European Conference on Logics in Artificial Intelligence (JELIA'10), pages 365-368. Springer, 2010.
- [Marques-Silva and Sakallah, 1999] J. Marques-Silva and K. Sakallah. GRASP: A search algorithm for proposi- tional satisfiability. IEEE Transactions on Computers, 48(5):506-521, 1999.
- [Perri et al., 2010] S. Perri, F. Ricca, and M. Sirianni. A parallel ASP instantiator based on DLV. In Proc. Work- shop on Declarative Aspects of Multicore Programming (DAMP'10), pages 73-82. ACM Press, 2010.
- [Peschiera et al., 2010] C. Peschiera, L. Pulina, A. Tac- chella, U. Bubeck, O. Kullmann, and I. Lynce. The seventh QBF solvers evaluation (QBFEVAL'10). In Proc. Interna- tional Conference on Theory and Applications of Satisfia- bility Testing (SAT'10), pages 237-250. Springer, 2010.
- [Pfeifer, 2004] G. Pfeifer. Improving the model genera- tion/checking interplay to enhance the evaluation of dis- junctive programs. In Proc. International Conference on Logic Programming and Nonmonotonic Reasoning (LP- NMR'04), pages 220-233. Springer, 2004.
- Syrjänen, ] T. Syrjänen. Lparse 1.0 user's manual.
- [Tu et al., 2011] P. Tu, T. Son, M. Gelfond, and A. Morales. Approximation of action theories and its application to conformant planning. AI Journal, 175(1):79-119, 2011.
- [Zhang et al., 2001] L. Zhang, C. Madigan, M. Moskewicz, and S. Malik. Efficient conflict driven learning in a Boolean satisfiability solver. In Proc. International Con- ference on Computer-Aided Design (ICCAD'01), pages 279-285. ACM Press, 2001.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Answer Set Programming (ASP; [Baral, 2003]) has become a popular tool for declarative problem solving. Its growing range of applications has also increased the demand for the elevated complexity of disjunctive logic programs (expressing ΣP2 -hard problems). Although recent advances facilitate modeling such problems [Gebser et al., 2011a], existing disjunctive ASP solvers [Leone et al., 2006; Janhunen et al., 2006; Lierler, 2005; Drescher et al., 2008] still lack some features of non-disjunctive solvers. Also, the indispensable coupling of a solver unit generating answer set candidates with one checking their minimality was so far insufficiently exploited: while the "generator" is run continuously, a "tester" is repeatedly re-invoked bearing significant redundancy.
We address these shortcomings by introducing a new approach to disjunctive ASP solving that aims at an equitable interplay between generator(s) and tester(s). The idea is to launch both types of solver units only once with their respective Boolean constraint problems and to let them subsequently communicate in a bidirectional way. This enables both generators and testers to benefit from conflictdriven learning over whole runs. We begin by developing novel characterizations of answer sets and unfounded sets in terms of Boolean constraints solvable with state-of-theart NP search procedures. Unlike existing encodings [Koch et al., 2003; Drescher et al., 2008], our specification of unfounded sets is comprehensive in applying to arbitrary (total or partial) answer set candidates. We further present a solver architecture featuring multi-threading and incremental solving techniques, along with its implementation in the new disjunctive ASP solver claspD-2, seamlessly passing dynamic information between orthogonal solver units.
∗Affiliated with SFU, Canada, and Griffith University, Australia. This work was partially funded by DFG grant SCHA 550/8-3. We also thank Sebastian B¨ohne, Mikol´aˇs Janota, and Roland Kaminski.
2 Background
A (ground disjunctive) rule r is of the form
p1 ∨ · · · ∨ pl ← pl+1, . . . , pm, ∼pm+1, . . . , ∼pn where p1, . . . , pl, pl+1, . . . , pm, pm+1, . . . , pn are propositional atoms for 0≤l≤m≤n. By hd(r) = {p1, . . . , pl} and bd(r) = {pl+1, . . . , pm,∼pm+1, . . . ,∼pn}, we denote the head and the body of r, where ∼ stands for default negation. For any set L = {pl+1, . . . , pm,∼pm+1, . . . ,∼pn}, let L+ = {pl+1, . . . , pm} and L= {pm+1, . . . , pn}. We say that r is applicable wrt. a set X of atoms if bd(r)+ ⊆ X and bd (r)- ∩ X = ∅; r is satisfied wrt. X if hd(r) ∩ X ̸= ∅ when r is applicable wrt. X. Any p ∈ hd(r) is supported by r wrt. X if r is applicable wrt. X and hd(r) ∩ X ⊆ {p}. A (ground disjunctive) program P is a set of rules. We denote atoms and bodies occurring in P by atP = ⋃r∈P (hd(r)∪bd(r)+∪bd(r)-) and bdP = {bd(r) | r ∈ P}. A set X of atoms is a model of P if every r ∈ P is satisfied wrt. X; X is supported by P if every p ∈ X is supported by some r ∈ P wrt. X. We write appP (X) to refer to the subset of P including all applicable rules wrt. X. The reduct of P wrt. X is P X = {hd(r) ← bd(r)+ | bd(r)- ∩X = ∅}. A model X of P is an answer set of P if there is no Y ⊂ X such that Y is a model of P X .
The (directed) positive atom dependency graph of P is GP = (atP , {(p, q) | r ∈ P, p ∈ hd(r), q ∈ bd(r)+}). A non-empty L ⊆ atP is a loop of P if its induced subgraph of GP is strongly connected. We denote the set of all loops of P by loopP . As the ⊆-maximal elements of loopP partition atP and induce strongly connected components (SCCs) of GP , we write sccP to refer to the set of such loops. We call L ∈ sccP a head cycle component (HCC) of P if |hd(r) ∩ L| > 1 for some r ∈ P. By scc hc P , we denote the subset of sccP including all HCCs of P; P is head-cycle-free (HCF; [Ben-Eliyahu and Dechter, 1994]) if scc hc P = ∅, and non-HCF otherwise.
As an example, consider the following program:
P1 yields loopP1 = {{a}, {b}, {c}, {d}, {e}, {a, b}, {b, c}, {b, d}, {a, b, c}, {a, b, d}, {b, c, d}, {a, b, c, d}} and sccP1 = {{a, b, c, d}, {e}}. In view of rules r1 and r5, we have that scc hc P1 = {{a, b, c, d}}, so that P1 is non-HCF. One can check that {a, b, d}, {c}, and {e} are the three answer sets of P1.
3 Boolean Constraints
Deciding whether a (ground disjunctive) program has an answer set is ΣP2 -complete [Eiter and Gottlob, 1995]. In fact, generating candidate models X of a program P and checking ⊆-minimality wrt. P X can both be viewed as Boolean constraint solving tasks, which can be specified as follows.
A nogood {σ1, . . . , σn} is a set of literals σi of the form Tυi or Fυi for 1≤i≤n, where υi is a (propositional) variable. We refer to the complement of a literal by Tυ = Fυ and Fυ = Tυ. For any set δ of literals, let δT = {υ | Tυ ∈ δ} and δF = {υ | Fυ ∈ δ}. Given a set Δ of nogoods, we denote the variables occurring in Δ by var(Δ) = ⋃δ∈Δ(δT ∪ δF ). Any subset A of {Tυ, Fυ | υ ∈ var(Δ)} such that AT ∩AF = ∅ is an assignment for Δ; A is a solution for Δ if AT ∪ AF = var (Δ) and δ ̸⊆ A for any δ ∈ Δ.
Answer Sets. In order to compute answer sets by means of Boolean constraint solving procedures, we specify nogoods whose solutions match answer sets. In fact, the nogoods capture particular properties of answer sets, viz. satisfaction of rules, support of atoms, and minimality wrt. the reduct.
For expressing that some atom in hd(r) must be true when a rule r is applicable, we map bd(r) to literals making it true:
Eg., for r2 from P1, bd(r2) = {b,∼d} yields β(r2) = {T b, Fd}. We use such sets of literals to refer to (composite) variables with an intrinsic meaning (cf. Definition 3) in the following nogoods stipulating rules to be satisfied.
Definition 1. Let P be a program. We define the rule nogood for any r ∈ P by
For instance, the nogoods for rules in P1 are as follows:
Given that any answer set X of a program P is supported by P, for every p ∈ X, there must be some applicable rule r ∈ P such that no q ∈ hd(r)\{p} belongs to X. Support can be captured by atom-wise shifting [Ben-Eliyahu and Dechter, 1994], mapping a rule r to ⃗r(p) and identifying bd(⃗r(p)) with an extended set β(r, p) of literals:
For instance, atom-wise shifting of r5 = c ∨ d ← b yields ⃗r5(c) = c ← b,∼d and ⃗r5(d) = d ← b,∼c. Respective extensions of bd(r5) = {b} are reflected by the literals in β(r5, c) = {T{Tb},Fd} and β(r5, d) = {T{Tb},Fc}. Note that the original body representation, as included in a rule nogood, is reused, rather than repeatedly unfolding the body for each head atom. On the other hand, atom-wise shifting may reproduce the body of another program rule; eg., we have that bd(⃗r5(c)) = {b, ∼d} = bd(r2).
In view of the previous observation, we introduce the following concept to switch between the reuse of an existing rule body or the introduction of a new set of literals for representing a body stemming from atom-wise shifting:
Since bd(⃗r5(c)) = {b,∼d} = bd(r2), while bd(⃗r5(d)) = {b,∼c} /∈ bdP1 , the representations βP1 (r5, c) = {Tb,Fd} and βP1 (r5, d) = {T{Tb},Fc} are selected for bodies obtained through atom-wise shifting of r5. In general, βP (r, p) picks the original body representation β(r) if hd(r) = {p}, so that rules without proper disjunctive head do not lead to new variables for bodies in the support nogoods given next.
Definition 2. Let P be a program. We define the support nogood for any p ∈ atP by
The support nogoods of P are ΨP = {ψP (p) | p ∈ atP }.
A nogood of the form ψP (p) expresses that p must not be true if it is not supported by any rule in P, as indicated by FβP (r, p) for all rules with p in the head. For instance, we obtain the following support nogoods for the atoms of P1:
Rule and support nogoods define the atoms of a program in terms of rule bodies, possibly obtained through atom-wise shifting. Bodies in turn represent the conjunction of their contained literals, which is captured by defining the corresponding variables by means of the following nogoods.
Definition 3. Let P be a program and β a set of literals. We define the conjunction nogoods for β by
The conjunction nogoods of P are
Observe that ΓP includes defining nogoods for literal sets β(r) representing elements of bdP in ΦP as well as for extensions β(r, p), selected via βP (r, p), that occur in ΨP . Eg., β(r1) = ∅, β(r2) = {Tb,Fd}, and βP1 (r1, a) = {T ∅, F c, F e} are defined via the following subsets of ΓP1 :
In particular, {F∅} requires T∅, which occurs in a nogood defining {T ∅, F c, F e}, to belong to any solution for ΓP1 .
Although the combined set ΦP ∪ΨP ∪ ΓP of nogoods suffices to characterize models of P that are supported by P, we rely on component-wise shifting [Drescher et al., 2008] as an a priori simplification, particularly for (complex) minimality checking detailed below. To this end, we refer to the SCCs of head atoms in a rule r by sccP (r) = {L ∈ sccP | hd(r) ∩ L ̸= ∅}. Component-wise shifting then decomposes rules (with proper disjunctive heads) on the basis of SCCs.
Definition 4. Let P be a program. We define the componentshifted version of P by
For P1, component-wise shifting yields the following:
Note that the heads of rules in ⃗ P1 are confined to SCCs, viz. hd(r) ⊆ {a, b, c, d} or hd(r) ⊆ {e} holds for all r ∈ ⃗ P1. In general, a program P is non-HCF iff its component-shifted version ⃗ P includes some rule with proper disjunctive head.
Unlike atom-wise shifting, component-wise shifting preserves the (classical) semantics of loop formulas [Lee and Lifschitz, 2003]. Hence, a program P and its componentshifted version ⃗ P are equivalent.
Proposition 1. Let P be a program and X a set of atoms. We have that X is an answer set of P iff X is an answer set of ⃗ P .
The previous result tells us that nogoods aiming at answer sets of P may safely concentrate on ⃗ P. In fact, we define the nogoods capturing completion [Lee and Lifschitz, 2003] relative to the component-shifted version ⃗ P of P.
Definition 5. Let P be a program. We define the completion nogoods of P by ΔP = Φ⃗ P ∪Ψ⃗ P ∪ Γ⃗ P .
For instance, the rule nogood {F a, F c, F e, T ∅} from ΦP1 turns into φ(r0) = {Fe, T{Fa,Fc}} and φ(r1) = {Fa, Fc, T{Fe}} in Φ⃗ P1 and ΔP1 . Observe that φ(r0) and φ(r1) (in view of the conjunction nogood {F∅} from ΓP1 ) exclude the same combination of literals over a, c, and e as {Fa,Fc,Fe, T∅}, yet relying on different variables (sets of literals) standing for rule bodies. As we describe below, the bodies obtained through component-wise shifting can be readily reused in the context of (complex) minimality checking for signaling the (non-)applicability of rules.
In order to establish correspondences between models of a program and solutions for nogoods, we map any set of atoms to an induced assignment as follows.
Definition 6. Let P be a program and X a set of atoms. We define the induced assignment of X for P by
Beyond literals over atoms, an induced assignment AXP includes either Tβ(r) or Fβ(r) for each r ∈ ⃗ P along with either Tβ(r, p) or Fβ(r, p) for any extension β(r, p) obtained through atom-wise shifting and selected via β⃗ P (r, p). For instance, the induced assignment A{a,b,d} P1 contains T a, T b, F c, T d, F e, T β(r5) = T {T b}, T β⃗ P1 (r5, d) = T {T {T b}, F c}, and further literals over rule bodies.
As stated next, variables standing for rule bodies are defined via conjunction nogoods in Γ⃗ P and do thus not introduce additional combinatorics regarding solutions for ΔP .
Proposition 2. Let P be a program and X a set of atoms. We have that AatP∩X P is the unique solution for
In view of the above result, the following yields a one-toone correspondence between models of P that are supported by P and solutions for the completion nogoods ΔP .
Theorem 1. Let P be a program and X a set of atoms. We have that X is a model of P that is supported by P iff AXP is a solution for ΔP .
For instance, {a, b, c} is a model of P1 that is supported by P1, and the support nogoods ψ⃗ P1 (a), ψ⃗ P1 (b), and ψ⃗ P1 (c) are not contained in the induced assignment A{a,b,c} P1 , which includes Tβ⃗ P1 (r2, a) = Tβ⃗ P1 (r5, c) = T{Tb,Fd} and T β⃗ P1 (r3, b) = T{Ta, Fe}. However, {a, b, c} is not an answer set of P1 because {c} is a model of P {a,b,c} 1 .
In order to make sure that solutions match answer sets, we still need to guarantee that true atoms are non-circularly supported. To this end, we denote the external supports of a set L of atoms for a program P by εP (L) = {r ∈ P | hd(r) ∩ L ̸= ∅, bd(r)+ ∩ L = ∅}. Moreover, ρ(r, L) = {Fβ(r)}∪{Tp | p ∈ hd(r)\L} collects all literals satisfying a rule r regardless of whether any atom from L is true. Eg., ε⃗ P1 ({a, b}) consists of r1 = a ∨ c ← ∼e and r4 = b ← c, d, whose associated literal sets are ρ(r1, {a, b}) = {F{Fe}, T c} and ρ(r4, {a, b}) = {F {T c, T d}}.
We say that a set L of atoms is unfounded [Leone et al., 1997] for a program P wrt. an assignment A if ρ(r, L)∩A ̸= ∅ holds for any r ∈ εP (L). For instance, {a, b} is unfounded for ⃗ P1 wrt. A{a,b,c} P1 , which includes Tc ∈ ρ(r1, {a, b}) and F{Tc, Td} ∈ ρ(r4, {a, b}). Unfounded sets are addressed by loop nogoods as follows.
Definition 7. Let P be a program. We define the loop nogoods for any L ⊆ atP by
The loop nogoods of P are ΛP = ⋃L⊆atP λ⃗ P (L).
Loop nogoods in λP (L) express that every atom from L must be false if all external supports of L for P are satisfied independently of L, as indicated by some literal from ρ(r, L) for each r ∈ εP (L). Also note that ΛP collects loop nogoods constructed from ⃗ P to align literals over bodies of external supports with variables defined via the conjunction nogoods Γ⃗ P . Eg., ΛP1 includes λ⃗ P1 ({a, b}) = {{Tp, F{Fe}, F{Tc, Td}}, {Tp, Tc,F{Tc, Td}} | p ∈ {a, b}}, among which {T a, T c, F {T c, T d}} and {T b, T c, F {T c, T d}} are contained in A{a,b,c} P1 .
Augmenting completion with loop nogoods yields a oneto-one correspondence between solutions and answer sets.
Theorem 2. Let P be a program and X a set of atoms. We have that X is an answer set of P iff AXP is a solution for ΔP ∪ ΛP .
The above result characterizes answer sets in terms of (induced) assignments encapsulating "unfounded-free" models in the sense of Leone et al. (1997), who show that unfounded set checks can be localized to SCCs of GP . Local checks are tractable for elements of sccP \scc hc P , but not for the HCCs in scc hc P , so that evaluating loop nogoods for the (exponentially many) subsets of HCCs is computationally complex.
Unfounded Sets. Given the complexity of identifying unfounded sets contained in HCCs, we specify nogoods having such unfounded sets as solutions. The nogoods require some true atom not belonging to the unfounded set to be present in the head of any external support whose body is not false. We thus refer to atoms that occur together with members of a set L of atoms in a proper disjunctive head for a program P by Lhc P = {p ∈ hd(r) | r ∈ P, |hd(r) ∩ L| > 1}. Given this, unfounded set nogoods for atoms L of SCCs are as follows.
Definition 8. Let P be a program. We define the unfounded set nogoods for any L ∈ sccP by
The basic idea of ΩP (L) is to represent the atoms p in an unfounded subset L′ of L by literals of the form Tup in a solution. Additional variables are used to encode unfoundedness wrt. an underlying assignment A for ΔP . That is, for any r ∈ ⃗ P such that hd(r) ∩L ̸= ∅, the literal Tfβ(r) signals that β(r) ∈ AF , so that r is inapplicable. For atoms p ∈ L occurring in a proper disjunction in ⃗ P, Thp expresses that p ∈ AT \ L′ , where p ∈ AT is reflected by the literal Ttp, while Fup indicates that p /∈ L′ . Then, for any r ∈ ⃗ P such that hd(r) ∩ L′ ̸= ∅, the unfoundedness of L′ is witnessed by inapplicability of r, some true atom q ∈ hd(r) \ L′ , or an atom p ∈ bd(r)+ ∩ L′ , as represented by literals of the form T fβ(r), Thq, or Tup, respectively. Finally, L′ must not be the (trivial) empty unfounded set.
For instance, we obtain the following unfounded set nogoods for the HCC L1 = {a, b, c, d} of P1:
Eg., r5 = c ∨ d ← b yields the nogoods {T uc, F hd, F f{T b}, F ub} and {T ud, F hc, F f{T b}, F ub} to prohibit assignments representing a subset L′ of L such that {c, d} ∩ L′ ̸= ∅ and b /∈ L′ , while {c, d} ∩AT ⊆ L′ and {Tb} /∈ AF hold wrt. an underlying assignment A for ΔP1 .
The nogoods in ΩP (L) encode (non-empty) unfounded subsets of L wrt. arbitrary assignments for ΔP . Upon computing answer sets, however, one is interested in unfounded sets wrt. an assignment A at hand. Hence, we extract nogoods from A that restrict solutions for ΩP (L) accordingly.
Definition 9. Let P be a program and A an assignment for ΔP . We define the assignment nogoods for any L ∈ sccP by
As every nogood in ΘA P (L) is of the form {σ}, it immediately implies the complement σ of its literal σ. In particular, variables fβ(r) and tp, expressing whether bodies β(r) are false or atoms p ∈ Lhc ⃗ P are true wrt. A, are partitioned via A into (necessarily) true and false literals. That is, the variables representing an assignment A in ΩP (L) are fixed through the assignment nogoods ΘA P (L). Moreover, false members of L are excluded from unfounded sets obtainable as solutions.
For example, consider an assignment for ΔP1 as follows:
In view of β(r4) = {Tc, Td} ∈ AF1 , c ∈ Lhc 1⃗ P1 ∩ AT1 , and d ∈ L ∩ AF1 , we obtain the following assignment nogoods:
That is, unfounded sets admitted as solutions for ΩP1 (L1) ∪ ΘA1 P1 (L1) must neither include d (or Tud, respectively) nor rely on literals of the form Thp or T fβ(r) for p ̸= c or r ̸= r4. In fact, ΩP1 (L1) ∪ ΘA1 P1 (L1) has a single solution as follows:

This solution yields the unfounded set {a, b} for ⃗ P1 wrt. A1, where the members of ε⃗ P1 ({a, b}) = {r1, r4} are satisfied independently of a and b in view of T c ∈ ρ(r1, {a, b}) ∩ A1 and F {T c, T d} ∈ ρ(r4, {a, b}) ∩ A1.
In general, we have the following one-to-one correspondence between (particular) unfounded sets and solutions.
Proposition 3. Let P be a program, A an assignment for ΔP , L ∈ sccP , and ∅ ⊂ L′ ⊆ L \ AF . We have that L′ is unfounded for ⃗ P wrt. A iff
is the unique solution for ΩP (L)∪ΘA P (L) such that {p ∈ L | up ∈ BT } = L′ .
The confinement to non-empty unfounded subsets L′ of L\ AF for some L ∈ sccP is sufficient for minimality checking because circular positive dependencies cannot spread across multiple SCCs of GP . Moreover, for any rule r ∈ ⃗ P such that bd(r)+ ∩AF ̸= ∅, the conjunction nogoods Γ⃗ P requireFβ(r) to belong to any solution for ΔP , so that false atoms can be subtracted from unfounded sets. In view of Theorem 2, the correctness of minimality checking via unfounded sets within SCCs can be stated as follows.
Theorem 3. Let P be a program and A a solution for ΔP . We have that A is a solution for ΛP iff ΩP (L) ∪ ΘA P (L) is unsatisfiable for any L ∈ sccP .
As noted above, unfounded set checks are tractable for SCCs whose atoms do not occur jointly in any proper disjunction (trivially including singletons like {e} ∈ sccP1 ). Hence, solving ΩP (L) ∪ ΘA P (L) to compute unfounded sets is appropriate for HCCs only. In the course of this, however, component-wise shifting reduces the amount of assignment specifics passed through ΘA P (L), since only atoms from L are considered in addition to variables for rule bodies.
4 The claspD-2 System
Our approaches to model generation and minimality checking are implemented in the new conflict-driven disjunctive ASP
solver claspD-2. Its generating and testing solver units rely on Conflict-Driven Constraint Learning (CDCL; [MarquesSilva and Sakallah, 1999; Zhang et al., 2001]), as originally devised for SAT. CDCL incorporates deterministic (unit) propagation, heuristic decisions, conflict resolution to derive and record a new nogood from any assignment containing some nogood, and backjumping to recover after a conflict.
The generator(s) in claspD-2 combine propagation via completion nogoods with unfounded set checks. The latter concentrate on (non-trivial) SCCs, and complex checks by solving ΩP (L) ∪ ΘA P (L) are limited to HCCs L ∈ scc hc P . 1 For scheduling such checks, claspD-2 distinguishes whether an assignment A is total, viz. AT ∪ AF = var(ΔP ), or not. Before some total A is accepted, the unsatisfiability of ΩP (L) ∪ ΘA P (L) needs to be verified for all L ∈ scc hc P , and thus a total check investigating each HCC is performed. Unlike this, partial checks are not mandatory for soundness and can be customized in claspD-2. The ad hoc strategy applied by default relies on two thresholds: low is initialized with 0 and updated to the (greater) level of a decision where partial checking yields unsatisfiability of ΩP (L) ∪ ΘA P (L) for all L ∈ scc hc P ; high is initially ∞ and then updated to the level of a decision where a solution B for ΩP (L) ∪ ΘA P (L) such that λ ⊆ A for some λ ∈ λ⃗ P ({p ∈ L | up ∈ BT }) exhibits a conflict. Given this, a partial check is scheduled for decision level ⌈ high-low 2 ⌉, assuming that roughly half the number of variables unassigned by backjumping from a previous conflict due to an unfounded set will be reassigned.
Figure 1 displays the system architecture of claspD-2. Preprocessing a (ground disjunctive) input program P includes the calculation of SCCs along with the component-shifted version ⃗ P of P. This provides the basis for internal data representations of ΔP and ΩP (L1), . . . ,ΩP (Lk) for scc hc P = {L1, . . . , Lk}. Such data representations are further handled by dedicated solver objects, one generating candidate models and k testers performing unfounded set checks for individual HCCs. Building on the multi-threaded design of the clasp 2 series [Gebser et al., 2012b], the assembly of a generator along with testers may be reproduced to obtain n (currently up to n = 64) threads running in parallel. The n generating and k×n testing solvers can be separately configured, eg., to specify portfolios of search strategies for model generation and/or minimality checking. Notably, different generators as well as the n testers working on the same HCC share common data, rather than copying it n times.
In addition to multi-threading support, the interplay between generator(s) and tester(s) has been a prime target of enhancements in claspD-2. To this end, the unfounded set nogoods ΩP (L) are formulated in such a way that they remain invariant under dynamic assignment information passed through ΘA P (L). Since all nogoods in ΘA P (L) are singletons fixing truth values for some variables, their effect can be implemented via assumptions [E´en and S¨orensson, 2003]. In fact, claspD-2 utilizes the interface of clasp [Gebser et al.,
1 The (linear-time) unfounded set detection algorithm of clasp (cf. [Gebser et al., 2012a]) allows for identifying sets L′ such that β(r) ∈ AF applies to all external supports r ∈ ε⃗ P (L′ ). This is sufficient to detect any unfounded subset of a non-disjunctive SCC.
| Benchmark | # | basic | partial | pfolio[4] | pfolio[8] | claspD-1 | cmodels | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ConformantPlanning | 23 | 49 | (1) | 50 | (1) | 21 | (0) | 15 | (0) | 92 | (0) | 395 | (10) |
| MaximalSatisfiableSet | 86 | 51 | (3) | 46 | (2) | 23 | (0) | 5 | (0) | 230 | (12) | 619 | (57) |
| MinimalDiagnosis | 58 | 28 | (1) | 4 | (0) | 4 | (0) | 4 | (0) | 11 | (0) | 900 | (58) |
| 2QBF | 53 | 276 | (14) | 278 | (15) | 190 | (7) | 148 | (4) | 568 | (32) | 577 | (32) |
| Repair | 60 | 79 | (4) | 44 | (2) | 11 | (0) | 8 | (0) | 354 | (20) | 900 | (60) |
| StrategicCompanies | 32 | 489 | (6) | 473 | (6) | 528 | (10) | 521 | (8) | 773 | (23) | 862 | (30) |
| Average Time (Timeouts) | 312 | 162 | (29) | 149 | (26) | 129 | (17) | 117 | (12) | 338 | (87) | 709 | (247) |
2008] for solving under assumptions to handle unfounded set checks via queries to testers in charge. Importantly, the same tester processes all queries from a generator (likewise at total and partial checks) for some HCC, so that conflict nogoods recorded when solving a query can persist and constrain future queries. In turn, an unfounded set L′ from a tester always yields some loop nogood λ ∈ λ⃗ P (L′ ) such that λ ⊆ A for the querying generator's assignment A (thus indicating a conflict) or that λ can be propagated wrt. A. In either case, λ is recorded on the generator side, which may make analogous queries (from any generator) obsolete in the sequel.
5 Experiments
We compare two single- and two multi-threaded configurations of claspD-2 (R6582 2 ) with its predecessor claspD-1 (1.1.4) and cmodels (3.8.2). All these systems accept (ground disjunctive) input programs in lparse format [Syrj¨anen] and utilize CDCL technology for model generation and minimality checking. The experiments were run on a Linux machine with two Quad-Core Xeon E5520 2.27GHz processors, limiting each run to 900 seconds wall-clock time.
Table 1 shows average runtimes in seconds on 312 instances 2 from six classes: ConformantPlanning [Tu et al., 2011], MaximalSatisfiableSet [Janota and Marques-Silva, 2011], MinimalDiagnosis [Gebser et al., 2011b], 2QBF [Peschiera et al., 2010], Repair [Gebser et al., 2010], and StrategicCompanies [Calimeri et al., 2013]. Each instance was solved within the time limit by at least one system, while timeouts, given in parentheses, account for 900 seconds. The last row displays average runtimes over all six classes (weighted equally) along with sums of timeouts.
The difference between the single-threaded claspD-2 configurations "basic" and "partial" is that only the latter performs partial checks for HCCs. We observe some yet moderate performance gains due to partial checks according to our ad hoc strategy sketched above. Parallel portfolios, varying the search strategies of generators along with their testers, with n = 4 or n = 8 threads in "pfolio[n]" turn out to be quite effective (except for StrategicCompanies, where nogood exchange distracts search), especially on 2QBF. However, these benchmark results can give a first impression only, as neither the scheduling of partial checks nor multi-threaded operation modes of claspD-2 are fine-tuned at present.
Although claspD-2 still lacks fine-tuning, the comparison with claspD-1 and cmodels clearly shows advantages of our new system. For one, they are owed to using state-of-theart solver units from the clasp 2 series for model generation and minimality checking. For another, claspD-2 is the first disjunctive ASP solver in which generators and testers coexist over whole runs, whereas prior approaches rely on rebuilding Boolean constraints to check different assignments.
2 http://www.cs.uni-potsdam.de/claspD
For a complement, we also ran the backtracking-based solver dlv (Dec12) on the instances of MinimalDiagnosis and StrategicCompanies, whose encodings from [Calimeri et al., 2013] are compatible with dlv's (first-order) input language. Like cmodels, dlv could not finish any MinimalDiagnosis instance within 900 seconds. However, with 7 timeouts and about 522 seconds average runtime, dlv was competitive on StrategicCompanies, whose instances are randomly generated and not very amenable to conflict-driven learning.
6 Discussion
We introduced an approach to disjunctive ASP solving along with the claspD-2 system equitably interleaving model generation and minimality checking. Unlike previous unfounded set encodings, our new formulation includes variables to represent relevant parts of candidate assignments to check. By means of assumptions, the truth values of such variables can be fixed to query for unfounded sets wrt. a particular assignment at hand. This enables the reuse of Boolean constraints characterizing unfounded sets, both static ones as well as those recorded from conflicts, in a sequence of queries.
While multi-threaded parallelism has already been exploited to instantiate (disjunctive) programs [Perri et al., 2010], claspD-2 is the first solver offering shared memory multi-threading in the search for answer sets of disjunctive programs. In this work, we presented the initial version of claspD-2, whose fine-tuning for ΣP2 -hard problem solving is still progressing. For instance, we aim at more elaborate approaches to schedule partial checks than our current ad hoc strategy or the one of dlv [Pfeifer, 2004]. A second issue to future work is exploring in how far the search for unfounded sets can be geared towards effectiveness in pruning the space of candidate models. As a side effect of its decision heuristic, the tester of dlv [Maratea et al., 2010] identifies ⊆-minimal unfounded sets, but a systematic investigation of unfounded set "optimization" is yet missing. Finally, we envisage a native treatment (without compiling to simpler constructs) of recursive aggregates (cf. [Alviano et al., 2011]) involved in HCCs as a means to increase expressiveness in the future.
@inproceedings{ijcai2013p140,
title = {Advanced Conflict-Driven Disjunctive Answer Set Solving},
author = {Gebser, Martin and Kaufmann, Benjamin and Schaub, Torsten},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {912--917},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/140},
}
TY - CPAPER TI - Advanced Conflict-Driven Disjunctive Answer Set Solving AU - Gebser, Martin AU - Kaufmann, Benjamin AU - Schaub, Torsten T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 912 EP - 917 UR - https://ijcai.org/proceedings/2013/140 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: