grASP: A Graph Based ASP-Solver and Justification System
This addresses the challenge for researchers and practitioners in knowledge representation and combinatorial problem-solving by providing a method that allows justification without grounding, though it appears incremental as it builds on existing dependency graph approaches.
The paper tackles the problem of efficiently computing answer sets in answer set programming (ASP), which is NP-hard, by proposing a novel graph-based approach that explicitly represents conjunction of goals as nodes, enabling uniform representation and elegant justification for literals, with performance results reported.
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.