Evaluating Epistemic Logic Programs via Answer Set Programming with Quantifiers

Wolfgang Faber, Michael MorakAAAI 2023 · DOI

Introduction

Epistemic Logic Programs (ELPs) extend standard Answer Set Programming (ASP) by introducing epistemic operators such as K ("known to be true") and M ("possibly true"). These operators allow for sophisticated reasoning about knowledge and uncertainty, such as the "presumption of innocence" rule: innocent(X) :- not K guilty(X). However, the computational complexity of ELPs is high, with the problem of deciding the existence of a "world view" being $\Sigma^P_3$-complete. Traditional solvers typically employ procedural loops that call standard ASP solvers multiple times. This paper explores a declarative alternative: translating ELPs into Answer Set Programming with Quantifiers (ASP(Q)).

Methodology

The authors propose a three-step rewriting process to transform an ELP into an ASP(Q) program. ASP(Q) is an extension of ASP that supports explicit existential ($\exists$) and universal ($\forall$) quantification over answer sets. The rewriting involves:

  1. Guessing: An existential quantifier block guesses truth values for epistemic literals.
  2. Verification of Existence: A block ensures the resulting program reduct has at least one valid answer set.
  3. Verification of Consistency: Universal and existential blocks verify that the initial guesses align with the actual answer sets (e.g., if K guilty was guessed true, guilty must be true in all answer sets).

This approach results in a quantified program structure ($\exists \dots \forall \dots : C$) that is only polynomially larger than the original ELP, allowing for native handling of complex quantifications.

Experimental Evaluation

The proposed tool, elp2qasp, was evaluated against state-of-the-art solvers like EP-ASP and selp on several benchmarks.

Scholarship Eligibility

On this non-ground ELP benchmark involving up to 25 students, the elp2qasp approach using the q_asp backend demonstrated highly competitive performance. While some solvers like EP-ASP showed exponential runtime growth as the number of students increased, the QBF-based q_asp maintained low runtimes, completing all tasks within 13 seconds.

Figure 1: Runtime comparison on the Scholarship Eligibility benchmark showing the stability of q_asp compared to EP-ASP.

Yale Shooting Problem

This classic conformant planning problem highlights the strengths of the declarative rewriting approach. Existing solvers often struggled with these instances, whereas the elp2qasp + q_asp combination solved all instances efficiently, remaining under 70 seconds while others experienced significant performance spikes.

Figure 2: Runtime comparison on the Yale Shooting Problem instances, highlighting the efficiency of the q_asp backend.

Key Insights and Results

The experiments reveal that ASP(Q) is a natural target for ELPs due to the direct mapping of epistemic semantics to quantifiers. By leveraging q_asp, which utilizes an underlying QBF solver, the authors tapped into advanced optimizations from the QBF community. The declarative "rewriting" approach allows the underlying engine to perform more global optimizations compared to procedural "looping" solvers.

Limitations and Future Work

Despite its success, the current implementation has limitations. The q_asp backend requires programs to be head-cycle free, which prevented it from solving the Tree QBF benchmark—a task where selp still excels. Additionally, the current rewriting does not yet support "knowledge minimization" semantics, though this is a planned extension. Future work will also involve adapting the tool for a broader range of ELP semantics proposed in recent years.

Conclusion

Lifting complex logic problems into quantified frameworks like ASP(Q) offers a powerful, declarative path for automated reasoning. By utilizing QBF-based backends, researchers can achieve significant performance gains on high-complexity tasks like conformant planning, demonstrating that this is a highly viable path for building next-generation reasoning tools.

Summary updated

BibTeX
@inproceedings{faber2023evaluating,
  author = {Wolfgang Faber and Michael Morak},
  title = {{Evaluating Epistemic Logic Programs via Answer Set Programming with Quantifiers}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i5.25778},
}
Figure