Local reasoning and knowledge compilation for efficient temporal abduction

Risultato della ricerca: Contributo su rivistaArticolo in rivistapeer review

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. The aim of this paper 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. In the paper, 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.

Lingua originaleInglese
pagine (da-a)1230-1248
Numero di pagine19
RivistaIEEE Transactions on Knowledge and Data Engineering
Volume14
Numero di pubblicazione6
DOI
Stato di pubblicazionePubblicato - nov 2002

Fingerprint

Entra nei temi di ricerca di 'Local reasoning and knowledge compilation for efficient temporal abduction'. Insieme formano una fingerprint unica.

Cita questo