Changing times : an Iivestigation in probabilistic temporal reasoning

The world in which we live changes in uncertain ways. Building intelligent machines able to interact with the real world requires a theory of change. The required theory has to represent change and uncertain temporal evolutions at a minimal computational cost. The theory has to perform temporal projection to predict the effects of actions and events, as well as temporal explanation to interpret observed developments. Temporal projection and explanation are essential operations for planning, plan recognition, natural language understanding and diagnosis. The basic tasks of a temporal reasoner is to perform temporal projection and explanation. From a computational complexity viewpoint, performing these operations is very demanding. The complexity of temporal reasoning has prohibited its use in real-time applications. This dissertation presents an approach to uncertain temporal reasoning that is more efficient and therefore more practical. To achieve this efficiency, many basic issues in temporal reasoning arereexamined and new concepts are introduced. Dynamic probabilities change with time and are updated as events and actions take place. Some instances of temporal reasoning are reduced to atemporal reasoning using dynamic probabilities. Events and actions have functions specifying their effects on the dynamic probabilities. Since events may occur simultaneously, predicting the net effect of concurrent interacting events requires models describing common event interaction patterns. These models reduce the elicitation and reasoning complexity in the presence of interacting events. A degree of relevance measure helps in determining the portion of past event history relevant to the time period of interest. This notion is akin to the commonsense notion of forgetting. Surprise is another commonsense notion useful for belief revision in the probabilistic framework presented here. The present formalism integrates the above notions within a causal framework. This formalism is used in conjunction with Bayesian networks to perform probabilistic reasoning. We also use the formalism in conjunction with an abductive reasoning formalism to perform nonmonotonic reasoning using a changing rule base. Both systems are useful for applications in diagnosis, commonsense reasoning and planning as illustrated by examples