Single-Shot Epistemic Logic Program Solving

Manuel Bichler, Michael Morak, Stefan WoltranIJCAI 2018 · DOI

TL;DR

This paper introduces a novel method to solve Epistemic Logic Programs (ELPs) by translating them into a single, non-ground Answer Set Program (ASP). This approach allows existing ASP solvers to handle ELPs efficiently in one go, overcoming the multi-call limitations of previous methods and demonstrating competitive performance on benchmark instances.

What Problem Does This Paper Address?

Epistemic Logic Programs (ELPs) extend Answer Set Programming (ASP) by introducing epistemic operators, allowing for reasoning about multiple possible worlds (answer sets). This meta-reasoning capability makes ELPs more expressive but also computationally more challenging. Traditional ELP solvers typically rely on making multiple calls to an ASP solver to evaluate an ELP. This multi-call approach can be inefficient and may lead to a loss of learned information within the ASP solver. The paper addresses the need for a more direct and efficient way to solve ELPs, specifically by enabling their evaluation with a single call to an ASP system.

Methods

The core contribution is a novel translation from ELPs to non-ground ASP programs with bounded predicate arity. This translation is designed to be solved in a "single shot" by an ASP solver. The translation process involves several key components:

  • Guessing Epistemic Literals: A part of the translated program guesses a set of epistemic literals, representing a potential "world view" for the ELP.
  • Checking Conditions: The program then includes checks to verify if this guessed world view satisfies the conditions of a candidate world view as defined by Shen and Eiter's semantics. These checks are broken down into three sub-programs:
  • Π'check1: Ensures that the guessed world view is a valid answer set of the ELP's epistemic reduct.
  • Π'check2: Verifies that for each epistemic literal not l in the guess, there exists at least one answer set where l is false.
  • Π'check3: Guarantees that for epistemic literals not l not in the guess, l is true in all answer sets.
  • Large Non-Ground Rules: The translation heavily relies on large, non-ground ASP rules. To handle these efficiently, the paper leverages a rule decomposition tool (lpopt) that splits large rules into smaller ones based on treewidth decomposition. This is crucial for practical grounding.
  • Preserving Treewidth: A key aspect of the practical implementation is carefully constructing the translation to preserve the treewidth of the original ELP's structure, ensuring that the decomposition tool remains effective.

Datasets

The paper evaluates their system, selp, on three types of benchmark instances:

  • Scholarship Eligibility (SE): A set of non-ground ELP programs from the ELP literature, encoding the scholarship eligibility problem for varying numbers of students.
  • Yale Shooting (YS): A set of non-ground ELP programs encoding a simplified version of the Yale Shooting Problem, a conformant planning problem.
  • Tree QBFs (TQ): Instances derived from certain Quantified Boolean Formulas (QBFs) with three quantifier blocks, known to have low treewidth structures. These are based on the 14 "Tree" instances from QBFEVAL'16.

Key Insights and Ideas

  • Single-Shot Solving is Achievable: The most significant insight is that ELP consistency can be directly mapped to ASP consistency using a single, albeit complex, non-ground ASP program. This bypasses the need for iterative calls to an ASP solver.
  • Leveraging Non-Ground ASP: The translation effectively utilizes the power of non-ground ASP rules, which, when combined with techniques like treewidth decomposition, can represent complex logical relationships concisely.
  • Treewidth Matters for Performance: The paper highlights that the efficiency of their approach, particularly when dealing with large rules, is heavily dependent on the treewidth of the underlying problem structure. Problems with low treewidth are handled much more effectively.
  • Flexibility of the Encoding: The proposed encoding is presented as flexible, adaptable to different ASP semantics and capable of handling more complex reasoning tasks.

Key Results

The paper's prototype system, selp, was compared against the state-of-the-art ELP solver EP-ASP.

  • Scholarship Eligibility (SE): selp solved all instances within 30 seconds, while EP-ASP timed out on many instances (only solving 17 within 8 hours).
  • Yale Shooting (YS): EP-ASP outperformed selp on these instances, solving 17 within 30 minutes compared to selp's 6 instances.
  • Tree QBFs (TQ): selp solved 6 out of 14 instances within 12 hours, whereas EP-ASP was unable to solve any.

These results indicate that selp is highly competitive on well-structured problems (low treewidth), while EP-ASP performs better on instances with higher treewidth.

Limitations and Future Work

  • Treewidth Dependence: The paper acknowledges that selp is most suited for ELPs of low treewidth. Instances with high treewidth (e.g., those with large clique structures) are not handled as efficiently.
  • Practical Performance on High Treewidth: While the translation is theoretically optimal, practical performance on high-treewidth instances can still be challenging due to the complexity of grounding large rules, even with decomposition.
  • Future Work:
    • Developing a combined solver that intelligently chooses between selp and another state-of-the-art solver based on the input's treewidth.
  • Exploring the encoding for other ASP semantics beyond the FLP semantics used.
  • Investigating the use of advanced ASP solver features (like optimization) for more complex ELP reasoning tasks, such as checking atom truth in all subset-maximal guesses.

Summary updated

BibTeX
@inproceedings{bichler2018single,
  author = {Manuel Bichler and Michael Morak and Stefan Woltran},
  title = {{Single-Shot Epistemic Logic Program Solving}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/237},
}

Loading related content...

Figure