Introduction

Answer Set Programming (ASP) [1,2] is a well-known declarative AI formalism for KRR. Thanks to the availability of efficient implementations, ASP finds extensive applications in several AI sub-areas [3], such as Planning [4], Scheduling [5,6], Natural Language Processing [7,8,9], and Databases [10,11,12].

Traditional ASP systems, such as CLINGO [13] and DLV [14], are based on the Ground&Solve approach [15]. Intuitively, an input program is first "grounded" to compute a variable-free equivalent propositional program; and subsequently, the grounded program is "solved" by employing a CDCL-like algorithm [16] that computes its answer sets. However, such an approach intrinsically suffers from the so-called grounding bottleneck, i.e., getting rid of variables already consumes all the computational resources (i.e., time and/or space) in several cases of practical interest [17,18].

The grounding bottleneck [19] has been approached from several perspectives. These include hybrid formalisms [20,13,18,21], lazy grounding architectures [22,23,24,25,26], complexity-driven program rewritings [27,28], and program compilation into propagators [29,30,31,32]. Among these, compilation-based approaches demonstrated that the grounding can be skipped in some relevant cases by compiling rules in propagators able to ground rules' inferences. Such techniques were first proposed for subprograms acting as constraints [30,31]. More recently, the ProASP system [32] has been proposed. ProASP demonstrated that it is possible to devise a compiler also for rules "generating" answer sets (i.e., involving non-stratified negation). In ProASP, a tight [33] non-ground input program is first pre-processed by applying a rewriting encompassing program completion [34] and normalization (i.e., it produces rules of two kinds). Then, the compiler generates code for both Herbrand base generation and rule propagators. That code is injected in the CDCL solver Glucose [35] to initialize variables and simulate the presence of ground rules, respectively. In this way, the ProASP compiler produces a solver specific for the non-ground program in input that needs no grounder. Clearly, ProASP implements an approach that is basically at the antipodes of Ground&Solve, since it compiles all rules of the program.

However, empirical evidence showed that compiling all rules of an ASP program does not pay off in all cases w.r.t. traditional approaches [31]. This is not surprising. It is well-established that there is no free lunch in ASP solving [36], i.e., no single algorithm is the best in all cases. Under typical operational scenarios, it is plausible that certain rules of the program can be efficiently grounded and, thus, are amenable to be processed using the traditional architecture; whereas, for the remaining part of the program, which is made of rules that are subject to the grounding bottleneck, a compilation-based system could offer a viable solution for their evaluation. This latter case, which is very common in practice, cannot be approached in the best possible way with current state-of-the-art ASP systems, that either ground or compile everything.

In the paper "Blending grounding and compilation for efficient ASP solving", we presented a compilation-based architecture, built on top of the ProASP system, for blending grounding and compilation. This novel approach allows for an unrestricted blending of both methods and aims at achieving superior performance by combining the advantages of both approaches.

In this paper, we overview hybrid ASP solving, outline its strengths, and discuss future directions of this line of research.

Hybrid ProASP: Blending Grounding and Compilation

In this section we describe the extended architecture of the ProASP system that exploits an optimized rewriting strategy and allows for the compilation of a program into a hybrid ASP solver (i.e. mixing Ground&Solve and Compilation) without any compilability restrictions that existing compilation-based approaches [30,31] are subject to.

The ProASP system implements two different stages, namely Compilation and Solving stages. The former is used to build a hybrid solver starting from a non-ground program Π, while the latter employs the obtained ad-hoc hybrid solver to compute an answer set Π ∪ 𝐹 , where 𝐹 is a set of facts representing a specific problem instance. At Compilation Stage ProASP system takes as input a non-ground program Π and compiles it into a hybrid solver. To this end, the input program Π is fed into the Compiler module that analyzes Π, identifies the rules that should be compiled and those that should be grounded, and then compiles them properly. More precisely, the Compiler first applies a pre-processing step that extends the normalization of ProASP to allow grounded rules to coexist with propagators, no matter if they are involved in a recursive definition. Then, the rules to be compiled follow the usual path of ProASP, i.e., they are compiled in propagators; whereas the remaining rules are compiled in a code that performs grounding, i.e., code that generates propositional clauses that are stored in the Glucose data structures. As a result, we obtain an ASP system that blends compilation and grounding.

