Tractable Classes of Metric Temporal Problems with Domain Rules

Abstract

In this paper, we will deal with some important kinds of metric temporal reasoning problems that arise in many real-life situations. In particular, events X0, X1 ... XN are modeled as time points, and a constraint between the execution times of two events Xi and Xj is either simple temporal (of the form Xi - Xj ∈ [a, b]), or has a connected feasible region that can be expressed using a finite set of domain rules each in turn of the form Xi ∈ [a, b] → Xj ∈ [c, d] (and conversely Xj ∈ [e, f] → Xi ∈ [g, h]). We argue that such rules are useful in capturing important kinds of non-monotonic relationships between the execution times of events when they are governed by potentially complex (external) factors. Our polynomial-time (deterministic and randomized) algorithms for solving such problems therefore enable us to efficiently deal with very expressive representations of time.