Compilation of ASP programs: Recent developments

Abstract

Answer Set Programming (ASP) is a well-known declarative AI formalism developed in the area of logic programming and nonmonotonic reasoning. Modern ASP systems are based on the ground&solve approach. Although efective in industrial and academic applications ground&solve ASP systems are still unable to handle some classes of programs because of the so-called grounding bottleneck problem. Compilation of ASP programs demonstrated to be an efective technique for overcoming the grounding bottleneck. In the paper titled “Compilation of Aggregates in ASP Systems”, which we presented in the Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI 2022), the first compilation-based approach for ASP programs that contain aggregates has been presented. In this paper, we outline the benefits of compiling ASP programs and mention possible developments in this line of research.

1. Introduction

Answer Set Programming (ASP) [ 1 ] is a fully declarative AI formalism. ASP was developed in the Logic Programming and Knowledge Representation communities and represents the most well-known logic formalism that is based on stable model semantics [ 2 ]. ASP demonstrated to be very useful for representing and solving many classes of problems. Indeed, ASP features both a standardized first-order language and several eficient systems [ 3 ]. ASP has many applications both in academia and in industry such as planning, scheduling, robotics, decision support, natural language understanding, and more (cfr. [ 4 ]). ASP is supported by eficient systems, but the improvement of their performance is still an open and challenging research topic. State-of-the-art ASP systems are based on the ground&solve approach [ 5 ]. The firstorder input program is transformed by the grounder module in its propositional counterpart, whose stable models are computed by the solver, implementing a Conflict-Driven Clause Learning (CDCL) algorithm [ 5 ]. ASP implementations based on ground&solve, basically, enabled the development of ASP applications. However, there are classes of ASP programs whose evaluation is not eficient (sometimes not feasible) due to the combinatorial blow-up of the program produced by the grounding step. This issue is known under the term grounding bottleneck [ 6, 7 ]. Many attempts have been done to approach the grounding bottleneck, from language extensions [ 6, 8, 9, 10, 11, 12, 13 ] to lazy grounding [ 14, 15, 16 ]. These techniques obtained good preliminary results, but lazy grounding systems are still not competitive with ground&solve systems on common problems [ 3 ]. Recent research suggests that compilationbased techniques can mitigate the grounding bottleneck problem due to constraints [ 17, 18 ]. Essentially, their idea is to identify the subprograms causing the grounding bottleneck, and subsequently translate them to propagators, which are custom procedures that lazily simulate the ground&solve on the removed subprograms. Problematic constraints are removed from the non-ground input program and the corresponding propagator is dynamically linked to the solver to simulate their presence at running time. Compilation of ASP programs demonstrated to be an efective technique for overcoming the grounding bottleneck. This approach is meant to speed-up computation by avoiding full grounding and exploiting information known at compilation time to create custom procedures that are specific to the program at hand. In the paper titled “Compilation of Aggregates in ASP Systems”, that we presented in the ThirtySixth AAAI Conference on Artificial Intelligence (AAAI 2022) [ 19 ], the rfist compilation-based approach for ASP programs that contain aggregates [ 20 ] has been presented1, despite aggregates are among the most relevant and commonly-employed constructs of ASP [ 21 ]. In this paper, we propose a compilation-based approach for ASP programs with aggregates. We identify the syntactic conditions under which a program with aggregates can be compiled, thus extending the definition of compilable subprograms of [ 17 ]. Then, we implement the approach on top of the state-of-the-art ASP solver wasp [ 22 ]. In this paper we overview our compilation technique, outline the benefits of compiling ASP programs, and mention possible developments in this line of research. In the following, we assume the reader familiar with Answer Set Programming syntax and semantics, and refer the reader to introductory and founding papers for details [ 1, 2, 20 ].

2. Compilation-based approaches

