Solving Epistemic Logic Programs Using Generate-and-Test with Propagation

Jorge Fandinno, Lute LilloAAAI 2025 · DOI

Abstract

Epistemic Logic Programs (ELPs) extend Answer Set Programming (ASP) to allow reasoning about knowledge and uncertainty. However, solving ELPs is computationally intensive, sitting at $\Sigma^P_3$-complete on the polynomial hierarchy. This paper presents a novel framework for solving ELPs that utilizes "epistemic propagation" within a generate-and-test approach. By incorporating logical consequences into the candidate generation phase ($G_1$), the proposed solver significantly prunes the search space. Experimental results demonstrate a ~3.3x speedup and a 91% increase in solved benchmark instances compared to previous state-of-the-art tools.

Introduction

Answer Set Programming (ASP) is a robust paradigm for solving complex search problems, yet it lacks the native ability to reason about "knowledge about knowledge." Epistemic Logic Programs (ELPs) address this by introducing subjective literals, which allow rules to check whether a system knows a fact or remains ignorant of it.

The primary challenge with ELPs is their computational complexity. Standard ASP is NP-complete, but ELP solving is two levels higher. Existing solvers typically rely on a "generate-and-test" methodology: a generator produces candidate solutions, which an expensive tester then validates. If the generator is "blind" to epistemic constraints, it produces a massive volume of invalid candidates, leading to significant performance bottlenecks.

Methodology: Epistemic Propagation

The core innovation of this work is a general framework for Generate-and-Test with Propagation. The researchers developed a sophisticated Generator Program ($G_1$) that moves logical reasoning from the testing phase into the generation phase.

  1. Normal Form Transformation: ELPs are first converted into a simplified normal form to streamline processing.
  2. Epistemic Propagation: Unlike traditional generators that merely guess solutions, $G_1$ uses rules to propagate the consequences of those guesses. For instance, if the solver assumes knowledge of fact $A$, and a rule dictates that knowing $A$ implies knowing $B$, the generator infers $B$ immediately.
  3. Search Space Pruning: By applying consistency constraints (e.g., preventing the system from simultaneously knowing and not knowing a fact), the generator can discard invalid branches of the search tree before they reach the costly testing phase.
  4. Implementation: This framework was implemented as an updated version of eclingo, leveraging the high-performance clingo ASP solver.

Experimental Evaluation

The solver was evaluated using an expanded benchmark suite of 326 instances, up from the original 58, to test the scalability of modern solvers. The benchmarks included:

  • Eligibility: Reasoning within disjunctive databases (145 instances).
  • Yale Shooting: A classic AI planning problem (7 instances).
  • Bomb in the Toilet: A conformant planning problem involving packages and hazards (174 instances).

Key Results and Insights

The $G_1$ generator represents a significant breakthrough in solver efficiency. The authors observed that while the testing phase is inherently difficult, making the generator "smarter" leads to an exponential reduction in candidates. In problems like "Bomb in the Toilet," this propagation prevents the exploration of $2^n$ invalid candidates with only a linear increase in generator complexity.

Cactus plot showing the number of instances solved over time, comparing the G1-based solver against other state-of-the-art epistemic logic solvers.

As shown in the performance data, the new solver dominated the competition:

  • Overall Performance: It solved 283 out of 326 instances, whereas the previous version of eclingo solved 148 and EP-ASP solved only 80.
  • Speed and Efficiency: The solver achieved a ~3.3x speedup over the best available alternatives. In the Eligibility benchmark, it was approximately 7.5x faster than its predecessor.
  • Benchmark Breakthroughs: On the "Bomb in the Toilet" problem, the new version solved 131 instances, a massive improvement over the 17 solved by the previous version.
Detailed performance metrics across various benchmarks, comparing the G1 and G0 generators against existing solvers like eclingo, EP-ASP, and selp.

Conclusion and Future Work

While the propagation framework offers a major leap in performance, some specialized solvers like EP-ASP^{se} still outperform it on specific planning tasks due to domain-specific heuristics. Future research will focus on integrating these heuristics into the general framework, exploring "splitting" techniques to break down large programs, and extending the propagation logic to other epistemic semantics such as K15 or C19.

Summary updated

BibTeX
@inproceedings{fandinno2025solving,
  author = {Jorge Fandinno and Lute Lillo},
  title = {{Solving Epistemic Logic Programs Using Generate-and-Test with Propagation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i14.33634},
}
Figure