At Solving Stage, instead, ProASP takes as input a set of facts 𝐹 denoting a specific instance of the program Π that should be solved, and computes an answer set of Π ∪ 𝐹 , if any, or proves its incoherence. First of all, the input instance 𝐹 is given as input to the Hybrid Generator module that generates the set of relevant atoms [32] for computing the answer set of Π ∪ 𝐹 together with the ground instantiations of rules of Π that should be grounded. Produced ground rules are successively transformed into a set of clauses [33] that, together with generated atoms, are used to initialize the Glucose SAT solver at the core of the ProASP system. At this point, Glucose starts the CDCL for computing an answer set of Π ∪ 𝐹 . At each step of the CDCL algorithm, Glucose chooses a branching literal 𝑙 and performs the unit propagation by (i) considering the generated clauses encoding the ground rules and (ii) using the Propagator module, for simulating the inferences of the remaining rules. During the CDCL, as soon as the current interpretation becomes inconsistent, the conflicting literals are analyzed according to the propagation clauses that derived them. More precisely, for all those literals that have been derived from compiled propagators, Glucose uses the Propagator module to reconstruct the propagation clauses, while, for all other literals, Glucose analyzes its internal clauses that caused the propagation. As soon as the current interpretation is total or the consistency cannot be restored, then the CDCL stops. At this point, if such total interpretation 𝑀 has been found, then 𝑀 is an answer set of Π ∪ 𝐹 , otherwise ProASP returns ⊥, denoting that Π ∪ 𝐹 has no answer sets.

Scalability of hybrid ASP solving

We report here about the final experiment performed in [37], where the ProASP system with hybrid solving enabled has been compared to the state-of-the-art Ground&Solve ASP system CLINGO on wellestablished benchmarks featuring 2366 instances from 14 application domains. In this evaluation, we considered eight variants of ProASP representing different ways of blending grounding and compilation by splitting programs by rule type. More precisely, we identified the following three types of rules: (CS) constraints not containing aggregates; (AG) rules containing aggregates; (RL) normal rules; and also their combinations, i.e., RL+CS, RL+AG, and CS+AG. Additionally, we also consider the two versions of ProASP in which the whole program is compiled or grounded. Finally, we label HYBRID-PROASP the ProASP version obtained by considering the best split for each benchmark. Obtained results are reported in Figure 1 where the two cactus plots report, respectively, time and memory consumption. Recall that, in a cactus plot, instances are sorted by memory (or time) usage, and a point (𝑖, 𝑗) indicates that a solver is capable of solving the 𝑖-th instance with a memory (or time) limit of 𝑗 megabytes (or seconds), respectively. As it is evident from the plots, the hybrid solving results in significant performance improvements w.r.t. the state-of-the-art by solving 513 more instances and consuming much less memory (roughly 60%). For further details, we refer reader to [37].

Discussion

ASP systems based on Ground&Solve approach are generally effective, but they can struggle with the grounding bottleneck. On the other hand, compilation-based ASP systems have shown that, in certain cases, grounding can be avoided. However, neither approach pays off in all cases.

By developing a technique that seamlessly combines grounding and compilation, we achieved notable improvements over existing compilation-based methods and current state-of-the-art implementations. This is a very promising result, expanding the applicability of ASP as an AI tool for solving complex combinatorial problems.

As far as future work is concerned, since the ProASP system does not support the entire ASP-Core 2 standard, it would be interesting to extend the benefit of the blending also to a wider class of programs such as non-tight programs and disjunctive ones. Another promising avenue is the exploration of a more fine-grained-and possibly automated-procedure for selecting which rules to ground or compile. However, this presents a significant challenge arising from the unique nature of compilation, which must be performed prior to executing any instance of the problem.