Introduction
Representing how events relate in time is a fundamental task in artificial intelligence. Whether planning a robot's tasks or understanding natural language, systems must reason about relations such as "Event A happens during Event B" or "Event C overlaps Event D." The standard framework for this is Allen’s Interval Algebra, which defines 13 basic relations between time intervals.
While the 13 basic relations are straightforward, allowing for uncertainty (e.g., "A happens before or meets B") leads to a power set of $2^{13}$ (8,192) possible relations. Determining satisfiability—whether a set of such constraints is consistent with a linear timeline—is NP-hard for the full algebra. To build practical systems, researchers seek "tractable subclasses": subsets of the algebra where reasoning can be performed in polynomial time.
The ORD-Horn Subclass
This paper introduces the ORD-Horn subclass ($\mathcal{H}$), identifying it as the largest known subset of Allen’s algebra that remains computationally "easy." The authors' approach rests on translating interval relations into logical "ORD clauses" involving the endpoints of the intervals.
A relation belongs to the ORD-Horn subclass if its endpoint constraints can be expressed as Horn clauses—logical statements with at most one positive literal. Horn clauses are a well-known "sweet spot" in computer science because they are significantly easier to solve than general propositional logic.
Methods and Proof of Maximality
The research employs three primary pillars to establish the properties of $\mathcal{H}$:
- Logical Encoding: Relations are mapped to constraints on interval endpoints ($X^-, X^+, Y^-, Y^+$) using the axioms of partial orders.
- Path-Consistency: The authors prove that the "path-consistency" algorithm—a standard technique that checks triples of variables for local consistency—is sufficient to guarantee global satisfiability for this subclass.
- Machine-Assisted Proof: To prove that $\mathcal{H}$ is maximal, the authors used a computer program to perform an exhaustive case analysis, showing that adding any relation outside $\mathcal{H}$ to the set of 13 basic relations makes the satisfiability problem NP-hard.
Key Insights
- Expressiveness: The ORD-Horn subclass contains 868 relations, roughly 10.6% of the full algebra. This is a significant improvement over previous tractable fragments, such as the "pointisable" subclass (188 relations) or the "continuous endpoint" subclass (83 relations).
- Algorithmic Completeness: For years, path-consistency was used as a heuristic. This paper identifies the exact boundary where this heuristic becomes a definitive proof of satisfiability.
- Uniqueness: The authors demonstrate that $\mathcal{H}$ is the unique greatest tractable subclass containing all 13 basic relations, making it the optimal choice for general-purpose temporal reasoning systems.
Conclusion
The identification of the ORD-Horn subclass provides a powerful tool for AI developers. By using $\mathcal{H}$ as a base case, developers can speed up solvers for the full NP-hard algebra through more efficient backtracking searches. While 90% of the algebra remains NP-hard, the ORD-Horn subclass offers the most expressive language currently available for guaranteed polynomial-time temporal reasoning.
Summary updated