In recent years, compilation-based approaches have been proposed to overcome the grounding bottleneck problem. Basically, the idea behind these approaches is to compile the groundingintensive part of an ASP program into a dedicated procedure, named propagator, that simulates it into an ASP solver during the solving phase. A first attempt has been proposed in [ 17 ] where the authors identified some syntactic conditions that allow the compilation of a subprogram into a lazy propagator. In this approach, the compiled program is omitted in the original program and is simulated by a procedure that, as soon as a candidate stable model, , of the remaining program is computed, checks whether is coherent or not with omitted subprogram. If it is the case then the candidate stable model is also a model of the original program otherwise violated constraints are added into the solver and the model computation process restarts. This strategy proved to be very efective on grounding-intensive benchmarks and so it motivated the idea to push forward the concept of propagators. Another compilation-based approach for ASP constraints has been proposed in [ 18 ]. This work introduced the translation of constraints of an ASP program into a propagator of the CDCL algorithm that works on partial interpretation. More precisely, constraints are removed from the input program and they are compiled into an eager propagator, that simulates the propagation of the omitted constraints during the solving phase. In this approach solver and propagator works together in order to prevent constraints failure and so, unlike lazy propagators, the candidate stable model produced by the solver will be coherent also with the omitted constraints. Eager compilation of grounding-intensive 1Recipient of the “Outstanding student paper award honorable mention of AAAI2022” constraints introduced significant improvements outperforming traditional ASP solvers but, unfortunately, it is limited to simple constraints that do not contain aggregates. Aggregates are among the most used constructs that make ASP efective in representing complex problems in a very compact way and very often their grounding could be a bottleneck. An attempt to extend the compilation also to constraints with aggregate has been proposed in [ 23 ]. Basically, this approach provides a compilation strategy for constraints with a count aggregate into an eager propagator. Count aggregates are normalized under a unique comparison operator, ≥ , and then, following the idea described in [ 18 ], they are compiled into a custom procedure that simulates aggregates propagations. Results obtained by this extension highlighted the strength of the contribution solving more instances than state-of-the-art system wasp on hard benchmarks from ASP competitions [ 7 ] containing constraints with count aggregate. Starting from the idea proposed in [ 23 ] we generalized the compilation of aggregates to rules with sum or count aggregate [ 19 ]

2.1. Conditions for Splitting and Compiling Programs

An ASP program is a set of rules of the form: ℎ ← 1, . . . , , ∼ +1, . . . , ∼ (1) with ≥ ≥ 0, where ℎ is a standard atom referred to as head and it can absent, whereas 1, . . . , , ∼ +1, . . . , ∼ is the body, 1, . . . , are atoms, and +1, . . . , are standard atoms. Moreover, for a rule , and are two sets containing the head and the body of a rule , respectively, + and − are two sets containing the positive and the negative body of , respectively, denotes the set of aggregate atoms appearing in , and Conj +() and Conj − () denotes the set of positive and negative standard literals appearing in the aggregate atoms of the body, respectively. Given a program , a sub-program of is a set of rules ⊆ . In what follows, we denote with preds() the set of predicate names appearing in where is a structure (literal, conjunction, rule, program, etc). Moreover, given a set of rules , let head ( ) = { | ∈ , ∈ }.

Definition 1. Given an ASP program , the dependency graph of , denoted , is a labeled graph (, ) where is the set of predicate names appearing in some head of , and contains (i) (1, 2, +), if there is ∈ | 1 ∈ preds(+) ∪ preds(Conj +()), 2 ∈ preds(); (ii) (1, 2, − ), if there is ∈ | 1 ∈ preds(− ) ∪ preds(Conj − ()), 2 ∈ preds(). Definition 2. Given an ASP program , an ASP sub-program ⊆ is compilable w.r.t. if (i) has no loop in it; (ii) for each ∈ pred (head ( )), ∈/ pred ( ∖ ); (iii) given two rules 1, 2 ∈ , 1 ̸= 2, preds(1 ) ∩ preds(2 ) = ∅; and (iv) for each ∈ , || ≤ 1.

2.2. Normalization of the Input Program

In the following, we describe the main preprocessing steps that are performed to compile the input sub-program. First of all the sub-program is analyzed in order to be split into two sub-programs, namely lazy and eager . This analysis consists of navigating the dependency graph starting from nodes that have no incoming edges and recursively label predicates that appear in the body of a rule whose head predicate has been already labeled. In this way, the rules whose head predicate has not been labeled could be treated in a lazy way ( lazy ); other rules are in eager . For eager , we perform a rewriting to obtain a normalized form with rules of a specific format in order to have a uniform treatment of all the rules to compile. Also, for a structure (set, list, conjunction, etc.) of elements , let vs() be the set of all variables appearing in . Step 1. Each rule ∈ eager of the form (1), with || = 1, ({Vars : Conj }) ≺ ∈ , and ≺∈ { <, ≤ , >, ≥} , is replaced by the following rules: 1. as(Vars, ) ← Conj ; 2. bd (, ) ← ∖ ; 3. aggr (, ) ← dm(, ), ({Vars : as(Vars, )}) ≥ , where = if ≺∈ {≥ and = + 1 if ≺∈ {≤ , >}; 4. ℎ ← bd (, ), aggr (, ) if ≺∈ { >, ≥} and ℎ ← bd (, ), ∼ aggr (, ) if ≺∈ { <, ≤} ; , <}, where is vs(Conj ) ∩ vs( ∖ ). Intuitively, is a set of all variables appearing in both aggregate set and body.

Example 1. Let assume to be the following rule:

Then, is replaced by the following rules: (, ) ← (, ), (, ), #{ : (, ), ∼ ()} ≥ . 1 : as(, ) ← (, ), ∼ () 2 : bd (, ) ← (, ), (, ) 3 : aggr (, ) ← dm(, ),

#{ : as(, )} ≥ 4 : (, ) ← bd (, ), aggr (, ) Step 2. Each rule ∈ eager of the form (1), with || = 1, ({Vars : Conj }) ≺ ∈ , and ≺∈ { =}, is replaced by the rules 1., 2., and by the following rules: 5. aggr 1(, ) ← dm(, ), ({Vars : as(Vars, )}) ≥ ; 6. aggr 2(, ) ← dm(, ), ({Vars : as(Vars, )}) ≥ + 1; 7. ℎ ← bd (, ), aggr 1(, ), ∼ aggr 2(, ).

Step 3. Each rule ∈ eager , with || = 0, is replaced by the following rules: 8. ℎ ← 9. ← 10. ←

aux (vs(+)); aux (vs(+)), , ∼ aux (vs(+)).

This step is applied also to rules from steps 1 and 2. ∀ ∈ {1, . . . , };

Example 2. Let assume to be the following rule:

(, ) ← (, ), ∼ (). 8 : (, ) ← 9′ : 9′′ : 10 :

aux (, ) ← aux (, ), ∼ (, ) ← aux (, ), () ← (, ), ∼ (), ∼ aux (, ).

Intuitively, the normalization ensures that aggregate functions are applied to a set of atoms, and rules are subject to a form of completion [ 24 ]. After applying the normalization step the program contains only rules of the form: (1) ℎ ← (2) ℎ ← , #({ : }) ≥ (3) ℎ ← , #({ : }) ≥ (4) ← 1, ..., Thus, the compiler will only have to produce propagators simulating the above-mentioned four rule types. Finally, it is important to emphasize that atoms of the form dm(· ) and aux (· ) do not appear in the head of any rule in the program, and thus the ASP semantics would make them false in all stable models. Therefore, in our approach, they are treated as external atoms [ 25 ], whose instantiation and truth values are defined at running time in the propagator when the base eager is determined.

2.3. Compilation

The compilation step, basically, follows the baseline described in [ 18 ]. In particular, a rewritten subprogram will be compiled into a C++ procedure that includes propagator code for each rule ∈ . Afterward, the eager propagator procedure is nested into the state-of-the-art system wasp as a dynamic library. In order to better understand the idea behind our approach let us consider the following rules produced by the normalization step: 1 : () :– (, ).

