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
&diffexternal 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