Exploiting Partial Assignments for Efficient Evaluation of Answer Set Programs with External Source Access

Thomas Eiter, Tobias Kaminski, Christoph Redl, Antonius Weinzierl

Research output: Contribution to journalArticleScientificpeer-review

6 Citations (Scopus)
253 Downloads (Pure)

Abstract

Answer Set Programming (ASP) is a well-known declarative problem solving approach based on nonmonotonic logic programs, which has been successfully applied to a wide range of applications in artificial intelligence and beyond. To address the needs of modern applications, HEX-programs were introduced as an extension of ASP with external atoms for accessing information outside programs via an API style bi-directional interface mechanism. To evaluate such programs, conflict-driving learning algorithms for SAT and ASP solving have been extended in order to capture the semantics of external atoms. However, a drawback of the state-of-the-art approach is that external atoms are only evaluated under complete assignments (i.e., input to the external source) while in practice, their values often can be determined already based on partial assignments alone (i.e., from incomplete input to the external source). This prevents early backtracking in case of conflicts, and hinders more efficient evaluation of HEX-programs. We thus extend the notion of external atoms to allow for three-valued evaluation under partial assignments, while the two-valued semantics of the overall HEX-formalism remains unchanged. This paves the way for three enhancements: first, to evaluate external sources at any point during model search, which can trigger learning knowledge about the source behavior and/or early backtracking in the spirit of theory propagation in SAT modulo theories (SMT). Second, to optimize the knowledge learned in terms of so-called nogoods, which roughly speaking are impossible input-output configurations. Shrinking nogoods to their relevant input part leads to more effective search space pruning. And third, to make a necessary minimality check of candidate answer sets more efficient by exploiting early external evaluation calls. As this check usually accounts for a large share of the total runtime, optimization is here particularly important. We further present an experimental evaluation of an implementation of a novel HEX-algorithm that incorporates these enhancements using a benchmark suite. Our results demonstrate a clear efficiency gain over the state-of-the-art HEX-solver for the benchmarks, and provide insights regarding the most effective combinations of solver configurations.
Original languageEnglish
Pages (from-to)665-727
Number of pages63
JournalJournal of Artificial Intelligence Research
Volume62
DOIs
Publication statusPublished - 30 Jul 2018
MoE publication typeA1 Journal article-refereed

Fingerprint

Dive into the research topics of 'Exploiting Partial Assignments for Efficient Evaluation of Answer Set Programs with External Source Access'. Together they form a unique fingerprint.

Cite this