Tractable Classes of Metric Temporal Problems with Domain Rules

Proceedings of the AAAI Conference on Artificial Intelligence, 21

Volume

Technical Papers

Reasoning about Plans and Actions

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 X_0, X_1 ... X_N are modeled as time points, and a constraint between the execution times of two events X_i and X_j is either simple temporal (of the form X_i - X_j in [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 X_i in [a,b] -> X_j in [c,d] (and conversely X_j in [e,f] -> X_i in [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.