On Computing World Views of Epistemic Logic Programs

Tran Cao Son, Tiep Le, Patrick Thor Kahl, Anthony P. Leclerc

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.

Performance comparison on Scholarship Eligibility (E) and Yale Shooting (Y) benchmarks.

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.

Performance comparison on 'Bomb in the Toilet' (BT) conformant planning benchmarks against DLV-K.

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

Abstract

This paper presents a novel algorithm for computing world views of different semantics of epistemic logic programs (ELP) and two of its realization, called Ep-asp (for an older semantics) and Ep-asp^{se} (for the newest semantics), whose implementation builds on the theoretical advancement in the study of ELPs and takes advantage of the multi-shot computation paradigm of the answer set solver Clingo. The new algorithm differs from the majority of earlier algorithms in its strategy. Specifically, it computes one world view at a time and utilizes properties of world views to reduce its search space. It starts by computing an answer set and then determines whether or not a world view containing this answer set exists. In addition, it allows for the computation to focus on world views satisfying certain properties. The paper includes an experimental analysis of the performance of the two solvers comparing against a recently developed solver. It also contains an analysis of their performance in goal directed computing against a logic programming based conformant planning system, dlv-k. It concludes with some final remarks and discussion on the future work.
BibTeX
@inproceedings{son2017computing,
  author = {Tran Cao Son and Tiep Le and Patrick Thor Kahl and Anthony P. Leclerc},
  title = {{On Computing World Views of Epistemic Logic Programs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/176},
}
Figure