Enhancing Lazy Grounding with Lazy Normalization in Answer-Set Programming

Jori Bomanson, Tomi Janhunen, Antonius WeinzierlAAAI 2019 · DOI

Abstract

Answer-Set Programming (ASP) often suffers from the "grounding bottleneck," where the instantiation of variables into a ground program leads to memory exhaustion. This paper presents lazy normalization, a technique implemented in the Alpha solver that unfolds complex aggregates into simple rules during search. By utilizing sorting networks and a novel enumeration built-in, this approach enables ASP to solve large-scale problems previously inaccessible to traditional ground-and-solve systems.

Introduction

ASP is a powerful declarative paradigm for solving combinatorial search problems. However, its traditional "ground-and-solve" workflow faces a significant hurdle: the grounding bottleneck. Before the search for a solution begins, the high-level program must be fully instantiated into a variable-free ("ground") version. For complex real-world problems, this ground program can grow exponentially, exhausting system memory before the solver even starts.

While "lazy grounding" was developed to mitigate this by generating rules on-the-fly, it has historically struggled with aggregates—functions like #count or #sum. This paper introduces lazy normalization, a technique that allows these aggregates to be handled efficiently within a lazy grounding framework.

Lazy Normalization and Sorting Networks

The authors propose "unfolding" aggregates into a series of standard, simple rules as the search progresses. This process, termed lazy normalization, relies on two key innovations:

  1. The Enumeration Built-in (enum): This atom assigns a unique, contiguous index to ground terms as they are encountered. This provides a stable sequence (1, 2, 3...) that the solver can use for counting or summing, even without knowing the total number of elements beforehand.
  2. Sorting Networks: To encode the counting logic efficiently, the authors utilize Batcher’s odd-even merge sorting networks. These networks are "data-oblivious," meaning their structure is independent of the input values, making them ideal for incremental, lazy instantiation.
Hierarchical structure of a sorting network used for lazy normalization of aggregates.

By using $O(n \log^2 n)$ encodings, the system ensures that the number of generated rules remains manageable even as the data scale increases. This transparency allows the solver to use existing optimization techniques, such as conflict-driven clause learning, on the aggregates.

Evaluation and Performance

The approach was evaluated using custom benchmarks designed to stress-test the grounding process, including robot simulations and large-scale summation tasks. The results demonstrate that lazy normalization effectively bypasses the grounding bottleneck.

In a robot simulation benchmark, traditional solvers like Clingo and Dlv2 reached their memory limits at 600 time steps. In contrast, Alpha, using lazy normalization, successfully scaled to 2000 time steps while maintaining a low memory footprint.

Performance comparison of Alpha (lazy grounding) against Clingo and Dlv2 on the robot simulation benchmark.

As shown in the table above, Alpha's memory usage remained stable (between 80 MB and 620 MB), whereas competing solvers hit a 40 GB limit and crashed. This demonstrates that lazy normalization opens ASP to entirely new classes of long-horizon simulation problems.

Conclusion and Future Work

Lazy normalization represents a significant step forward for ASP. By converting complex aggregates into standard rules, the solver can leverage its full suite of optimization tools on previously "black box" functions. While current work focuses on monotone aggregates, future research will focus on extending this framework to non-monotone and convex aggregates, further broadening the applicability of lazy grounding in complex domains.

Summary updated

BibTeX
@inproceedings{bomanson2019enhancing,
  author = {Jori Bomanson and Tomi Janhunen and Antonius Weinzierl},
  title = {{Enhancing Lazy Grounding with Lazy Normalization in Answer-Set Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012694},
}
Figure