Constraint Propagation Algorithms for Temporal Reasoning

Marc B. Vilain, Henry A. KautzAAAI 1986

Introduction

In the mid-1980s, the field of Artificial Intelligence faced a significant challenge in representing and reasoning about temporal information. James Allen's "Interval Algebra" emerged as a dominant framework, allowing events to be represented as intervals and related through thirteen basic qualitative relations, such as "before," "during," or "overlaps." While intuitive for human language and planning, the computational properties of this algebra were not fully understood. This paper investigates the complexity of reasoning within the Interval Algebra and proposes a more efficient alternative based on time points.

The Complexity of Interval Algebra

The primary goal of temporal reasoning systems is to determine the consistency of a set of temporal assertions and to derive all possible consequences. Allen originally proposed a polynomial-time constraint propagation algorithm (path consistency) to handle these tasks. However, this algorithm was known to be incomplete—it could fail to detect certain contradictions or miss valid inferences.

The thirteen basic relations between time intervals A and B in Allen's Interval Algebra.

The authors prove that the problem of determining satisfiability in the full Interval Algebra is NP-hard. This result was achieved by reducing the 3-clause satisfiability problem (3-SAT) to a temporal reasoning problem. The core difficulty lies in the algebra's ability to express disjunctive ambiguity, such as the relation "A is either before or after B." Such disjunctions create a combinatorial explosion that prevents any "perfect" fast algorithm from existing, assuming $P \neq NP$.

The Point Algebra: A Tractable Alternative

To address the computational intractability of the Interval Algebra, the authors introduce a "Point Algebra." In this framework, the fundamental units are points in time (representing the start or end of an event) related by simple primitives: PRECEDES ($<$), SAME ($=$), and FOLLOWS ($>$).

The authors demonstrate that reasoning within this Point Algebra is significantly more efficient. They present an algorithm that achieves completeness in $O(n^3)$ time and $O(n^2)$ space, where $n$ is the number of time points. This efficiency stems from the simpler $3 \times 3$ multiplication table used for point relations, compared to the $13 \times 13$ table required for intervals.

The Tractable Fragment and the Translation Gap

A key insight of the paper is the identification of a "tractable fragment" of the Interval Algebra. Many common interval relations—such as during, overlaps, and meets—can be translated directly into conjunctions of point relations. For example, "A during B" can be expressed as "(Start of B < Start of A) AND (End of A < End of B)."

An illustration of the 'During' relation, where interval A is contained within the span of interval B.

The boundary of tractability is defined by the "translation gap." Relations that require disjunctions of point relations (like the "before or after" example) are the source of NP-hardness. By restricting reasoning to the fragment that maps to simple point relations, AI systems can maintain efficiency without sacrificing the most useful aspects of temporal logic.

Conclusion

This work clarifies the trade-off between expressivity and efficiency in temporal reasoning. While the full Interval Algebra is computationally "hard," the Point Algebra provides a robust and complete framework for a large and useful subset of temporal relations. This distinction has guided the design of subsequent AI planning and scheduling systems, emphasizing the importance of identifying tractable sub-logics for practical applications.

Summary updated

BibTeX
@inproceedings{vilain1986constraint,
  author = {Marc B. Vilain and Henry A. Kautz},
  title = {{Constraint Propagation Algorithms for Temporal Reasoning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure