An efficient algorithm for temporal abduction

In this paper, we consider the following form of temporal abduction: given a domain theory where each explanatory formula is augmented with a set of temporal constraints on the atoms occurring in the formula, and given a set of observed atoms, with associated temporal constraints, the goal is the generation of a temporally consistent abductive explanation of the observations. Temporal abduction is the basis of many problem solving activities such as temporal diagnosis or reasoning about actions and events. This paper presents an e cient nondeterministic algorithm for temporal abduction which exploits the STP framework [8] in order to represent temporal information. In particular, we exploited some properties of STP, proved in [3], which allow us to e ciently prune temporally inconsistent candidate explanations as soon as possible. The pruning is achieved by interleaving abductive steps with temporal reasoning localized to the constraints on the formula used at each abductive step. The paper discusses the properties of the algorithm, providing both analytical and experimental evaluations of its performance