Simple Stochastic Temporal Constraint Networks

Many artificial intelligence tasks (e.g., planning, situation assessment, scheduling) require reasoning about events in time. Temporal constraint networks offer an elegant and often computationally efficient framework for such temporal reasoning tasks. Temporal data and knowledge available in some domains is necessarily imprecise - e.g., as a result of measurement errors associated with sensors. This paper introduces stochastic temporal constraint networks thereby extending constraint-based approaches to temporal reasoning with precise temporal knowledge to handle stochastic imprecision. The paper proposes an algorithm for inference of implicit stochastic temporal constraints from a given set of explicit constraints. It also introduces a stochastic version of the temporal constraint network consistency problem and describes techniques for solving it under certain simplifying assumptions