Conflict-driven ASP solving with external sources

Thomas Eiter, Michael Fink, Thomas Krennwallner, Christoph Redl

TL;DR

This paper introduces a native, conflict-driven approach for solving HEX-programs—a version of Answer Set Programming (ASP) that interacts with external data sources like web resources or description logic reasoners. By integrating External Behavior Learning (EBL) directly into the solver's search loop, the authors move beyond the inefficient "guess-and-check" method, achieving massive speedups and pruning the search space early using learned constraints (nogoods).

What Problem Does This Paper Address?

Answer Set Programming (ASP) is a powerful tool for solving hard combinatorial problems, but it traditionally struggles to "talk" to the outside world. HEX-programs were created to bridge this gap, allowing logic programs to call external "atoms" (e.g., querying a database or running a specialized reasoner).

The traditional way to solve these programs was the translation approach: the solver would guess the truth values of all external calls, find a potential solution (a model candidate), and only then check if those guesses actually matched the external source's behavior. If they didn't, the solver had to start over. This "blind guessing" creates a massive bottleneck, especially when external sources are non-deterministic or the search space is large.

Methods

The authors propose a new algorithm, HEX-CDNL (Conflict-Driven Nogood Learning for HEX), which treats external sources as active participants in the search process rather than afterthoughts.

Key technical contributions include:

  • Native Integration: Instead of translating to standard ASP, the solver builds model candidates from scratch and accesses external sources during the search.
  • External Behavior Learning (EBL): When an external atom is evaluated, the solver doesn't just get a "true/false" answer. It generates nogoods—sets of assignments that are logically impossible. These nogoods are added to the solver's knowledge base to prevent it from ever exploring that specific conflict again.
  • Uninformed vs. Informed Learning:
    • Uninformed: The solver learns basic input-output relationships (e.g., "If input X is true, output Y must be true").
  • Informed: If the developer provides meta-information about the external source (like monotonicity or functionality), the solver can generate much more powerful, "shorter" nogoods that prune significantly larger branches of the search tree.

Datasets

The authors evaluated their approach using several benchmarks designed to test different aspects of external interaction:

  • Set Partitioning: A synthetic benchmark testing how the solver handles the &diff external atom.
  • Bird-Penguin (Default Reasoning): A classic AI problem (Tweety the bird) implemented using Description Logic (DL) atoms.
  • Wine Ontology: A real-world-scale ontology used to test classification under default rules.
  • Multi-Context Systems (MCS): Benchmarks for finding explanations for inconsistencies across multiple distributed knowledge bases.
  • Logic Puzzles (Sudoku): Used to demonstrate the power of user-defined learning functions.

Key Insights and Ideas

  • Pruning is Better than Checking: The "aha moment" is that you don't need a full model to know an external source will fail. By calling the source with a partial assignment, the solver can "learn" why a path is a dead end and backtrack immediately.
  • Gray Boxes over Black Boxes: While external sources are often treated as black boxes, even a little bit of meta-knowledge (like knowing that adding more facts to a query won't remove existing results—monotonicity) allows the solver to generalize a single failure into a massive rule that prunes thousands of future guesses.
  • SMT-like Architecture: The approach mirrors how Satisfiability Modulo Theories (SMT) solvers work, but tailored for the unique "stable model" semantics of ASP.

Key Results

The performance gains were often dramatic:

  • Set Partitioning: In cases where the old approach saw exponential growth in runtime, the EBL-enabled solver's runtime remained almost constant for the tested range.
  • Wine Ontology: The solver achieved speedups of up to 33x (averaging around 7x) and was able to solve instances that previously timed out.
  • Sudoku: Without EBL, the solver timed out because it was blindly guessing every cell. With user-defined learning rules that explained why a number placement was invalid, the solver finished in seconds.
  • Model Reduction: The number of "candidate" models that needed to be checked dropped significantly, often from thousands down to just a handful.

Limitations and Future Work

  • Manual Learning Functions: Currently, "informed" learning requires the developer to manually specify properties or write custom nogood-generation functions. The authors suggest a future "user-friendly language" to make this easier.
  • Heuristics for Lazy Evaluation: Calling an external source is expensive. The paper notes a trade-off: call it too often, and you waste time; call it too rarely, and you don't prune enough. Developing better heuristics for when to trigger an external call is a key area for future research.
  • Automatic Property Detection: Future work could involve the solver automatically detecting properties like monotonicity during runtime rather than relying on developer input.

Summary updated

Abstract

Answer Set Programming (ASP) is a well-known problem solving approach based on nonmonotonic logic programs and efficient solvers. To enable access to external information, hex-programs extend programs with external atoms, which allow for a bidirectional communication between the logic program and external sources of computation (e.g., description logic reasoners and Web resources). Current solvers evaluate hex-programs by a translation to ASP itself, in which values of external atoms are guessed and verified after the ordinary answer set computation. This elegant approach does not scale with the number of external accesses in general, in particular in presence of nondeterminism (which is instrumental for ASP). In this paper, we present a novel, native algorithm for evaluating hex-programs which uses learning techniques. In particular, we extend conflict-driven ASP solving techniques, which prevent the solver from running into the same conflict again, from ordinary to hex-programs. We show how to gain additional knowledge from external source evaluations and how to use it in a conflict-driven algorithm. We first target the uninformed case, i.e., when we have no extra information on external sources, and then extend our approach to the case where additional meta-information is available. Experiments show that learning from external sources can significantly decrease both the runtime and the number of considered candidate compatible sets.
BibTeX
@inproceedings{eiter2012conflict,
  author = {Thomas Eiter and Michael Fink and Thomas Krennwallner and Christoph Redl},
  title = {{Conflict-driven ASP solving with external sources}},
  booktitle = {Theory Pract. Log. Program},
  year = {2012},
  url = {https://openreview.net/forum?id=cgw35BoGKy},
}

Loading related content...

Figure