Doing Time: Putting Qualitative Reasoning on Firmer Ground

Brian C. WilliamsAAAI 1986

TL;DR

This paper introduces a novel Temporal Constraint Propagator (TCP) that significantly improves qualitative reasoning about dynamic physical systems. By cleanly separating temporal principles from qualitative representations and using "concise histories" to represent behavior, TCP overcomes limitations in existing systems, enabling more robust prediction, explanation, and diagnosis of complex behaviors, including those with feedback.

What Problem Does This Paper Address?

Predicting the behavior of dynamic physical systems is crucial for intelligent agents interacting with the world. While qualitative reasoning has made strides in this area, existing methods struggle with temporal aspects. They often force unnecessary temporal distinctions, over-restrict temporal descriptions, perform weak temporal inference, and construct incomplete justifications. This makes them difficult to apply to large, complex systems and limits their utility for tasks like diagnosis and design. The paper aims to provide a more general and robust framework for qualitative temporal reasoning.

Methods

The core contribution is the Temporal Constraint Propagator (TCP). Key aspects of TCP include:

  • Clean Separation: Principles related to time, continuity, and qualitative representations are kept distinct. This modularity allows for easier extension and adaptation.
  • Concise Histories: Instead of state-based representations, TCP describes a system's behavior using "concise histories." A history is a sequence of "episodes," where each episode represents an interval of uniform behavior for a state variable. "Concise" means each episode is maximal, covering the longest possible contiguous interval for that value, thus suppressing irrelevant temporal distinctions.
  • Temporal Constraint Propagation: This is the inference mechanism. It operates on episodes (values over time intervals) rather than just values. Rules are functions parameterized by time. New episodes are deduced by applying rules to input episodes, with the new episode's extent being the intersection of its inputs' extents.
  • Time Box: A dedicated module that handles temporal reasoning. It answers questions about episode extents and temporal relations, allowing for symbolic manipulation of time points and inequalities. This separation of temporal inference is key to the system's generality.
  • Justification Histories: In addition to value histories, TCP maintains justification histories that record why a particular value was deduced, including the specific rule and input episodes used. This is crucial for explanation and diagnosis.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and demonstrates its application with a qualitative example of a harmonic oscillator.

Key Insights and Ideas

  • The Power of Conciseness: Representing behavior with "concise histories" is a critical insight. By only recording maximal intervals of uniform behavior, the system avoids the combinatorial explosion and irrelevant distinctions that plague state-based approaches.
  • Separation of Concerns: Decoupling temporal reasoning (handled by the "Time Box") from the core qualitative reasoning engine makes the system more flexible and extensible. Different temporal representations can be plugged in without altering the fundamental propagation mechanism.
  • Justifications as First-Class Citizens: Explicitly tracking why a prediction is made (via justification histories) is essential for higher-level reasoning tasks like explanation and diagnosis, going beyond simple simulation.
  • Handling Feedback: The framework is designed to handle feedback loops, a notoriously difficult problem for temporal reasoning systems, by allowing propagation to occur even when an episode's full extent isn't yet determined.

Key Results

The paper presents a theoretical framework and a qualitative demonstration.

  • Qualitative Example: The paper walks through the qualitative reasoning process for a harmonic oscillator, showing how TCP can predict its behavior (position, velocity, acceleration) based on physical laws and continuity principles.
  • Generality: The approach is claimed to be applicable to a wide class of physical systems (discrete or continuous) and various representations (digital, quantitative, qualitative, symbolic).
  • Improved Reasoning: TCP overcomes specific limitations of prior systems, including handling time-varying inputs, reasoning about durations and delays, and constructing more complete justifications.

Limitations and Future Work

  • Completeness: TCP inherits the limitation of local constraint propagators in that it is not a complete constraint satisfaction system. Techniques exist to address this, depending on the value representation.
  • Implementation Status: A prototype was implemented in 1984, using a "Quantity Lattice" as the time box. A second time box incorporating disjunction was being developed.
  • Future Directions:
    • Augmenting TCP to perform "envisionment" (generating a qualitative model from structure) as well as simulation.
  • Incorporating techniques for abstracting or approximating constraints.
  • Developing a more robust control strategy for guiding the propagation process.
  • Further exploration of temporal reasoning for feedback systems and handling disjunctions in the time box.

Summary updated

BibTeX
@inproceedings{williams1986doing,
  author = {Brian C. Williams},
  title = {{Doing Time: Putting Qualitative Reasoning on Firmer Ground}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure