TL;DR
This paper introduces a novel technique for "conflict-driven learning" in Answer Set Programming (ASP) with external sources (HEX-programs). By identifying and propagating "inconsistency reasons" between program components, they achieve significant speedups, potentially exponential, overcoming bottlenecks in existing methods.
What Problem Does This Paper Address?
Answer Set Programming (ASP) is a powerful declarative reasoning paradigm. However, extending ASP with external sources (like databases or web services) via HEX-programs introduces challenges. Specifically, when these external sources can invent new values (domain expansion), the grounding process (preparing the program for solving) becomes computationally expensive, potentially requiring exponentially many evaluations.
Existing solutions include program splitting, which divides the program into components and processes them sequentially. This helps with grounding but creates a new bottleneck: it hinders "conflict-driven learning," a crucial technique for efficient solving where the system learns from encountered inconsistencies. This paper tackles the problem of having both efficient grounding and effective conflict-driven learning in HEX-programs.
Methods
The core contribution is a new technique for "conflict-driven learning over multiple program components." This involves:
- Inconsistency Reasons (IRs): Identifying specific sets of input facts that cause a program component to become inconsistent. This is done by analyzing the conflict-driven solver's internal state (implication graph) when an inconsistency is detected.
- Trans-Unit Propagation (tu-propagation): Once an IR is found for a component, it's translated into a constraint. This constraint is then "propagated back" to predecessor components. This allows earlier components to prune guesses that would inevitably lead to inconsistency in later components.
- Algorithm Extension: The authors adapt an existing conflict-driven HEX-program evaluation algorithm (HEX-CDNL) to incorporate this inconsistency analysis and propagation. They extend this to handle nonground programs by using partially optimized groundings.
Datasets
The paper evaluates their approach on two types of benchmarks:
- Configuration Problem: 10 randomly generated instances for each size, with varying numbers of domain elements, properties, and constraints.
- Diagnosis Problem: 10 randomly generated instances for each size, characterized by definite and potential observations.
They also use a synthetic benchmark designed to showcase the best-case performance of their approach. No new datasets were introduced; existing benchmarks were used to compare configurations.
Key Insights and Ideas
- Bridging the Gap: The most significant insight is that inconsistency analysis can effectively bridge the gap between program splitting (good for grounding) and conflict-driven learning (good for solving). By propagating learned inconsistency reasons, they retain the benefits of splitting without sacrificing solving efficiency.
- Early Pruning: Propagating constraints derived from inconsistency reasons to earlier program components allows for much earlier pruning of incorrect guesses. This is crucial for programs where guesses are separated from constraints by nonmonotonic external atoms.
- Beyond Single-Component Debugging: Unlike traditional ASP debugging, which focuses on explaining inconsistencies within a single program, this work addresses inconsistencies arising from interactions between program components.
Key Results
The experiments demonstrate a significant performance improvement for their tu-propagation approach compared to monolithic evaluation and standard program splitting.
- Configuration Problem: Tu-propagation consistently outperformed monolithic and splitting approaches across various instance sizes, with monolithic suffering from grounding bottlenecks and splitting from solving bottlenecks.
- Diagnosis Problem: Tu-propagation was again the fastest, especially as instance sizes grew. Monolithic evaluation was particularly slow due to expensive external source evaluations.
- Synthetic Benchmark: The tu-propagation approach showed exponential speedups, highlighting its effectiveness in scenarios where other methods struggle with the combinatorial explosion of guesses.
- Overall: The results suggest that tu-propagation can achieve significant, potentially exponential, speedups for the class of programs where guessing and checking are separated by nonmonotonic external atoms.
Limitations and Future Work
- Generalization of Nogood Propagation: The current work focuses on propagating reasons for inconsistency. Future work could explore generalizing this to propagate information from consistent program components.
- Solver Optimizations: The authors disabled some typical solver optimizations for tu-propagation to ensure soundness. Identifying which optimizations are compatible with their approach could lead to further improvements.
- Exploiting Structural Information: Future research could investigate how to use the program's structure to better restrict the set of atoms that might receive support from rules missing in the current grounding.
- Minimality of IRs: While the current method for computing IRs prioritizes speed over minimality, formalizing minimal IRs could be a direction for future work.
Summary updated