| 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 Brown 81 , to deal with time in an efficient and natural manner. The techniques presented here constitute a solute to the problem of updating a representation of the world changing over time as a consequence of various processes, otherwise known as the frame problem McCarthy 69 . These techniques subsume the functionality of current approaches to dealing with time in planning (e.g., Sacerdoti 77 , (Tate 77 , Vere 83 , and Allen 83 ).;Applications in robot problem solving are stressed, but examples drawn from other application areas are used to demonstrate the generality of the techniques. The issues involved in processing temporal queries, propagating metric constraints, noticing the invalidation of default assumptions, and reasoning with incomplete knowledge are discussed in conjunction with the presentation of algorithms. |
