Probabilistic Temporal Reasoning

Thomas L. Dean, Keiji KanazawaAAAI 1988

Abstract

Traditional artificial intelligence models often rely on the "law of inertia," assuming states persist indefinitely until an explicit event causes a change. This paper proposes a transition toward a probabilistic understanding of time. By integrating survivor functions, causal dependency graphs, and the Maximum Entropy principle, the authors develop a framework capable of reasoning about persistence and change under conditions of imperfect knowledge and incomplete observations.

Introduction: The Projection Problem

In classical AI, the "Law of Inertia" posits that a proposition remains true until an event explicitly makes it false. While logically elegant, this approach struggles with real-world scenarios where knowledge is imperfect. For instance, if an agent leaves an object in a specific location, the law of inertia suggests it remains there forever unless a theft is observed. This failure to account for unobserved changes is known as the Projection Problem: how can an agent predict the future state of the world when it lacks a complete predictive model and perfect observations?

Dean and Kanazawa argue that reasoning about the future requires more than just logic; it requires a model of "natural attrition"—the reality that states may change due to spontaneous or unobserved factors. They propose a framework for probabilistic temporal reasoning that replaces rigid persistence with decaying expectations.

Methodology

The authors propose a multi-layered approach to handle temporal uncertainty:

1. Survivor Functions

Borrowing from queuing theory, the model represents the persistence of a "fluent" (a time-varying state) using a decay function. An exponential decay, $e^{-\lambda \Delta}$, represents the probability that a state persists over an interval $\Delta$. This allows the system to reason that a state is likely to hold shortly after it was observed but becomes increasingly unlikely as time passes without re-verification.

2. Causal Dependency Graphs

To manage the propagation of evidence, the authors utilize causal dependency graphs. These graphs represent propositions and events over a discrete time grid, allowing for both forward-looking prediction and backward-looking explanation.

Causal dependency graph representing propositions and events over a discrete time grid.

In this structure, evidence at one time point can influence the probability of states at other points. For example, knowing a complex assembly is complete at time $T1$ provides probabilistic evidence that the necessary components were available at $T0$. This bi-directional reasoning is a core strength of the dependency graph approach.

3. Maximum Entropy Principle

When a problem is underconstrained—meaning multiple probability distributions could explain the known facts—the authors apply the Maximum Entropy principle. By using the calculus of variations, they identify the distribution that makes the fewest additional assumptions, resulting in a belief measure ($BEL'$) that serves as an unbiased estimate of likelihood.

Key Results

The framework was evaluated using a "toy domain" simulation of a factory environment involving tool displacement and assembly tasks. The authors compared two belief measures: $BEL$, a conservative measure acting as a greatest lower bound, and $BEL'$, the measure derived from the Maximum Entropy distribution.

Comparison of belief measures BEL and BEL' in the factory domain simulation.

As shown in the results table, $BEL'$ consistently provided higher and more realistic estimates of success in the factory domain. In scenarios where tools might have been displaced (Example 4), $BEL'$ captured the nuanced likelihood of success (14.17%) that the more rigid $BEL$ measure underestimated (10.80%).

Discussion and Future Work

While the proposed framework offers a significant advancement over non-probabilistic models, the authors identify several challenges. The computational complexity of the probability space grows exponentially with the number of propositions, making exact calculations difficult for large-scale applications. Additionally, the initial model relies on independence assumptions between events that may not always hold in complex causal chains. Future research directions include the use of stochastic relaxation techniques, such as Gibbs sampling, to approximate these probabilities more efficiently without exhaustive state calculation.

Summary updated

BibTeX
@inproceedings{dean1988probabilistic,
  author = {Thomas L. Dean and Keiji Kanazawa},
  title = {{Probabilistic Temporal Reasoning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure