Conflict-driven ASP Solving with External Sources

Thomas Eiter, Michael Fink, Thomas Krennwallner, Christoph Redl

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:

  1. 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.
  2. 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 &diff external 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

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},
}
Figure