Query Answering in Propositional Circumscription

Mario AlvianoIJCAI 2018 · DOI

TL;DR

This paper introduces new algorithms for efficiently answering queries in propositional circumscription, a logic that prioritizes "minimal" models. The proposed methods avoid computing full optimal models, instead focusing on finding models that satisfy the query and ruling out counterexamples, leading to potentially faster query answering.

What Problem Does This Paper Address?

Propositional circumscription is a powerful non-monotonic reasoning formalism that allows us to express preferences over possible interpretations (models) of a logical theory. This is useful for modeling real-world scenarios where we want to find "best" solutions, like diagnosing faults or determining acceptable arguments. However, answering queries about these preferred models (e.g., "Does there exist a preferred model where property X holds?") can be computationally expensive, often falling into higher complexity classes of the polynomial hierarchy. Existing approaches often rely on finding all optimal models, which can be prohibitive. This paper aims to develop more efficient algorithms for query answering in this setting, specifically by avoiding the full computation of optimal models.

Methods

The core of the paper presents two main algorithms for query answering in propositional circumscription.

  • Complete Algorithm (Algorithm 1): This algorithm iteratively searches for a model that satisfies the query (q). If such a model I is found, it then checks if there exists a "countermodel" I' that is more preferred (or equally preferred) but does not satisfy the query. If a countermodel is found, the search space is pruned by adding a blocking clause that prevents finding similar countermodels in the future. This process continues until either a model satisfying the query is found and no countermodel exists, or all possibilities are exhausted. A key aspect is that neither the found model nor the countermodel needs to be an optimal model itself. The algorithm leverages two SAT solvers: one to find models satisfying the query and another to find countermodels.
  • Incomplete Algorithm (Algorithm 4): This is a heuristic approach that aims to provide a "YES" answer more quickly, but without guaranteeing a "NO" answer if it fails. It checks if there's a subset of objective literals that, when added to the theory and the query, leads to an unsatisfiable formula. If such a subset is found, it implies the existence of an optimal model satisfying the query. This algorithm is faster but might not find an answer if one exists.

The paper also discusses simplified versions of the complete algorithm (Algorithm 2 and 3) that exploit specific properties of the query or objective literals.

Datasets

The algorithms were tested on instances from the 2nd International Competition on Computational Models of Argumentation (ICCMA'17). These instances represent problems related to credulous and skeptical acceptance of arguments under preferred and semi-stable semantics. The paper does not introduce new datasets.

Key Insights and Ideas

  • Avoiding Full Optimality: The most significant insight is that answering whether a circumscribed model satisfies a query doesn't necessarily require finding the optimal model. By focusing on finding a query-satisfying model and then efficiently ruling out more preferred counterexamples, the problem can be tackled more directly.
  • Blocking Clauses for Pruning: The use of blocking clauses derived from countermodels is a clever way to prune the search space. These clauses effectively guide the SAT solver away from regions of the search space that are known not to contain a solution.
  • SAT Solver Synergy: The algorithms are designed to work with off-the-shelf SAT solvers, making them practical to implement. The interplay between two SAT solvers (one for finding models, one for countermodels) is crucial.
  • Trade-off between Completeness and Speed: The introduction of an incomplete algorithm highlights the common trade-off in AI: sacrificing completeness for potential speedups. This heuristic can be useful when a quick "yes" is sufficient.

Key Results

  • The complete algorithm (Algorithm 1), when implemented in the solver PYGLAF, outperformed existing systems like ARGSEMSAT and CEGARTIX on ICCMA'17 benchmark instances, solving significantly more instances within the given time and memory limits.
  • The incomplete algorithm, when combined with the complete algorithm, sometimes deteriorated performance, particularly for skeptical acceptance problems. This suggests that the incomplete algorithm is best used as a heuristic, possibly with further restrictions.
  • The paper demonstrates that the proposed algorithms can be effectively applied to argumentation semantics (preferred and semi-stable), mapping argumentation problems to query answering in circumscription.

Limitations and Future Work

  • Incomplete Algorithm's Performance: The authors note that the incomplete algorithm can sometimes hinder performance, suggesting it should be used cautiously or with further restrictions, perhaps as a heuristic with a budget on conflicts.
  • Heuristic Development: Developing a more refined heuristic strategy for limiting the execution of the incomplete algorithm is identified as future work.
  • Complexity: While the algorithms aim to improve efficiency, the underlying problem of query answering in propositional circumscription remains computationally challenging. The paper doesn't claim to solve the inherent complexity but rather to provide practical algorithmic improvements.

Summary updated

BibTeX
@inproceedings{alviano2018query,
  author = {Mario Alviano},
  title = {{Query Answering in Propositional Circumscription}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/231},
}
Figure