A Method for Metric Temporal Reasoning

AAAI 2002

TL;DR

This paper introduces STP*, a new point-based approach for metric temporal reasoning that extends the expressiveness of existing tractable interval algebra fragments while remaining computationally efficient. It offers a simpler implementation than previous methods like Horn DLRs and demonstrates competitive performance in experiments.

What Problem Does This Paper Address?

Temporal reasoning, the task of understanding and manipulating time-based information, is crucial in many AI applications. While qualitative temporal reasoning (e.g., "event A happens before event B") has well-studied formalisms like Allen's interval algebra, incorporating quantitative (metric) information (e.g., "event A happens at least 5 minutes before event B") significantly increases complexity. Existing methods for metric temporal reasoning, such as Horn Disjunctive Linear Relations (Horn DLRs), are powerful but notoriously difficult to implement due to their reliance on complex linear programming algorithms. Other approaches, like augmenting interval algebras with Simple Temporal Problems (STPs), are simpler but less expressive. This paper aims to bridge this gap by proposing a new formalism, STP*, that balances expressiveness and implementability for metric temporal reasoning.

Methods

The core contribution is the introduction of STP (Simple Temporal Problem with disjunctions of disequalities). STP extends the standard Simple Temporal Problem (STP) by allowing constraints of the form:

$x_1 + r_1 \le y_1 \lor x_2 + r_2 \ne y_2 \lor \dots \lor x_n + r_n \ne y_n$

where $x_i, y_i$ are time points, $r_i$ are real constants, and $\lor$ denotes disjunction. This allows for more complex relationships between time points than standard STPs.

The paper also presents Algorithm STP-1, a novel algorithm for deciding the satisfiability of STP* problem instances. This algorithm is based on a modified shortest path algorithm (similar to Floyd-Warshall) and iteratively refines a distance matrix representing the shortest paths between time points. It handles disjunctive clauses by attempting to satisfy them and removing them if they are satisfied or if they lead to contradictions. The algorithm is proven to accept only satisfiable instances and reject only unsatisfiable ones.

Furthermore, the authors demonstrate how STP can express the tractable preconvex fragment of Allen's interval algebra (also known as the ORD-Horn fragment). This means that problems solvable by this fragment can be translated into STP and solved efficiently. They also show that STP can express some constraints from the rectangle algebra*, a formalism for reasoning about spatial relationships.

Datasets

Not discussed in the paper. The authors generated random problem instances for their experiments.

Key Insights and Ideas

  • Bridging the Expressiveness-Complexity Gap: STP* offers a sweet spot between highly expressive but complex formalisms (like Horn DLRs) and simpler but less expressive ones (like basic STPs or restricted interval algebras).
  • The Power of Disjunctive Disequalities: Allowing disjunctions of disequalities in temporal constraints significantly increases expressiveness without making the problem intractable. This is a key insight for designing more practical temporal reasoning systems.
  • Efficient Algorithm for STP*: Algorithm STP-1 provides a practical and relatively simple way to solve STP* problems, making metric temporal reasoning more accessible.
  • STP* as a Unifying Formalism: The ability of STP* to express the ORD-Horn fragment of interval algebra suggests its potential as a unifying formalism for various temporal reasoning tasks.

Key Results

  • Expressibility: STP* subsumes the expressiveness of the tractable preconvex fragment of the augmented interval algebra.
  • Algorithm Performance: Algorithm STP-1 demonstrates good practical performance. For converted interval algebra problems, it runs in approximately $O(n^{3.35})$ time, which is comparable to or better than other methods when considering the added expressiveness.
  • Metric Information Impact: Adding metric constraints to interval algebra problems did not significantly degrade performance in practice, and in some cases, even improved it by allowing unsatisfiable instances to be detected earlier.
  • Comparison to Allen's Algebra: When solving converted interval algebra problems, the STP* solver was found to be efficient, with a constant factor overhead (around 8x) compared to a solver working directly on intervals, which is attributed to the extended expressibility.

Limitations and Future Work

  • Interval Conversion Overhead: The current approach converts interval algebra problems into point-based STP* problems, which doubles the number of variables. Future work could explore handling purely qualitative interval constraints directly to improve efficiency.
  • Rectangle Algebra Expressibility: The full extent to which STP can express rectangle algebra relations remains an open question. The authors specifically ask if the full set of strongly-preconvex RA relations can be expressed using STP.
  • Comparison with Horn DLRs: The paper notes the lack of publicly available implementations of Horn DLR solvers, preventing a direct comparison of STP* with this powerful formalism.
  • Practical Implementation: While the algorithm is described as "easily implementable," further studies on actual implementations and comparisons with other approaches are suggested.

Summary updated

BibTeX
@inproceedings{2002method,
  title = {{A Method for Metric Temporal Reasoning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2002},
}
Figure