Temporal imagery: an approach to reasoning about time for planning and problem solving

Abstract

Reasoning about time typically involves drawing conclusions on the basis of incomplete information. Uncertainty arises in the form of ignorance, indeterminacy, and indecision. Despite the lack of complete information a problem solver is continually forced to make predictions in order to pursue hypotheses and plan for the future. Such predictions are frequently contravened by subsequent evidence. This dissertation presents a computational approach to temporal reasoning that directly confronts these issues. The approach centers around techniques for managing a data base of assertions corresponding to the occurrence of events and the persistence of their effects over time. The resulting computational framework performs the temporal analog of (static) reason maintenance (Doyle 79) by keeping track of dependency information involving assumptions about the truth of facts spanning various intervals of time. The system developed in this dissertation extends classical predicate-calculus data bases, such as those used by Prolog (Bowen 81), to deal with time in an efficient and natural manner. Applications in robot problem solving are stressed, but examples drawn from other applications areas are used to demonstrate the generality of the techniques.