An Algebra of Granular Temporal Relations for Qualitative Reasoning

Quentin Cohen-Solal, Maroua Bouzid, Alexandre NiveauIJCAI 2015

Abstract

This paper introduces a new qualitative temporal algebra that allows AI systems to reason about time across different scales—like minutes, days, or months—without needing exact numerical durations. By extending existing frameworks to include relations between both time points and intervals, the authors provide a robust method for checking the consistency of imprecise, multi-scale temporal information.

Introduction

In classical AI, Qualitative Temporal Reasoning (QTR) helps agents understand how events relate (e.g., "Event A happened during Event B") without needing precise timestamps. The most famous tool for this is Allen’s Interval Algebra. However, standard algebras struggle with granularity.

Imagine two meetings: Meeting A is from 1:30 to 3:10 PM, and Meeting B is from 3:15 to 5:07 PM. At the minute scale, A is "before" B. At the hour scale, they might "meet" or overlap. At the day scale, they are indistinguishable—both happened on the same day. Previous attempts to solve this had a major flaw: they couldn't handle cases where an interval effectively becomes a "point" when viewed at a coarser scale. They also often required quantitative data, which isn't always available when processing natural language or vague human input.

Methodology

The authors propose a Granular Temporal Algebra that operates purely qualitatively. Their approach includes:

  1. Expanded Relations: Instead of just interval-to-interval relations, they use a set of 26 elementary relations that cover point-to-point, interval-to-interval, and point-to-interval interactions. This allows an interval at a fine scale to "shrink" into a point at a coarser scale without breaking the logic.
Endpoint relations for elementary temporal relations
  1. Conversion Operators: They define "Upward" ($\uparrow$) and "Downward" ($\downarrow$) conversion rules. These rules describe how a relation (like "overlaps") changes when you zoom out to a coarser granularity or zoom in to a finer one.
Upward and downward conversion rules for temporal relations
  1. Qualitative Granularities: Their system doesn't need to know that a day is 24 hours. It only needs to know the relative scale (e.g., "days are coarser than hours").
  2. Algebraic Closure Algorithm: They provide a polynomial-time algorithm to propagate these temporal constraints across a network. This allows a system to take a bunch of scattered facts at different scales and determine if they are logically consistent.

Key Insights and Results

  • The Power of Coarseness: Counter-intuitively, reasoning at a coarser scale can sometimes provide more information. If we know two events are "separated" even at a very coarse scale, we know they are much further apart than if they were just "before" each other at a fine scale.
  • Handling the "Point" Transition: By including point-interval relations, the algebra avoids the "dead ends" of previous models. It gracefully handles the transition of an event from a duration-based interval to a single-moment point as the scale changes.
  • Algorithmic Efficiency: The proposed algebraic closure algorithm has a complexity of $O(mn^2(m+n))$, where $n$ is the number of time entities and $m$ is the number of granularities. For a fixed number of scales, this scales similarly to standard non-granular temporal algebras ($O(n^3)$).

Limitations and Future Work

While checking a specific "scenario" is fast, the general problem of checking consistency when relations are ambiguous remains NP-complete, a limitation inherited from Allen’s Algebra. Future work should identify "tractable subclasses" that can be solved quickly even with ambiguity. Additionally, the authors believe these granular concepts can be generalized to spatial reasoning (e.g., a city as a point vs. an area) and require further analysis regarding dense vs. discrete time domains.

Summary updated

BibTeX
@inproceedings{cohensolal2015algebra,
  author = {Quentin Cohen-Solal and Maroua Bouzid and Alexandre Niveau},
  title = {{An Algebra of Granular Temporal Relations for Qualitative Reasoning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure