Plausibility Reasoning via Projected Answer Set Counting - A Hybrid Approach

Johannes Klaus Fichte, Markus Hecher, Mohamed A. NadeemIJCAI 2022 · DOI

TL;DR

This paper introduces "plausibility reasoning" as a more nuanced way to reason about logic programs, going beyond simple "yes/no" answers to quantify the likelihood of a query being true. They propose a novel hybrid approach that combines dynamic programming on tree decompositions with standard answer set solvers to efficiently compute this projected plausibility, outperforming existing systems on challenging instances.

What Problem Does This Paper Address?

Traditional Answer Set Programming (ASP) offers powerful declarative reasoning but is primarily focused on determining if a statement is true in at least one (brave) or all (cautious) possible solutions (answer sets) of a program. This binary approach is often insufficient when we need a more quantitative understanding, like "how likely is this statement to be true?" This is especially true when dealing with auxiliary atoms introduced for modeling convenience, which need to be "hidden" or "projected" out to focus on the atoms of interest. The paper addresses the challenge of efficiently computing this "plausibility" – the proportion of answer sets that satisfy a query, considering only a specific subset of atoms.

Methods

The core of the paper is a novel hybrid approach for computing projected plausibility. This approach leverages:

  • Projected Answer Set Counting (#PA): This is the fundamental problem of counting how many answer sets of a program, when projected onto a specific set of atoms (the projection set), result in a particular configuration.
  • Tree Decompositions (TDs): The authors use TDs of a program's "primal graph" (a graph representing atom dependencies) to enable dynamic programming. The width of the TD provides a bound on the complexity of the dynamic programming approach.
  • Dynamic Programming (DP) on TDs: A bottom-up DP algorithm is employed, processing nodes of the TD to build up solutions. This is efficient for problems with bounded treewidth.
  • Abstraction: To bridge the gap between DP and standard solvers, the authors introduce the concept of "abstraction." This involves selecting a subset of atoms (the abstraction set) to focus the DP on, while treating the remaining atoms as part of sub-programs solved by standard ASP solvers. This allows for a flexible trade-off between DP and brute-force search.
  • Hybrid Solver (HybPA): The algorithm combines these techniques. It first attempts to solve the problem directly. If the problem is too complex (e.g., high treewidth), it uses heuristics to choose an abstraction set and then applies DP on the TD of the projected primal graph, recursively calling itself for sub-problems.

Datasets

The paper evaluates their approach on two sets of instances:

  • S1: Instances from the ICCMA'17 competition (abstract argumentation).
  • S2: Prototypical ASP domain instances involving reachability and transitive closure on real-world transportation networks.

They also mention using randomly selected projection atoms for these datasets.

Key Insights and Ideas

  • Plausibility as a Generalization: Plausibility reasoning (quantifying the proportion of satisfying answer sets) offers a more nuanced view than just brave or cautious reasoning, acting as a middle ground.
  • The Challenge of Projection: Counting answer sets is already hard (#co-NP-complete), but projected answer set counting (#PA) is even more challenging (#Σ-complete), making efficient computation crucial.
  • Hybridization is Key: No single approach (pure DP or pure ASP solving) is sufficient for all instances. A hybrid strategy that intelligently combines DP on TDs with standard ASP solvers, guided by abstraction, is necessary for practical performance.
  • Abstraction as a Control Knob: The ability to choose an "abstraction set" provides a flexible mechanism to balance the computational effort between dynamic programming and standard ASP solving, allowing the system to adapt to different problem structures.

Key Results

  • Feasibility Confirmed (H1): The HybPA system successfully computes projected answer sets for a significant number of challenging instances, demonstrating the practical feasibility of projected plausibility reasoning.
  • Performance Gains (H2): HybPA consistently outperforms the standard ASP solver clingo on hard instances, particularly those with a large number of projected answer sets.
  • Specific Improvements: On set S1, HybPA solved more instances than clingo. On set S2, HybPA achieved a lower average runtime, indicating better performance. The scatter plot comparing HybPA and clingo on S2 clearly shows HybPA solving instances that clingo struggles with.

Limitations and Future Work

  • Computational Hardness: Projected answer set counting remains computationally very hard, and while HybPA improves performance, it still faces timeouts on extremely difficult instances.
  • Heuristics for Abstraction: The selection of abstraction sets is currently heuristic-based, and further research into more optimal abstraction strategies could yield further improvements.
  • Integration with ASP Solvers: The authors plan to more tightly integrate their method into existing ASP solvers, potentially enabling multi-shot extensions and learning across different tree decompositions.
  • Approximate Plausibility: For computationally intractable problems, exploring approximate variants of plausibility reasoning is suggested as a promising direction.

Summary updated

BibTeX
@inproceedings{fichte2022plausibility,
  author = {Johannes Klaus Fichte and Markus Hecher and Mohamed A. Nadeem},
  title = {{Plausibility Reasoning via Projected Answer Set Counting - A Hybrid Approach}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/363},
}
Figure