Abstract
Answer Set Programming (ASP) is a powerful paradigm for declarative problem solving based on nonmonotonic logic programs. To extend its utility to real-world applications, HEX-programs were introduced, allowing bidirectional communication between logic programs and external sources such as description logic reasoners or Web resources. However, traditional solvers evaluate HEX-programs by translating them into standard ASP, a process that relies on a "guess-and-check" mechanism that often fails to scale. This paper presents a native, conflict-driven algorithm for evaluating HEX-programs. By extending conflict-driven nogood learning (CDNL) to accommodate external sources, the solver can learn from external evaluations during the search process. We demonstrate that this approach, particularly when augmented with meta-information about external sources, significantly reduces runtime and the number of candidate models explored.
Introduction
Answer Set Programming (ASP) has become a standard tool for solving complex combinatorial problems. Yet, its traditional closed-world nature makes it difficult to integrate with external data and specialized computational tools. HEX-programs bridge this gap by introducing external atoms, which allow a solver to query external sources.
Historically, the evaluation of HEX-programs relied on a translation-based approach. In this setup, the solver would guess the truth values of all external atoms, compute a model candidate, and only then verify these guesses against the actual external sources. This "blind guessing" creates a significant bottleneck, especially in the presence of nondeterminism, as the solver may repeatedly explore branches of the search space that are logically incompatible with the external source's behavior.
HEX-CDNL: Integrating External Learning
To address the scalability issues of the translation approach, we propose HEX-CDNL (Conflict-Driven Nogood Learning for HEX). This algorithm treats external sources as active participants in the search process. Instead of waiting for a complete model candidate, the solver interacts with external sources during the search, allowing it to prune the search space as soon as a partial assignment is found to be inconsistent.
External Behavior Learning (EBL)
The core of our approach is External Behavior Learning (EBL). When an external atom is evaluated, the solver does not merely receive a boolean result. Instead, it generates nogoods—sets of assignments that are logically impossible. These nogoods are integrated into the solver's knowledge base, preventing it from re-entering the same conflict state in future iterations. This mirrors the architecture of Satisfiability Modulo Theories (SMT) solvers but is specifically tailored for the stable model semantics of ASP.
Uninformed vs. Informed Learning
We distinguish between two levels of learning based on the available knowledge of the external source:
- Uninformed Learning: The solver learns basic input-output relationships. For example, if a specific set of inputs leads to a specific output, that relationship is recorded as a nogood.
- Informed Learning: If the developer provides meta-information (e.g., monotonicity, functionality, or anti-monotonicity), the solver can generate much more powerful, "shorter" nogoods. For instance, if an external source is known to be monotonic, the solver can infer that adding more facts to a query will not remove existing results, allowing it to prune significantly larger branches of the search tree.
Experimental Evaluation
We evaluated the HEX-CDNL approach across several benchmarks, comparing it against the traditional translation-based solver. The results demonstrate that learning from external sources can transform the performance profile of the solver.
- Set Partitioning: In synthetic benchmarks testing the
&diffexternal atom, the traditional approach exhibited exponential growth in runtime. In contrast, the EBL-enabled solver maintained almost constant runtime across the tested range. - Wine Ontology: Using a real-world-scale ontology to test classification under default rules, the solver achieved speedups of up to 33x, with an average improvement of 7x. It successfully solved instances that previously resulted in timeouts.
- Sudoku: To demonstrate the power of user-defined learning, we implemented a Sudoku solver where external atoms checked for valid number placements. Without EBL, the solver timed out due to the sheer number of guesses. With custom nogood-generation functions that explained why a placement was invalid, the solver reached a solution in seconds.
- Multi-Context Systems (MCS): The approach also proved effective in finding explanations for inconsistencies across distributed knowledge bases, significantly reducing the number of candidate models that required verification.
Discussion and Future Work
The transition from treating external sources as "black boxes" to "gray boxes"—where some internal properties are known—is key to the efficiency of HEX-CDNL. By leveraging even minimal meta-knowledge, the solver can generalize a single failure into a broad pruning rule.
However, several challenges remain. Currently, informed learning often requires manual specification of properties or custom nogood-generation functions. Future research will focus on developing a more user-friendly language for specifying these properties and exploring methods for the solver to automatically detect properties like monotonicity during runtime. Additionally, we aim to refine the heuristics for "lazy evaluation" to better balance the cost of calling an external source against the benefit of the knowledge gained.
Summary updated