The Consistent Labeling Problem in Temporal Reasoning

Edward P. K. TsangAAAI 1987

Abstract

This paper formalizes the task of ensuring consistency in temporal networks as a Consistent Labeling Problem (CLP). By analyzing the relationship between interval-based and point-based temporal algebras, it demonstrates that the computational intractability of temporal reasoning is a fundamental consequence of disjunctive logic rather than a byproduct of interval representations. The work provides a framework for applying standard constraint satisfaction heuristics to temporal planning.

Introduction

In artificial intelligence, temporal reasoning is essential for managing networks of events and their interdependencies. James Allen’s 1983 interval algebra introduced a powerful framework for qualitative temporal relations (e.g., "during," "overlaps"). However, subsequent research by Vilain and Kautz (1986) suggested that Allen’s algebra was computationally intractable (NP-hard), leading to a shift toward point-based representations which were perceived as more efficient.

Edward Tsang re-evaluates this dichotomy, arguing that the difficulty of temporal reasoning is not inherent to intervals themselves but arises from the inclusion of disjunction—the ability to specify that an event relates to another in multiple possible ways. This paper aims to unify temporal reasoning with general Constraint Satisfaction Problem (CSP) research by framing it as a CLP.

Formalizing Temporal Reasoning as a CLP

Tsang formalizes temporal reasoning by mapping it onto the components of a CLP:

  • Variables: The temporal relations between every pair of intervals in a given network.
  • Domain: The set of 13 primitive temporal relations defined by Allen (e.g., before, meets, overlaps, starts, during, finishes, equals, and their inverses).
  • Constraints: These include transitivity rules (e.g., if A is before B and B is before C, then A must be before C) and specific domain requirements.

To execute a plan, a system must find a "date line"—a specific, consistent assignment of relations that maps intervals onto a linear timeline. This process is equivalent to finding a solution to a CLP.

The Role of Disjunction and Complexity

A key insight of the paper is that the complexity of temporal reasoning is driven by disjunction. While conjunctive point algebra (where only a single relation is allowed between points) is tractable, the introduction of disjunctions (e.g., "A happens before or after B") makes the problem NP-hard in both point and interval representations.

Figure 1: Point-based decomposition of disjunctive interval relations.

As shown in Figure 1, representing disjunctive interval relations in a point-based system requires defining multiple possible relations between the endpoints of intervals A and B. For example, the notation [< >] indicates a disjunction where one point must be either less than or greater than another. This demonstrates that moving to a point-based representation does not eliminate the underlying combinatorial explosion; it merely shifts the disjunction from the interval level to the point level.

Search Strategies and Heuristics

By treating temporal reasoning as a CLP, Tsang identifies several search strategies to improve efficiency:

  1. Variable Ordering: Applying the "Fail First" principle by labeling the most constrained relations first to prune the search tree early.
  2. Value Ordering: Attempting the "least restrictive" temporal relations first to minimize backtracking. Tsang proposes a hierarchy of restrictiveness; for instance, "equals" is highly restrictive as it fixes both endpoints, while "before" is less so.
  3. Lookahead: Utilizing Allen’s transitivity-based constraint propagation to maintain "3-consistency" during the search, preventing the exploration of paths that are locally inconsistent.

Conclusion

Tsang’s work clarifies that the tractability of temporal reasoning depends on the logical structure of the constraints (conjunctive vs. disjunctive) rather than the primitive units (points vs. intervals). By establishing temporal reasoning as a formal CLP, the paper provides a robust theoretical foundation for using general CSP heuristics in temporal planners. While metric time and optimal scheduling remain separate challenges, this framework offers a clear path for managing qualitative temporal consistency in complex AI systems.

Summary updated

BibTeX
@inproceedings{tsang1987consistent,
  author = {Edward P. K. Tsang},
  title = {{The Consistent Labeling Problem in Temporal Reasoning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure