Grounding with Bounds

Johan Wittocx, Maarten Mariën, Marc DeneckerAAAI 2008

In the field of automated reasoning, the "grounding" process—translating high-level First-Order Logic (FO) into simple propositional logic—often acts as a significant bottleneck. Naive grounding can lead to a combinatorial explosion, overwhelming even the most advanced SAT solvers. This paper, originally presented at AAAI 2008 by researchers from K.U. Leuven, proposes a novel algorithm to mitigate this "complexity tax" by automatically discovering logical bounds that prune unnecessary computations before they begin.

The Grounding Challenge

Many modern AI systems, such as Answer Set Programming (ASP) or Model Expansion solvers, operate in two distinct phases. First, they ground a high-level theory by substituting variables with specific domain elements. For instance, the general rule "All humans are mortal" is expanded into individual propositions for every human in the domain.

The primary issue is scalability. A formula with multiple variables over a large domain can generate millions of instances. While experts can manually add redundant constraints to guide the grounder, this process is tedious and error-prone. The authors' goal is to automate this "common sense" pruning through a systematic approach that derives bounds from the theory itself.

Methodology: Symbolic Bounds and c-maps

The core of the proposed solution is the concept of c-maps, which assign two types of symbolic bounds to every subformula within a logical theory:

  • ct-bounds (certainly true): Conditions under which a formula is guaranteed to evaluate to true.
  • cf-bounds (certainly false): Conditions under which a formula is guaranteed to evaluate to false.

The researchers developed an any-time refinement algorithm that iteratively sharpens these bounds. It utilizes six primary rules, including the propagation of truth values through the parse tree (top-down and bottom-up reasoning) and the exploitation of functional properties.

Table 1: Propagation rules for deriving certainly true (ct) and certainly false (cf) bounds for logical subformulas.

To handle these bounds efficiently, the system employs Binary Decision Diagrams (BDDs). This allows the grounder to simplify complex logical expressions on the fly, effectively "failing fast" on branches of the search space that cannot lead to a solution.

Experimental Evaluation

The implementation, dubbed GIDL, was tested against 20 standard benchmark problems from the "Asparagus" repository, alongside specific examples in subgraph detection and planning. The results demonstrate that "Grounding with Bounds" is highly effective in practice.

Table 2: Relative size and time for 20 benchmark problems after applying the grounding with bounds algorithm.

Key findings from the experiments include:

  • Size Reduction: The algorithm reduced the size of the grounded theory by at least 10% in nearly half the cases, with "drastic" reductions (orders of magnitude) in 25% of the benchmarks.
  • Significant Speedups: Grounding time was reduced by more than 10% in half the cases, and by over 70% in six of the twenty benchmarks.
  • Early Simplification: Even when the final grounded size was not significantly smaller, the time often decreased because bounds allowed for earlier simplification, reducing peak memory and computational load.
  • Negligible Overhead: The "pre-reasoning" phase to compute bounds typically took less than 0.01 seconds, making it a low-risk optimization.

Insights and Future Directions

A central insight of this work is that redundancy is a feature. In grounding, adding logically redundant information allows the system to skip large, irrelevant search spaces. Furthermore, by looking at the theory holistically rather than sentence-by-sentence, constraints in one part of the logic can provide bounds that simplify distant formulas.

While highly effective, the approach has limitations. Recursive theories can lead to infinite refinement loops, requiring a stop criterion. Additionally, the complexity of BDDs must be managed to prevent them from becoming a bottleneck themselves. Future work may extend these approximate reasoning techniques to other domains, such as querying incomplete databases under integrity constraints.

Summary updated

BibTeX
@inproceedings{wittocx2008grounding,
  author = {Johan Wittocx and Maarten Mariën and Marc Denecker},
  title = {{Grounding with Bounds}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure