Current ASP solvers feature diverse optimization techniques that highly influence their performance, causing systems to outperform each other depending on the domain at hand. We present I-DLV+MS, a new ASP system that integrates an efficient grounder, namely I-DLV, with an automatic solver selector: machine-learning techniques are applied to inductively choose the best solver, depending on some inherent features of the instantiation produced by I-DLV. In particular, we define a specific set of features, and build our classification method for selecting the solver that is supposed to be the "best" for each input among the two state-of-the-art solvers clasp and wasp. Despite its prototypical stage, performance of the new system on benchmarks from the 6th ASP Competition are encouraging both against the state-of-the-art ASP systems and the best established multi-engine ASP system, ME-ASP.
Answer Set Programming (ASP) [3,16] is a declarative programming paradigm proposed in the area of non-monotonic reasoning and logic programming. The language of ASP is based on rules, allowing (in general) for both disjunction in rule heads and nonmonotonic negation in the body; such programs are interpreted according to the answer set semantics [15,17]. Throughout the years the availability of reliable, high-performance implementations [7,13] made ASP a powerful tool for developing advanced applications in many research areas, ranging from Artificial Intelligence to Databases and Bioinformatics, as well as in industrial contexts [7,19,22,28,30].
Although the performance of current ASP systems can be, in general, defined as good enough for a number of real-world applications, they feature several different optimization techniques, thus causing systems to outperform each other depending on the domain at hand. This is due to the different data structures, input simplification and heuristic implemented in the ASP solvers that allow suiting well depending on the characteristic of the domains, as reported in the results of the last published ASP competition [8].
The capability to enjoy good performance over different problems domains has already been pursued by neighbour communities, by means of proper strategies of algorithm selection [29]; we cite here, for instance, what has been done for solving propositional satisfiability (SAT) [31] and Quantified SAT (QSAT) [25]. This approach consists of building machine learning techniques to inductively choose the "best" solver on the basis of some input program characteristics, or features. As for what ASP is concerned, some interesting works in this respect have already been carried out in [21]; furthermore, in [11] similar strategies have been used in order to select the "best" configuration for the solver clasp.
In this paper we present I-DLV+MS, a new ASP system that integrates an efficient grounder, namely I-DLV [5], with an automatic solver selector: machinelearning techniques are applied to inductively choose the best solver, depending on some inherent features of the instantiation produced by I-DLV.
We define a specific set of features, and then and carry out an experimental analysis for computing them over the ground versions of all benchmarks submitted to the 6th ASP Competition [12]; we build then our classification method for selecting the solver that is supposed to be the "best" for each input among the two state-of-the-art solvers clasp [10] and wasp [1]. Furthermore, we test I-DLV+MS performance both against the state-of-the-art ASP systems and the best established multi-engine ASP system ME-ASP [21], that is the winner of the 6th ASP Competition. The tests prove that I-DLV+MS, even though still at a prototypical stage, already shows good performance.
Notably, I-DLV+MS participated in the latest (7th) ASP competition [14], resulting as the winner in the regular track, category SP (i.e., one processor allowed).
In the remainder of the paper we introduce I-DLV+MS providing the reader with an overview of the system, and we then describe the proposed classification method along with the selected features it relies on. We discuss a thorough experimental activity afterwards, and eventually draw our conclusions.
We briefly recall here syntax and semantics of Answer Set Programming.
A variable or a constant is a term. An atom is a(t 1 , . . . , t n ), where a is a predicate of arity n and t 1 , . . . , t n are terms. A literal is either a positive literal p or a negative literal not p, where p is an atom. A disjunctive rule (rule, for short) r is a formula H(r) denotes the set {a 1 , ..., a n } of head atoms, and by B(r) the set {b 1 , ..., b k , not b k+1 , . . . , not b m } of body literals. B + (r) (resp., B − (r)) denotes the set of atoms occurring positively (resp., negatively) in B(r). A rule r is safe if each variable appearing in r appears also in some positive body literal of r.
An ASP program P is a finite set of safe rules. An atom, a literal, a rule, or a program is ground if no variables appear in it. Accordingly with the database terminology, a predicate occurring only in facts is referred to as an EDB predicate, all others as IDB predicates; the set of facts of P is denoted by EDB(P ).
Let P be a program. The Herbrand Universe of P , denoted by U P , is the set of all constant symbols appearing in P . The Herbrand Base of a program P , denoted by B P , is the set of all literals that can be constructed from the predicate symbols appearing in P and the constant symbols in U P .
Given a rule r occurring in P , a ground instance of r is a rule obtained from r by replacing every variable X in r by σ(X), where σ is a substitution mapping the variables occurring in r to constants in U P ; ground(P ) denotes the set of all the ground instances of the rules occurring in P .
An interpretation for P is a set of ground atoms, that is, an interpretation is a subset I of B P . A ground positive literal A is true (resp., false) w.r.t. I if A ∈ I (resp., A � ∈ I). A ground negative literal not A is true w.r.t. I if A is false w.r.t. I; otherwise not A is false w.r.t. I. Let r be a ground rule in ground(P ). The head of r is true w.r.t. I if H(r) ∩ I � = ∅. The body of r is true w.r.t. I if all body literals of r are true w.r.t. I (i.e., B + (r) ⊆ I and B − (r) ∩ I = ∅) and is false w.r.t. I otherwise. The rule r is satisfied (or true) w.r.t. I if its head is true w.r.t. I or its body is false w.r.t. I. A model for P is an interpretation M for P such that every rule r ∈ ground(P ) is true w.r.t. M . A model M for P is minimal if no model N for P exists such that N is a proper subset of M . The set of all minimal models for P is denoted by MM(P ).
Given a ground program P and an interpretation I, the reduct of P w.r.t. I is the subset P I of P , which is obtained from P by deleting rules in which a body literal is false w.r.t. I. Note that the above definition of reduct, proposed in [9], simplifies the original definition of Gelfond-Lifschitz (GL) transform [17], but is fully equivalent to the GL transform for the definition of answer sets [9].
Let I be an interpretation for a program P . I is an answer set (or stable model) for P if I ∈ MM(P I ) (i.e., I is a minimal model for the program P I ) [24,17]. The set of all answer sets for P is denoted by AN S(P ).
The architecture of I-DLV+MS is reported in Figure 1. The Preprocessor module analyzes the input program P, and interacts with the I-DLV system in order to determine if the input program is non-disjunctive and stratified, as these kinds of programs are completely evaluated by I-DLV without the need for a solver. If this is not the case, the Grounding analyser module extracts the intended features from the ground program produced by I-DLV and passes them to the classification module.
Then, the Solver Selector, based on proper classification algorithms, tries to foresee, among the available solvers, which one would perform better, and selects it. This module is based on Decision Trees, a non-parametric supervised learning method used for classification [26]; this classifier aims at creating a model that predicts the value of a target variable by learning simple decision rules inferred from the data features.
We use an optimized version of tree algorithm implemented in scikit-learn library [23], namely CART (Classification and Regression Trees) [2]. The algorithm is a variant of C4.5 [27], and differs from it as it supports numerical target variables and does not compute rule sets. I-DLV+MS currently supports the two state-of-the-art ASP solvers clasp and wasp. Nonetheless, the modular architecture of I-DLV+MS easily allows one to update the solvers or even add additional ones. Clearly, such changes would require the prediction model to be retrained with appropriate statistics on the new solvers.
I-DLV+MS is freely available at [6].
As already introduced, the machine-learning technique herein employed selects the best solver according to some specific features of the input program. In this work, we selected several features with the aim of catching two fundamental aspects of ASP programs:
-Atoms ratios. We considered five different ratios that represent the type of atoms and a raw measure of their distribution in the input ground program: where F is the total number of facts and always true atoms, R the total number of ground rules, P A/N A the total number of positive/negative atoms and BA the total number of atoms appearing in rule bodies. -Rules ratios. We considered five different ratios that represent the type of rules and a raw measure of their distribution in the input ground program, taking into account also advanced constructs of the ASP-Core-2 standard language [4], such as choices, aggregates, and weak constraints:
where C is the total number of strong constraints, W the total number of weak constraints, SR the total number of standard rules, CR the total number of choice rules and W R the total number of weight rules. Please note with standard rules we denote rules without aggregate or choice atoms; weight and choice rules, instead, handle aggregate literals and choice atoms generated by the grounder.
In this section we report the results of an experimental activity performed in order to evaluate the approach implemented into I-DLV+MS. In particular, we performed two distinct sets of experiments, that are discussed in the following.
Experiments have been performed on a NUMA machine equipped with two 2.8GHz AMD Opteron 6320 and 128 GiB of main memory, running Linux Ubuntu 14.04.4 . Binaries were generated with the GNU C++ compiler 4.9.0. As for memory and time limits, we allotted 15 GiB and 600 seconds for each system per each single run.
With the first set of experiments, we aimed at preliminarly assessing the machinelearning-based model for solver selection, i.e., checking the quality of the choice made for each input. To this end, we took the benchmarks from the latest available ASP Competition [12] and ran I-DLV+MS along with two distinct combinations of the I-DLV grounder with the latest available versions, at the time of writing, of clasp and wasp solvers, respectively: clasp version 3.2.1 and wasp version 2017-05-04.
Basically, this allows us to easily compare the performance of the solver chosen by I-DLV+MS against the best one for each set of benchmarks. A system equipped with a perfect selector would ideally match the performance of the best solver for each benchmark, net of possible overheads.
Results are reported in Table 1: first column shows the name of the benchmark, while the next pairs report the solved instances and average times per each tested system (each benchmark featured 20 instances). The best performing combination among I-DLV +clasp and I-DLV +wasp is highlighted in bold, on a benchmark basis. Results show that I-DLV+MS performance is very close to the best solver; in particular, the system show the same performance of the best solver in 17 domains out of 24, suggesting that the defined measures, along with the chosen model, lead to good choices. Furthermore, the total number of instances solved by I-DLV+MS is 327, while for I-DLV +clasp and I-DLV +wasp is 292 and 256, respectively. It is worth noting that, even when the choice was right, I-DLV+MS pays some overhead. This is due to the fact that the ground program produced by I-DLV is not directly passed to the solver; rather, it must be analyzed in order to extract the features needed for making the choice: intuitively, huge ground programs might hence cause a loss of performance during the features extraction.
In the second set of experiments we compared I-DLV+MS against the latest available version of ME-ASP3 ), the state-of-the-art among multi-engine ASP solvers, resulted as the winner of the 6th ASP Competition. Differently from I-DLV+MS, ME-ASP employs machine-learning techniques to inductively choose the best ASP solver on a per-instance basis.
Figure 2 reports the cactus plot comparing I-DLV+MS and ME-ASP. Interestingly, even though I-DLV+MS is a prototypical system, on the overall, it showed encouraging performance: indeed, it solved 327 instances, 49 more instances with respect to what ME-ASP did.
The two systems are similar, yet they feature some key differences; in particular, the main differences are due to the nature and the number of systems used. First of all, ME-ASP computes features of the input program at hand over a ground program produced by gringo system, while I-DLV+MS makes use of I-DLV. Furthermore, the main interesting difference is due to the fact that ME-ASP manages five solvers, way more than the mere two taken into account by I-DLV+MS. On the one hand, the strategy of using a large pool of solver engines, as in the case of ME-ASP, allows to solve a significant number of instances uniquely, i.e., instances solved by only one solver, as the different engines use evaluation strategies that can be substantially different; nevertheless, such differences imply that a high price is paid in case of a wrong choice. On the other hand, when the space for choices is narrowed, the probability of picking the wrong solver decreases, and this might lead to a more consistent behaviour, as in the case of I-DLV+MS.
Notwithstanding the good performance of I-DLV+MS, the system is still in a prototype phase. As future work, we aim to test additional supervised learning method and also several frameworks for automatic algorithm configuration, like Autofolio [20] or Auto-WEKA [18]. We also plan to significantly extend experiments over additional domains and analyze the possible overfitting of the model and try different splits of the dataset for the train and test set among the available problems. Moreover, we aim to both include additional ASP solvers with different parameterizations, and explore more features for improving the classification capabilities and achieve better overall performance.
In addition, we are studying the possibility of taking advantage from machinelearning techniques for improving performance of ASP grounding engines; in particular, we plan to develop a built-in automatic algorithm selector within the I-DLV system (which I-DLV+MS is based on), thus opening up the possibility to dynamically adapt all the optimization strategies to the problem at hand.
In this work, we made use of machine-learning techniques in the ASP solving scenario, with the aim of designing and producing an efficient automatic ASP solver selector. To this end, we first selected syntactic features that represent specific characteristics of ground ASP programs, in order to be able to perform accurate classifications. Then, we trained the model and performed an extensive experimental evaluation on problems from the 6th ASP Competition. Experiments are very promising, as I-DLV+MS showed very good performance despite its prototypical nature. Indeed, our system outperforms both its ASP component solvers and the winner of the 6th ASP Competition. Such good performance is confirmed by the success in the latest (7th) ASP competition [14], where the system won the regular track in the SP category.