2 : () :– (), #{ : (, )} ≥ 2.

Basically, the idea behind generated propagators is reported in Algorithms 1 and 2. For more details on the automatic generation of such propagators we refer the reader to [ 19 ].

3. Experiments

Our approach has been evaluated in three diferent settings: () A simple benchmark used to show the limits of ground&solve (cfr. [ 19 ]). () All benchmarks from ASP competitions [ 7 ] including at least one rule with aggregates that can be compiled under our conditions. () Grounding-intensive benchmarks from the literature: Component Assignment Problem [ 26 ], Dynamic In-Degree Counting and Exponential-Save [27].

Algorithm 1 Propagator example for 1 1: if ∃ () ∈ then 2: = { : (, )is true} 3: = { : (, )is not assigned} 4: if | ∪ |= 1 then 5: = ∪ {(, ) | ∈ } 6: end if 7: else Algorithm 2 Propagator example for 2 1: for all : ∃ () do 2: = { : (, ) } 3: = { : (, ) } 4: = { : (, ) } 5: if ∼ () ∈ then 6: if | |= 1 then 7: = ∪ {∼ () | ∈ } 8: end if 9: else 10: if () ∈ then 11: if | ∪ |= 2 then 12: = ∪ {() | ∈ } 13: end if 8: if ∃ ∼ () ∈ then 9: = ∪ {(, ) |

(, ) } 10: else 11: if ∃ | (, ) ∈ then 12: = ∪ {()} 13: end if 14: end if 15: end if 14: else 15: if | ∪ |< 2 then 16: = ∪ {∼ ()} 17: else 18: if | |>= 2 then 19: = ∪ {()} 20: end if 21: end if 22: end if 23: end if 24: end for Hardware and Software. In all the experiments, the compilation-based approach, reported as wasp-comp, has been compared with the plain version of wasp [ 22 ] v. 169e40d and with the state-of-the-art system clingo v. 5.4.0 [ 25 ]. Moreover, for Dynamic In-Degree Counting and Exponential-Save we considered also the system alpha [ 16 ], which is based on lazy-grounding techniques. alpha cannot be used for other experiments since it does not support some of the language constructs used in the benchmarks (e.g., choice rules with bounds). Experiments were executed on Xeon(R) Gold 5118 CPUs running Ubuntu Linux (kernel 5.4.0-77-generic), time and memory are limited to 2100 seconds and 4GB, respectively. Results. Concerning the setting (), we report execution time (t) and used memory (mem) for each instance in Table 1. In particular, we observe that clingo and wasp cannot solve instances with ≥ 8000, whereas wasp-comp can eficiently handle instances up to values of = 40000. Concerning the setting () and () we report for each solver the number of solved instances (sol.), the sum of running times (sum t) in seconds and the average used memory (avg mem) in MB. Concerning wasp-comp we report also the compile time in seconds (comp t) that in general cases is not included in the sum of the time, since the compilation is done only once for each benchmark (with the exception of Exponential-Save) and, thus, can be done ofline. Concerning the setting (), we observe that clingo obtains the best performance overall, and it is faster than wasp and wasp-comp. This setting is useful to analyze the performance of the proposed technique on benchmarks that do not present a grounding issues and comparing wasp-comp and wasp, we observe that the former is competitive with the latter in all the benchmarks but Abstract Dialectical Framework and Partner Units, where wasp solves 6 and 17 more instances than wasp-comp. Nonetheless, wasp-comp performs better than wasp on the benchmark Incremental Scheduling, solving 12 more instances. Interestingly, on this benchmark, wasp-comp also uses less memory than wasp and clingo. Indeed, if only 512 MB are available (as reasonable in some cases) wasp-comp solves 57 and 53 instances more than wasp and clingo, respectively. Concerning the setting (), wasp-comp outperforms wasp in all the tested benchmarks solving 133 more instances overall. It is important to observe that each instance of Exponential-Save requires to be compiled since aggregates to be compiled are part of the instances. Therefore, in this benchmark, the solving time includes also the compilation time. Concerning Dynamic In-Degree Counting, wasp-comp and wasp solve the same number of instances, but wasp-comp is much faster. Moreover, we observe that wasp-comp solves 84 more instances than clingo overall. Finally, we observe that wasp-comp is competitive also with alpha, since the latter solves 80 instances of Dynamic In-Degree Counting in 492.0 seconds using 649.1 MB, and 27 instances of Exponential-Save in 332.9s using 227.8 MB.

4. Discussion

The grounding bottleneck is a limiting factor for ASP systems based on the ground&solve architecture. Compilation-based approaches proposed by [ 18 ] ofer the possibility to mitigate this issue in presence of constraints while keeping the benefits of state-of-the-art approaches. Compilation of aggregates introduced significant improvements in grounding-intensive domains outperforming state-of-the-art systems. It is worth observing that, compilation techniques currently are applicable to a limited class of programs. Indeed, the conditions for a subprogram to be compilable cover many cases of practical interest (constraint-like subprograms) and they are orthogonal to many available constructs, such as weak constraints, cautious reasoning and qualitative preferences among answer sets [28], but are far from covering the entire range of possible cases. Indeed, the support for the compilation of rules is limited, since the system does not support: unfounded sets propagation, and answer-sets-generator rules (eg., disjunction, choice rules, and unrestricted negation). The missing constructs are not easy to support, thus there is a long promising route to follow to deliver a system able to compile any ASP program that sufers from grounding bottleneck.

5. Acknowledgements

This work was partially supported by the Italian Ministry of Industrial Development (MISE) under project MAP4ID “Multipurpose Analytics Platform 4 Industrial Data”, N. F/190138/0103/X44 and by Italian Ministry of Research (MUR) under PRIN project “exPlaInable kNowledgeaware PrOcess INTelligence” (PINPOINT), CUP H23C22000280006. [27] J. Bomanson, T. Janhunen, A. Weinzierl, Enhancing lazy grounding with lazy normalization in answer-set programming, in: AAAI, AAAI Press, 2019, pp. 2694–2702. [28] E. Di Rosa, E. Giunchiglia, M. Maratea, A new approach for solving satisfiability problems with qualitative preferences, in: ECAI, volume 178 of FAIA, IOS Press, 2008, pp. 510–514.

References

[1] G. Brewka , T. Eiter , M. Truszczynski , Answer set programming at a glance , Commun. ACM 54 ( 2011 ) 92 - 103 .

[2] M. Gelfond , V. Lifschitz , Classical negation in logic programs and disjunctive databases, New Gener. Comput . 9 ( 1991 ) 365 - 386 .

[3] M. Gebser , N. Leone , M. Maratea , S. Perri , F. Ricca , T. Schaub , Evaluation techniques and systems for answer set programming: a survey, in: IJCAI, ijcai .org, 2018 , pp. 5450 - 5456 .

[4] E. Erdem , U. Öztok, Generating explanations for biomedical queries , TPLP 15 ( 2015 ) 35 - 78 .

[5] B. Kaufmann , N. Leone , S. Perri , T. Schaub, Grounding and solving in answer set programming , AI Mag . 37 ( 2016 ) 25 - 32 .

[6] M. Ostrowski , T. Schaub, ASP modulo CSP: the clingcon system , TPLP 12 ( 2012 ) 485 - 503 .

[7] F. Calimeri , M. Gebser , M. Maratea , F. Ricca , Design and results of the fifth answer set programming competition , Artif. Intell . 231 ( 2016 ) 151 - 181 .

[8] M. Balduccini , Y. Lierler , Constraint answer set solver EZCSP and why integration schemas matter , TPLP 17 ( 2017 ) 462 - 515 .

[9] M. Balduccini , Y. Lierler , Integration schemas for constraint answer set programming: a case study , TPLP 13 ( 2013 ).

[10] R. A. Aziz , G. Chu, P. J. Stuckey , Stable model semantics for founded bounds , TPLP 13 ( 2013 ) 517 - 532 .

[11] B. D. Cat , M. Denecker , M. Bruynooghe , P. J. Stuckey , Lazy model expansion: Interleaving grounding with search , J. Artif. Intell. Res . 52 ( 2015 ) 235 - 286 .

[12] B. Susman , Y. Lierler , Smt-based constraint answer set solver EZSMT (system description) , in: ICLP (Technical Communications) , volume 52 of OASICS , Schloss Dagstuhl - LeibnizZentrum für Informatik , 2016 , pp. 1 : 1 - 1 : 15 .

[13] T. Eiter , C. Redl , P. Schüller , Problem solving using the HEX family , in: Computational Models of Rationality, College Publications, 2016 , pp. 150 - 174 .

[14] A. D. Palù , A. Dovier , E. Pontelli, G. Rossi, GASP: answer set programming with lazy grounding , Fundam. Informaticae 96 ( 2009 ) 297 - 322 .

[15] C. Lefèvre , P. Nicolas , The first version of a new ASP solver : Asperix , in: LPNMR, volume 5753 of Lecture Notes in Computer Science, Springer, 2009 , pp. 522 - 527 .

[16] A. Weinzierl , Blending lazy-grounding and CDNL search for answer-set solving , in: LPNMR , volume 10377 of Lecture Notes in Computer Science, Springer, 2017 , pp. 191 - 204 .

[17] B. Cuteri , C. Dodaro , F. Ricca , P. Schüller , Partial compilation of ASP programs , TPLP 19 ( 2019 ) 857 - 873 .

[18] B. Cuteri , C. Dodaro , F. Ricca , P. Schüller , Overcoming the grounding bottleneck due to constraints in ASP solving: Constraints become propagators , in: IJCAI, ijcai.org , 2020 , pp. 1688 - 1694 .

[19] G. Mazzotta , F. Ricca , C. Dodaro , Compilation of aggregates in ASP systems , in: ThirtySixth AAAI Conference on Artificial Intelligence , AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022 , The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1 , 2022 , AAAI Press, 2022 , pp. 5834 - 5841 . URL: https://ojs.aaai.org/index.php/ AAAI/article/view/20527.

[20] W. Faber , G. Pfeifer, N. Leone , Semantics and complexity of recursive aggregates in answer set programming , Artif. Intell . 175 ( 2011 ) 278 - 298 .

[21] M. Gebser , M. Maratea , F. Ricca , The sixth answer set programming competition , J. Artif. Intell. Res . 60 ( 2017 ) 41 - 95 .

[22] M. Alviano , C. Dodaro , N. Leone , F. Ricca , Advances in WASP, in: LPNMR, volume 9345 of Lecture Notes in Computer Science, Springer, 2015 , pp. 40 - 54 .

[23] G. Mazzotta , B. Cuteri , C. Dodaro , F. Ricca , Compilation of aggregates in ASP: preliminary results , in: F. Calimeri , S. Perri , E. Zumpano (Eds.), Proceedings of the 35th Italian Conference on Computational Logic - CILC 2020 , Rende, Italy, October 13-15 , 2020 , volume 2710 of CEUR Workshop Proceedings, CEUR-WS.org , 2020 , pp. 278 - 296 . URL: http://ceur-ws. org/ Vol- 2710 /paper18.pdf.

[24] K. L. Clark , Negation as failure, in: Logic and Data Bases, Advances in Data Base Theory , Plemum Press, New York, 1977 , pp. 293 - 322 .

[25] M. Gebser , R. Kaminski , B. Kaufmann , M. Ostrowski, T. Schaub , P. Wanko, Theory solving made easy with clingo 5 , in: ICLP (Technical Communications) , volume 52 of OASICS, Schloss Dagstuhl - Leibniz-Zentrum für Informatik , 2016 , pp. 2 : 1 - 2 : 15 .

[26] M. Alviano , C. Dodaro , M. Maratea , Shared aggregate sets in answer set programming , TPLP 18 ( 2018 ) 301 - 318 .