Introduction
Epistemic Logic Programs (ELP) extend traditional Answer Set Programming (ASP) by incorporating introspective reasoning. While standard ASP determines what is true, ELPs allow an agent to reason about its own knowledge ($K$) and possibilities ($M$). This capability is crucial for applications like security protocols or reasoning under uncertainty. However, the computational cost of finding "world views"—the collections of answer sets representing an agent's beliefs—has historically limited ELPs to small-scale problems due to the combinatorial explosion inherent in traditional "guess-and-check" algorithms.
The EP-ASP Solver
This research introduces EP-ASP and EP-ASP$^{se}$, high-performance solvers designed to make ELPs practical. Unlike previous tools that treat ASP solvers as black boxes, EP-ASP leverages the multi-shot computation paradigm of the CLINGO solver. This allows for incremental program modification and aggressive pruning of the search space without restarting the entire solving process.
Key technical innovations include:
- Tight Solver Integration: Utilizing CLINGO's internal state to avoid redundant computations.
- Candidate Verification: Using skeptical and credulous entailment checks to invalidate candidate world views early in the search process.
- Goal-Directed Computing: Focusing computation on world views that satisfy specific objectives, which is essential for tasks like conformant planning.
Experimental Evaluation
The solvers were evaluated against state-of-the-art tools like ELPsolve and specialized planners like DLV-K across several benchmark sets, including Scholarship Eligibility (E-XX), Yale Shooting (Y-XX), and "Bomb in the Toilet" (BT) planning problems.
Reasoning and Scalability
On the Scholarship Eligibility and Yale Shooting benchmarks, the EP-ASP solvers demonstrated significant performance gains. As shown in the data, the new approach often achieves order-of-magnitude speedups. For instance, in problem E-24, the previous state-of-the-art ELPsolve ($E^+$) took approximately 955 seconds, while EP-ASP ($S_1$) completed the task in under 90 seconds.
Conformant Planning Performance
In "Bomb in the Toilet" planning tasks, EP-ASP proved highly competitive with DLV-K, a specialized system for planning. In complex variations like BTUC, the EP-ASP solvers were able to find solutions significantly faster and solve larger instances where DLV-K reached its limits.
Conclusion
The EP-ASP solvers represent a major step toward making epistemic reasoning a viable tool for real-world AI. By moving beyond simple guess-and-check methods and integrating deeply with modern ASP solvers, the authors have bridged the gap between theoretical introspection and practical performance. Future work will focus on automating heuristics and expanding goal-directed search to include "not knowing" constraints, opening new possibilities for security and privacy reasoning.
Summary updated