Combining Qualitative and Quantitative Constraints in Temporal Reasoning

Itay MeiriAAAI 1991

Abstract

This paper introduces a unified framework for temporal reasoning that bridges the gap between qualitative logic (e.g., relative ordering) and quantitative metrics (e.g., specific durations). By modeling temporal entities as variables in a constraint satisfaction network, the research identifies new "islands of tractability"—specific classes of complex temporal problems that can be solved in polynomial time.

Introduction

In the early 1990s, temporal reasoning was bifurcated into two distinct paradigms. Qualitative approaches, such as Allen’s Interval Algebra, were adept at describing relative orderings but failed to incorporate numerical data. Conversely, quantitative metric networks handled distances between time points effectively but struggled with disjunctive qualitative statements (e.g., "Event A occurred either before or after Event B, but not simultaneously").

Real-world reasoning, such as scheduling a commute involving multiple transit events and specific departure windows, requires both types of information. This paper proposes the General Temporal Constraint Network (GTCN) to handle these mixed constraints simultaneously without the computational explosion seen in previous hybrid models.

The General Temporal Constraint Network

The author proposes a model where variables can represent both time points and time intervals. Constraints within this network are unified: they may be metric (sets of real-number intervals) or qualitative (sets of basic relations like before, meets, or overlaps).

Figure 1: A General Temporal Constraint Network illustrating the integration of time points ($P_0 \dots P_4$), intervals ($J, F$), and mixed qualitative/quantitative constraints.

To solve these networks, the paper extends standard algebraic operations—specifically intersection and composition (transitivity)—to operate across mixed constraint types. The framework employs three primary strategies: decomposition into Simple Temporal Problems (STPs), adapted constraint satisfaction algorithms (such as Path Consistency), and a Meta-CSP approach that treats qualitative relation selection as a higher-level variable problem.

Unifying Qualitative and Quantitative Logic

A core insight of the paper is the mathematical unification of qualitative relations between intervals and points by mapping them to relations between their respective endpoints. This allows qualitative logic to be processed within the same mathematical structure as quantitative metric bounds.

Figure 5: The mapping of qualitative relations between a point $p$ and an interval $I$ to specific endpoint constraints.

By mapping out the relationship between different temporal algebras, the paper identifies the Interval-Point Algebra (IPA) as the boundary where reasoning shifts from tractable to NP-hard. However, the author discovered that Convex Point Algebra (CPA) networks—where relations do not contain "gaps" (like $\neq$)—remain solvable in polynomial time even when augmented with complex numerical domain constraints.

Key Results and Complexity

The paper establishes several critical complexity bounds and efficiency gains:

  • Complexity Bounds: The research proves that deciding consistency for a general IPA network is NP-hard.
  • Polynomial Solutions: It demonstrates that augmented CPA networks can be solved using arc and path consistency in $O(en^2K^2)$ time, where $K$ is the number of intervals in a domain.
  • Efficiency Gains: The integrated model is shown to be significantly more efficient than contemporary alternatives. For specific network conversions, the proposed approach reaches a complexity of $O(n^3R^3)$, compared to the $O(n^5R^3)$ required by previous models.

Conclusion

By integrating qualitative and quantitative data into a single graph, this model allows constraint propagation to occur at the "knowledge level," making it both conceptually clearer and computationally faster. While currently limited to binary constraints between two objects, this framework provides a robust foundation for future work in non-binary temporal reasoning and more complex scheduling tasks.

Summary updated

BibTeX
@inproceedings{meiri1991combining,
  author = {Itay Meiri},
  title = {{Combining Qualitative and Quantitative Constraints in Temporal Reasoning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure