Evidential Reasoning with Temporal Aspects

Thomas FallAAAI 1986

Abstract

In complex real-world environments, data often arrives as asynchronous "scraps" of evidence—varying in precision and certainty. This paper presents a framework for evidential reasoning that integrates temporal aspects by combining hierarchical state models with Gordon-Shortliffe theory. By utilizing frame-like models that enforce minimum and maximum residency times, the system can propagate uncertain evidence through time while maintaining consistency with historical data and avoiding common pitfalls of naive temporal reasoning.

Introduction

A significant challenge in artificial intelligence is making sense of uncertain data that arrives at different times. Traditional "naive" temporal reasoning often suffers from two major flaws. First, it is frequently inflexible regarding history; standard probability projections often ignore how long an object has already occupied a state. For instance, a taxi that has just entered a queue is unlikely to leave immediately, regardless of the general average wait time. Second, many evidence-combination methods, such as Dempster-Shafer, fall into a "dependency trap" by assuming pieces of evidence are independent. This can lead to overconfidence when multiple redundant reports are treated as unique data points.

Methodology

The proposed system is built upon four primary pillars designed to handle these complexities:

1. Activity Hierarchies

States are organized into a hierarchy ranging from general categories to specific activities. For example, a "Down Time" state might branch into "Garaged" or "On Break," while "Up Time" includes locations like "Uptown" or "Airport."

Figure 1: The activity hierarchy used in the taxi cab example, illustrating the decomposition of states from general to specific.

2. Gordon-Shortliffe Theory

The system utilizes an extension of Dempster-Shafer theory to combine evidence across these hierarchical "slots," allowing for the integration of vague but certain reports with precise but uncertain ones.

3. The "Model" Mechanism

The core innovation is the "model," a frame-like object representing a sequence of activities with defined minimum and maximum residency times. These models act as temporal anchors, enforcing logical constraints such as "if a vehicle is at the airport now, it must have spent at least 20 minutes in transit."

4. Temporal Propagation

When a new report arrives, it instantiates a model. The system uses residency constraints to "hatch out" possible future and past states. Subsequent reports do not merely add data points; they further constrain the timings of existing model instances.

Figure 2: An illustration of temporal propagation, where residency constraints define possible states (hatched areas) over time.

The engine was implemented in ZetaLisp on a Symbolics 3670 Lisp machine, ensuring computational feasibility for real-time applications.

Evaluation and Results

The system was evaluated using two primary datasets: a simulated "Taxi Cab Example" involving competing companies and a classified real-world vehicle identification domain featuring 30 states and 10 models.

Key findings include:

  • Expert Alignment: In a test with 50 reports, the system calculated a 64% likelihood for a specific candidate, closely matching human expert estimates of 60-70%.
  • Computational Efficiency: The implementation of a Global Rejection Value (GRV) was critical for performance. With a GRV of 0.01 (discarding evidence below a 1% threshold), reports were processed in 5 seconds. Without pruning, processing time ballooned to 10 minutes.
  • Stability and Robustness: The model-based approach proved stable; small input changes resulted in proportional output changes. Furthermore, the system demonstrated order independence, yielding the same results even when evidence was processed in reverse chronological order.

Discussion and Limitations

While effective, the system is sensitive to the definition of residency time parameters. Poorly defined min/max times can lead to the incorrect exclusion of valid states. Additionally, the current method for handling reports that match states with multiple parents in the hierarchy is somewhat ad-hoc and could benefit from more sophisticated knowledge-based functions. Finally, while the reasoning engine is domain-independent, the creation of specific models and hierarchies remains a knowledge-heavy process requiring significant expert input.

Conclusion

This research demonstrates that by anchoring evidential reasoning in temporal models with residency constraints, AI systems can more accurately interpret asynchronous and uncertain data. The framework successfully mitigates the dependency trap and provides a stable, expert-aligned method for complex state tracking.

Reference: Fall, T. C. (1986). Evidential Reasoning with Temporal Aspects. AAAI-86 Proceedings.

Summary updated

BibTeX
@inproceedings{fall1986evidential,
  author = {Thomas Fall},
  title = {{Evidential Reasoning with Temporal Aspects}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure