grASP: A Graph Based ASP-Solver and Justification System. (arXiv:2104.01190v1 [cs.AI])

Answer set programming (ASP) is a popular nonmonotonic-logic based paradigm
for knowledge representation and solving combinatorial problems. Computing the
answer set of an ASP program is NP-hard in general, and researchers have been
investing significant effort to speed it up. The majority of current ASP
solvers employ SAT solver-like technology to find these answer sets. As a
result, justification for why a literal is in the answer set is hard to
produce. There are dependency graph based approaches to find answer sets, but
due to the representational limitations of dependency graphs, such approaches
are limited. We propose a novel dependency graph-based approach for finding
answer sets in which conjunction of goals is explicitly represented as a node
which allows arbitrary answer set programs to be uniformly represented. Our
representation preserves causal relationships allowing for justification for
each literal in the answer set to be elegantly found. Performance results from
an implementation are also reported. Our work paves the way for computing
answer sets without grounding a program.



Related post