Space Efficient Evaluation of ASP Programs with Bounded Predicate Arities

Thomas Eiter, Wolfgang Faber, Mushthofa Mushthofa

Introduction

Answer Set Programming (ASP) is a powerful declarative paradigm for solving complex combinatorial problems. However, a significant hurdle in its practical application is the "grounding bottleneck." Most modern solvers rely on a "ground-then-solve" approach, which involves expanding rules with variables into all possible ground instances. For many hard problems, this process leads to an exponential explosion in memory usage, often causing solvers to crash before they even begin the search for a solution.

This paper addresses the gap between the theoretical polynomial space complexity of certain ASP programs and the practical memory-intensive nature of current solvers. The authors introduce three novel evaluation methods and a prototype system, BPA (Bounded Predicate Arity), designed to operate within polynomial space limits.

Methodology: The BPA Framework

The core innovation lies in evaluating ASP programs without full grounding. The authors propose three methods tailored to different classes of programs:

  1. Method 1 (Normal Programs): Computes local answer sets by focusing on polynomially-sized subsets of the ground program.
  2. Method 2 (Head-Cycle-Free Programs): Employs a "supporting minimal guess" strategy, iterating over interpretations and verifying minimality in polynomial space.
  3. Method 3 (General Disjunctive Programs): Uses a two-step process to generate candidate models and verify them through subset enumeration.

The BPA system acts as a controller, delegating tasks to external engines. It uses the DLV solver for consistency checks and the XSB Prolog engine for top-down generation of relevant program subsets. This modular approach leverages the "Locality Lemma," which posits that an answer set of a program subset can be an answer set for the entire program if it satisfies all remaining rules.

Experimental Evaluation

The BPA prototype was tested against state-of-the-art solvers DLV and GrinGo/claspD across three benchmarks: 2QBF, ChainStratComp, and Clique.

Memory Efficiency

A key finding is the stability of BPA's memory usage. While traditional solvers exhibit exponential memory growth as problem instances scale, BPA maintains a nearly constant, low memory footprint.

Space usage on 2QBF showing BPA's stable memory footprint compared to the exponential growth of traditional solvers.

In the 2QBF benchmark, for instance, BPA consistently operated within 22-26 MB, whereas competitors quickly exceeded the 2GB RAM limit.

Performance and Robustness

Contrary to the typical trade-off where space efficiency comes at the cost of time, BPA often outperformed traditional solvers on large instances. By avoiding the overhead of massive grounding, BPA remained responsive where other systems became paralyzed.

Time usage on ChainStratComp demonstrating BPA's superior performance on large problem instances.

In the ChainStratComp benchmark, BPA's execution time scaled much more gracefully than its competitors. Furthermore, in the Clique benchmark, BPA successfully completed all 32 instances, while DLV and claspD failed on nearly half due to memory exhaustion.

Conclusion and Future Directions

The BPA framework demonstrates that space-efficient ASP evaluation is not only theoretically possible but practically advantageous for large-scale problems. While the current prototype faces some implementation hurdles, such as memory leaks in external components and a lack of support for advanced features like aggregates, it proves that the grounding bottleneck can be overcome. Future work will focus on integrating these methods directly into solvers and optimizing subprogram pruning to further enhance performance.

Summary updated

Abstract

Answer Set Programming (ASP) has been deployed in many applications, thanks to the availability of efficient solvers. Most programs encountered in practice have an important property: Their predicate arities are bounded by a constant, and in this case it is known that the relevant computations can be done using polynomial space. However, all competitive ASP systems rely on grounding, due to which they may use exponential space for these programs. We present three evaluation methods that respect the polynomial space bound and a generic framework architecture for realization. Experimental results for a prototype implementation indicate that the methods are effective. They show not only benign space consumption, but interestingly also good runtime compared to some state of the art ASP solvers.
BibTeX
@inproceedings{eiter2010space,
  author = {Thomas Eiter and Wolfgang Faber and Mushthofa Mushthofa},
  title = {{Space Efficient Evaluation of ASP Programs with Bounded Predicate Arities}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7592},
}
Figure