Efficient HEX-Program Evaluation Based on Unfounded Sets

Thomas Eiter, Michael Fink, Thomas Krennwallner, Christoph Redl, Peter Schüller

TL;DR

This paper introduces a more efficient method for evaluating HEX-programs, a powerful logic programming paradigm that integrates external computations. By leveraging the concept of "unfounded sets," the authors significantly speed up the process of finding valid answer sets, making HEX-programs more practical for complex AI tasks.

What Problem Does This Paper Address?

Answer Set Programming (ASP) is a declarative problem-solving approach widely used in AI. However, real-world applications often require integrating external data sources (like databases or web services) into these programs. HEX-programs extend ASP to handle these external computations through "external atoms." While existing methods for evaluating HEX-programs exist, they are often computationally expensive, particularly the "minimality check" required to ensure valid answer sets. This check, often referred to as the "explicit FLP check," can dominate the runtime, limiting the scalability of HEX-programs. This paper addresses this bottleneck by proposing a more efficient unfounded set-based approach to the minimality check.

Methods

The core of this paper lies in developing and refining an "unfounded set check" for HEX-programs. This approach is a generalization of techniques used for standard logic programs.

  • Unfounded Set Definition: They extend the notion of unfounded sets to HEX-programs, which are sets of atoms that can be "turned off" without violating program rules, even considering external computations.
  • SAT Encoding: The detection of unfounded sets is translated into a propositional SAT problem. They present two encodings:
  • Basic Encoding (Γ): This encoding is generated specifically for each candidate answer set and assignment, making it less reusable but conceptually simpler.
  • Uniform Encoding (Ω): This advanced encoding is reusable across multiple candidate answer sets and assignments, requiring only temporary assumptions for the solver. While it has a slightly higher initialization cost, it offers significant advantages for programs with many candidate answer sets.
  • Optimizations and Learning: The paper introduces several optimizations:
  • Restricting Search: Focusing the search for unfounded sets only on atoms relevant to the current candidate assignment.
  • Avoiding Guesses: Techniques to avoid redundant computations by fixing the truth values of certain replacement atoms.
  • Learning Nogoods: Strategies to learn from detected unfounded sets to avoid re-evaluating the same issues, guiding the search more effectively.
  • Decision Criterion: A syntactic criterion to determine if an unfounded set check is even necessary, potentially skipping it entirely.
  • Program Decomposition: Breaking down the program into smaller components to apply the decision criterion and unfounded set checks more efficiently.
  • External Behavior Learning (EBL): They integrate EBL techniques to learn from external atom evaluations, further pruning the search space.

Datasets

The paper evaluates their approach on several benchmark datasets:

  • Set Partitioning: A synthetic benchmark used to test basic functionality.
  • Nonmonotonic Multi-Context Systems (MCSs): Benchmarks representing knowledge integration challenges, including both consistent and inconsistent scenarios.
  • Abstract Argumentation: Benchmarks based on abstract argumentation frameworks, a key area in AI reasoning.
  • Conformant Planning: Benchmarks for planning problems where actions have uncertain outcomes.

The authors note that their results are not directly comparable to some previous work due to differences in evaluation criteria (e.g., subset-minimal compatible sets vs. unfounded-free models).

Key Insights and Ideas

  • Unfounded Sets as a More Efficient Minimality Check: The core insight is that checking for unfounded sets is a more efficient alternative to the traditional explicit FLP check for ensuring answer set minimality in HEX-programs. This is because it directly targets the conditions that violate minimality.
  • Reusability of Encodings (Ω): The uniform encoding (Ω) significantly outperforms the basic encoding (Γ) when many unfounded set checks are required, highlighting the benefit of a reusable SAT encoding.
  • Learning from Unfounded Sets (UFL): Learning nogoods from detected unfounded sets is crucial for avoiding redundant computations and guiding the search effectively, especially in complex scenarios.
  • Syntactic Criterion for Skipping Checks: The ability to identify programs or components that cannot have unfounded sets (due to acyclic dependencies) offers a significant shortcut, avoiding computationally expensive checks altogether.
  • EBL's Impact Varies: External Behavior Learning (EBL) provides benefits, especially when combined with the UFS check, but its effectiveness can depend on the specific benchmark and whether all answer sets or just the first one are sought.

Key Results

The paper demonstrates significant performance improvements across various benchmarks:

  • Speedup: The proposed unfounded set checking approach, particularly with the uniform encoding (Ω) and learning techniques, often achieves speedups of several orders of magnitude compared to the explicit FLP check. For instance, in the MCS benchmarks, the Ω encoding was often much faster than the explicit check.
  • Reduced Candidates: The UFS check not only reduces runtime but also decreases the number of candidate answer sets and external atom evaluations.
  • Effectiveness Across Domains: The approach shows consistent improvements across diverse domains like multi-context systems, abstract argumentation, and conformant planning.
  • Decision Criterion Benefits: The syntactic decision criterion, while cheap to compute, can lead to additional speedup, especially when combined with program decomposition.

Limitations and Future Work

  • Heuristics for Partial Assignments: While the authors explored UFS checking on partial assignments, it didn't yield significant benefits in their experiments, possibly due to the effectiveness of UFL. Future work could involve developing more sophisticated, domain-specific heuristics for this.
  • Domain-Specific Knowledge: Incorporating domain-specific knowledge about external atoms into heuristics and learning algorithms is identified as a promising avenue for further improvement.
  • Other Criteria for Skipping Checks: Exploring additional criteria that allow skipping UFS checks efficiently is a key area for future research.
  • Generalizing Program Decomposition: Extending the program decomposition techniques beyond strongly connected components could offer further optimizations.

Summary updated

BibTeX
@article{eiter2014efficient,
  author = {Thomas Eiter and Michael Fink and Thomas Krennwallner and Christoph Redl and Peter Schüller},
  title = {{Efficient HEX-Program Evaluation Based on Unfounded Sets}},
  journal = {J. Artif. Intell. Res.},
  year = {2014},
  doi = {10.1613/jair.4175},
}

Loading related content...

Figure