A Linear-Programming Approach to Temporal Reasoning

AAAI 1996

TL;DR

This paper introduces Horn Disjunctive Linear Relations (Horn DLRs), a new formalism for temporal constraint reasoning. They demonstrate that checking the satisfiability of Horn DLRs can be done efficiently using linear programming, unifying many existing tractable temporal reasoning methods.

What Problem Does This Paper Address?

Temporal reasoning, the process of understanding and inferring relationships between events and time points, is crucial in AI for applications like planning, natural language understanding, and diagnosis. Traditionally, temporal reasoning has been approached using two main paradigms: qualitative methods based on Allen's interval algebra and quantitative methods using systems of inequalities on time points. While powerful, Allen's algebra suffers from computational complexity (NP-complete), and integrating qualitative and quantitative reasoning has been challenging. Several polynomial-time subalgebras of Allen's algebra have been proposed, but extending them to handle quantitative information effectively has been difficult. This paper aims to bridge this gap by proposing a unified, tractable formalism that can express both qualitative and quantitative temporal constraints and can be solved efficiently.

Methods

The core contribution is the introduction of Horn Disjunctive Linear Relations (Horn DLRs). This formalism represents temporal constraints as disjunctions of linear relations between time points. The key innovation is proving that the satisfiability problem for Horn DLRs can be solved in polynomial time by reducing it to a linear programming (LP) problem.

The paper leverages the fact that linear programming problems are solvable in polynomial time (citing algorithms by Khachiyan and Karmarkar). They define Horn DLRs and then present an algorithm, SAT(Γ), that recursively simplifies a set of Horn DLRs. The algorithm relies on two main ideas:

  1. Convex Relations and Disequations: Horn DLRs are classified into convex relations (like <, <=, =, >=, >) and disequational relations (like ≠). The algorithm uses the fact that a set of convex relations defines a convex set in n-dimensional space, and disequations can be viewed as hyperplanes.
  2. Blocking: A DLR is said to "block" a set of convex relations if it makes the combined set unsatisfiable. The algorithm checks for these blocking conditions.

The algorithm's steps involve:

  • Identifying the set of convex relations.
  • Rejecting if the convex relations are unsatisfiable.
  • Rejecting if a disequational relation blocks the convex relations.
  • Recursively simplifying if a heterogenous relation blocks the convex relations.
  • Accepting if no blocking conditions are met.

The paper proves the soundness and completeness of this algorithm and demonstrates that it runs in polynomial time.

Datasets

Not discussed in the paper. The paper focuses on a theoretical formalism and its algorithmic properties, using a fictional crime scenario for illustration rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Unifying Qualitative and Quantitative Reasoning: Horn DLRs provide a single framework that can naturally express both qualitative relationships (like "before" or "overlaps") and quantitative constraints (like "duration is between X and Y").
  • Linear Programming as a Powerful Tool: The paper highlights the surprising power of linear programming for solving complex temporal reasoning problems. By abstracting temporal constraints into a form solvable by LP, they achieve polynomial-time complexity.
  • Maximal Tractable Subclass Inheritance: A significant finding is that Horn DLRs subsume many existing tractable temporal reasoning formalisms, including the ORD-Horn algebra. This means that the maximality results for tractability in these subclasses can be extended to Horn DLRs.
  • Simplicity Through Abstraction: The authors emphasize that their LP-based approach leads to a surprisingly simple algorithm, as much of the low-level temporal reasoning is handled by the LP solver.

Key Results

  • Polynomial-Time Satisfiability: The paper proves that deciding the satisfiability of Horn DLRs is solvable in polynomial time.
  • Subsumption of Existing Formalisms: Horn DLRs can express constraints from ORD-Horn algebra, continuous endpoint algebra, pointisable endpoint algebra, Koubarakis's formulas, simple temporal constraints, CPA/single interval formulas, and TG-II formulas.
  • HORNDLRSAT is P-complete: The satisfiability problem for Horn DLRs is shown to be P-complete, meaning it's efficiently solvable but not significantly faster on parallel computers (unless P=NC).

Limitations and Future Work

  • Computational Cost of LP: While polynomial, the authors acknowledge that linear programming can be computationally "heavy" in practice. The presented algorithm is optimized for correctness proof rather than execution speed.
  • Assumptions about Time: The current framework assumes time is linear, dense, and unbounded. The paper notes that changing these assumptions (e.g., to discrete time) could make reasoning computationally harder, though some positive results for discrete time exist.
  • Future Work: The authors suggest exploring whether improved algorithms can compete with specialized systems like TIMEGRAPH II in terms of execution speed. They also point to the need to investigate the impact of different temporal assumptions (like discrete time) on reasoning complexity.

Summary updated

BibTeX
@inproceedings{1996linear,
  title = {{A Linear-Programming Approach to Temporal Reasoning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure