Local reasoning and knowledge compilation for efficient temporal abduction
- 10 December 2002
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 14 (6), 1230-1248
- https://doi.org/10.1109/tkde.2002.1047764
Abstract
Generating abductive explanations is the basis of several problem solving activities such as diagnosis, planning, and interpretation. Temporal abduction means generating explanations that do not only account for the presence of observations, but also for temporal information on them, based on temporal knowledge in the domain theory. We focus on the case where such a theory contains temporal constraints that are required to be consistent with temporal information on observations. Our aim is to propose efficient algorithms for computing temporal abductive explanations. Temporal constraints in the theory and in the observations can be used actively by an abductive reasoner in order to prune inconsistent candidate explanations at an early stage during their generation. However, checking temporal constraint satisfaction frequently generates some overhead. We analyze two incremental ways of making this process efficient. First we show how, using a specific class of temporal constraints (which is expressive enough for many applications), such an overhead can be reduced significantly, yet preserving a full pruning power. In general, the approach does not affect the asymptotic complexity of the problem, but it provides significant advantages in practical cases. We also show that, for some special classes of theories, the asymptotic complexity is also reduced. We then show how, compiled knowledge based on temporal information, can be used to further improve the computation, thus, extending to the temporal framework previous results in the case of atemporal abduction. The paper provides both analytic and experimental evaluations of the computational advantages provided by our approaches.Keywords
This publication has 24 references indexed in Scilit:
- Efficient Processing of Queries and Assertions about Qualitative and Quantitative Temporal ConstraintsComputational Intelligence, 1999
- A spectrum of definitions for temporal model-based diagnosisArtificial Intelligence, 1998
- An approach to the compilation of operational knowledge from casual modelsIEEE Transactions on Systems, Man, and Cybernetics, 1992
- On the Relationship Between Abduction and DeductionJournal of Logic and Computation, 1991
- A spectrum of logical definitions of model‐based diagnosis1Computational Intelligence, 1991
- The computational complexity of abductionArtificial Intelligence, 1991
- Temporal constraint networksArtificial Intelligence, 1991
- Explanation and prediction: an architecture for default and abductive reasoningComputational Intelligence, 1989
- Diagnosing multiple faultsArtificial Intelligence, 1987
- Theorist: A Logical Reasoning System for Defaults and DiagnosisPublished by Springer Science and Business Media LLC ,1987