Local-to-Global Consistency Implies Tractability of Abduction

Authors

  • Michal Wrona Linkoping University

DOI:

https://doi.org/10.1609/aaai.v28i1.8861

Keywords:

Diagnosis and Abductive Reasoning, Spatial and Temporal Reasoning, Local Consistency, Computational Complexity

Abstract

Abduction is a form of nonmonotonic reasoning that looks for an explanation, built from a given set of hypotheses, for an observed manifestation according to some knowledge base. Following the concept behind the Schaefer's parametrization CSP(Gamma) of the Constraint Satisfaction Problem (CSP), we study here the complexity of the abduction problem Abduction(Gamma, Hyp, M) parametrized by certain (omega-categorical) infinite relational structures Gamma, Hyp, and M from which a knowledge base, hypotheses and a manifestation are built, respectively. We say that Gamma has local-to-global consistency if there is k such that establishing strong k-consistency on an instance of CSP(Gamma) yields a globally consistent (whose every solution may be obtained straightforwardly from partial solutions) set of constraints. In this case CSP(Gamma) is solvable in polynomial time. Our main contribution is an algorithm that under some natural conditions decides Abduction(Gamma, Hyp, M) in P when Gamma has local-to-global consistency. As we show in the number of examples, our approach offers an opportunity to consider abduction in the context of spatial and temporal reasoning (qualitative calculi such as Allen's interval algebra or RCC-5) and that our procedure solves some related abduction problems in polynomial time.

Downloads

Published

2014-06-21

How to Cite

Wrona, M. (2014). Local-to-Global Consistency Implies Tractability of Abduction. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.8861

Issue

Section

AAAI Technical Track: Knowledge Representation and Reasoning