Advancing Lazy-Grounding ASP Solving Techniques – Restarts, Phase Saving, Heuristics, and More

DOI10.1017/S1471068420000332zbMATH Open1468.68228arXiv2008.03526OpenAlexW3088670598MaRDI QIDQ5140003FDOQ5140003

Richard Taupe, Gerhard Friedrich, Antonius Weinzierl

Publication date: 13 December 2020

Published in: Theory and Practice of Logic Programming (Search for Journal in Brave)

Abstract: Answer-Set Programming (ASP) is a powerful and expressive knowledge representation paradigm with a significant number of applications in logic-based AI. The traditional ground-and-solve approach, however, requires ASP programs to be grounded upfront and thus suffers from the so-called grounding bottleneck (i.e., ASP programs easily exhaust all available memory and thus become unsolvable). As a remedy, lazy-grounding ASP solvers have been developed, but many state-of-the-art techniques for grounded ASP solving have not been available to them yet. In this work we present, for the first time, adaptions to the lazy-grounding setting for many important techniques, like restarts, phase saving, domain-independent heuristics, and learned-clause deletion. Furthermore, we investigate their effects and in general observe a large improvement in solving capabilities and also uncover negative effects in certain cases, indicating the need for portfolio solving as known from other solvers. Under consideration for acceptance in TPLP.

Full work available at URL: https://arxiv.org/abs/2008.03526

zbMATH Keywords

knowledge representationanswer-set programmingsolving techniqueslazy-grounding

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Knowledge representation (68T30) Logic programming (68N17)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Theory and Applications of Satisfiability Testing
• BerkMin: A fast and robust SAT-solver
• GASP: Answer Set Programming with Lazy Grounding
• The ASP system DLV2
• The DLV system for knowledge representation and reasoning
• Semantics and complexity of recursive aggregates in answer set programming
• Optimization Methods for the Partner Units Problem
• Conflict-driven answer set solving: from theory to practice
• Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
• Optimal speedup of Las Vegas algorithms
• Lazy Model Expansion: Interleaving Grounding with Search
• Design and results of the Fifth Answer Set Programming Competition
• Train scheduling with hybrid ASP
• Blending lazy-grounding and CDNL search for answer-set solving
• Partial Compilation of ASP Programs
• \textit{telingo} = ASP + time
• Degrees of laziness in grounding. Effects of lazy-grounding strategies on ASP solving
• On the complexity of the partner units decision problem
• ASPeRiX, a first-order forward chaining approach for answer set computing

Cited In (1)

• Title not available (Why is that?)

Uses Software

• MiniSat
• Gringo
• Chaff
• BerkMin
• GASP
• WASP
• Clingo
• OMiGA
• DLV2

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• GASP: Answer Set Programming with Lazy Grounding 👍 👎
• AI*IA 2005: Advances in Artificial Intelligence 👍 👎
• An abstract view on optimizations in SAT and ASP 👍 👎
• Efficiently Coupling the I-DLV Grounder with ASP Solvers 👍 👎
• Lazy Clause Generation: Combining the Power of SAT and CP (and MIP?) Solving 👍 👎
• Degrees of laziness in grounding. Effects of lazy-grounding strategies on ASP solving 👍 👎

This page was built for publication: Advancing Lazy-Grounding ASP Solving Techniques – Restarts, Phase Saving, Heuristics, and More

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5140003)