Tractable Classes of Metric Temporal Problems with Domain Rules

T. K. Satish Kumar

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.

Subjects: 3.6 Temporal Reasoning; 1.12 Scheduling


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.