Lazy Atom Discovery in Compilation-Based ASP Solving

State-of-the-art Answer Set Programming (ASP) systems that adopt the Ground&Solve approach are limited by the grounding bottleneck. This issue arises whenever the grounding produces a large propositional program that cannot be handled efficiently during solving. The grounding bottleneck can be mitigated through compilation-based ASP solving, which avoids generating propositional rules for selected “problematic” subprograms. However, compilation-based ASP systems generate in advance the propositional atoms required for solving the problem. As a consequence, as soon as a large number of propositional atoms is required, also this approach exhibits overhead. In this paper a novel compilation-based technique is presented that overcomes this limitation by discovering propositional atoms lazily, i.e., during the solving process. Empirical results confirm the effectiveness of the approach.